Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
28.05.2004, 08:11 Uhr
virtual
Sexiest Bit alive
(Operator)

Unter einer PalindromZahl versteht man eine Zahl, welche von vorne und von hinten gelesen den gleichen Wert hat: "12321" wäre so eine Zahl.

Zu fast allen Zahlen läßt sich eine Palindromzahl finden, mit folgendem Algorithmus:
1. Man addiert zur Zahl N die Umkehrung N'. Ist etwa N=290, so ist N'=092, die Summe also 382.
2. Ist die Summe eine Palindromzahl, so sind wir fertig, ansonsten ist Schritt 1 zu wiederholen. (382 + 283 = 665; 665 + 566 = 1231; 1231 + 1321 = 2552)

Wir wollen nun der vereinfachungshalber davon ausgehen, daß wenn der Zahlenbereich eines unsigned long long (0..2^64) bei der Berechnung verlassen wird, die Zahl sich nicht auf diese Weise in eine Palindromzahl umwandeln läßt.

Zu finden ist die erste Zahl, welche sich nicht mit obigem Algorithmus in eine Palindromzahl verwandeln läßt.

Nur für Hardcoredumper: bitte kein unsigned long long benutzen, sondern eine einige string basierte addition von Zahlen.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 28.05.2004 um 08:13 Uhr von virtual editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
28.05.2004, 12:28 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

Zitat:

unsigned long long (0..2^64)

[klugscheissmode an]
nein nur bis 2^64-1

wenn die obere grenze exklusive sein soll dann bei der unteren bitte eine eckige klammer verwenden
[klugscheissmode aus]

schön das du mal wieder ein rätsel machst. werd mich morgen mal dran versuchen...
--
...fleißig wie zwei Weißbrote

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
28.05.2004, 14:27 Uhr
Oliver
S2-Pixelgeneral

Weiß nicht, ob ich das richtig verstanden habe, aber wie wärs damit (kann auch falsch sein):

C++:

#include <iostream>
#include <string>
using namespace std;

#define max(z1,z2) ((z1>z2)?z1:z2)
#define CharToInt(z) (z-48)
#define IntToChar(z) (z+48)
#define IsPalindrom(z) (z==Umkehren(z))

enum Vergleichsergebnis
{
    VG_GROESSER,
    VG_KLEINER,
    VG_GLEICH
};

// Strings addieren
string StrAdd(string zahl1,string zahl2)
{
    string ret;
    int i;

    // Stellenzahl berechnen, damit Nullen aufgestocket werden können
    int stellenzahl=max(zahl1.length(),zahl2.length());

    // Nullen aufstocken
    int diff;
    // im ersten String
    diff=stellenzahl-zahl1.length();
    for(i=0;i<diff;++i)
        zahl1.insert(zahl1.begin(),'0');
    // dasselbe in grün
    diff=stellenzahl-zahl2.length();
    for(i=0;i<diff;++i)
        zahl2.insert(zahl2.begin(),'0');

    // Schriftlich addieren
    int merke=0;
    int summand1,summand2;
    int summe;

    for(i=stellenzahl-1;i>=0;--i)
    {
        summand1=CharToInt(zahl1[i]);
        summand2=CharToInt(zahl2[i]);

        summe=summand1+summand2+merke;

        if(summe>9)
        {
            ret.insert(ret.begin(),IntToChar(summe-10));
            merke=1;
        }
        else
        {
            ret.insert(ret.begin(),IntToChar(summe));
            merke=0;
        }
    }
    if(merke==1)
        ret.insert(ret.begin(),'1');

    return ret;

}

// Vergleichen von Strings
Vergleichsergebnis StrVergleiche(string zahl1,string zahl2)
{
    // Stellenzahl berechnen, damit Nullen aufgestocket werden können
    int stellenzahl=max(zahl1.length(),zahl2.length());

    // Nullen aufstocken
    int diff;
    // im ersten String
    diff=stellenzahl-zahl1.length();

    int i;
    for(i=0;i<diff;++i)
        zahl1.insert(zahl1.begin(),'0');
    // dasselbe in grün
    diff=stellenzahl-zahl2.length();
    for(i=0;i<diff;++i)
        zahl2.insert(zahl2.begin(),'0');

    for(i=0;i<stellenzahl;++i)
    {
        if(CharToInt(zahl1[i])>CharToInt(zahl2[i]))
            return VG_GROESSER;
        else if(CharToInt(zahl1[i])<CharToInt(zahl2[i]))
            return VG_KLEINER;
    }

    return VG_GLEICH;
}

string Umkehren(string zahl1)
{
    string ret;

    int length;
    length=zahl1.length();

    for(int i=0;i<length;++i)
    {
        ret.insert(ret.begin(),zahl1[i]);
    }

    return ret;
}

int main()
{
    // Grenze für Palindromzahlenalgorithmus
    // muss normalerweise nach Aufgabenstellung auf 2^64-1 stehen
    // lässt sich anpassen
    const string Grenze="10000000";
    // Kleinste Zahl finden die, nicht mit dem Algorithmus brechnet werden kann
    string zahl="1";
    string umkehrung;
    string temp;
    while(1)
    {
        temp=zahl;
        while(!IsPalindrom(temp))
        {
            if(StrVergleiche(temp,Grenze)==VG_GROESSER)
            {
                cout << "Die kleinste Zahl ist gefunden, sie heisst: " << zahl;
                goto raus;
            }
            // Zahl für Umkehrung
            umkehrung=Umkehren(temp);
            // Sich selbst und Umkehrung addieren
            temp=StrAdd(temp,umkehrung);

        }
        // Nächste Zahl prüfen
        zahl=StrAdd(zahl,"1");
    }

raus:

    cin.get();
    return 0;
}

--
Demokratie ist die Diktatur der Mehrheit.

www.siedler25.org/ ( Siedler2 - Remake )

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
28.05.2004, 18:23 Uhr
0xdeadbeef
Gott
(Operator)

Mit String-Addition kann man den Schritt ewig wiederholen, von daher ist das Problem auf diese Art nicht lösbar. Ich setze einfach mal eine Wiederholungs-Obergrenze:

C++:

#include <algorithm>
#include <gmpxx.h>
#include <iostream>
#include <string>

const unsigned int max_iterations = 10;

bool is_palindrome(std::string s) {
  for(std::string::size_type i = 0; i < s.size() / 2; ++i)
    if(s[i] != s[s.size() - i - 1])
      return false;
  return true;
}

bool is_palindrome(mpz_class x) {
  return is_palindrome(x.get_str());;
}

int main() {
  mpz_class i, n;
  std::string s;
  int count;

  for(i = 0;; ++i) {
    n = i;
    count = 0;
    while(!is_palindrome(n)) {
      std::cout << n << '\t';
      if(++count > max_iterations)
        break;
      s = n.get_str();
      std::reverse(s.begin(), s.end());
      n += mpz_class(s);
    }
    std::cout << n << std::endl;
    if(count > max_iterations)
      break;
  }

  return 0;
}

So müsste es gehen - allerdings scheint die GMP 4.1.3 einen Bug zu haben, so dass "08" nicht richtig umgewandelt wird, weswegen er 80 als nicht umwandelbar erkennt. Oder meine Hardware spinnt mal wieder, was auch gut sein kann. Es war mir jedenfalls grad zu nervig, nen Workaround dafür zu schreiben...
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 28.05.2004 um 18:24 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
07.06.2004, 15:10 Uhr
virtual
Sexiest Bit alive
(Operator)

Hi,
ich wollte Euch meine Lösung nicht vorenthalten. Schließlich muß ich ja belegen, daß ich hier nicht irgendjemanden meine Hausaufgaben machen lasse und es selber kann:

C++:

#include <string.h>

#define MAX_DIGITS 1024
typedef char number_t[MAX_DIGITS];

int is_palindrome(const number_t number)
{
    size_t len = strlen(number);
    size_t i;
    for(i=0; i<len; ++i)
    {
        if (number[i] != number[len-i-1])
        {
            return 0;
        }
    }
    return 1;
}

void reverse_number(number_t result, const number_t number)
{
    size_t len = strlen(number);
    size_t i;
    for(i=0; i<len; ++i)
    {
        result[len-i-1] = number[i];
    }
    result[i] = 0;
}

int add(number_t result, const number_t a, const number_t b)
{
    int add = 0;
    size_t i;
    for(i=0; a[i] && b[i]; ++i)
    {
        int digit = a[i]-'0'+b[i]-'0'+add;
        result[i] = digit%10 + '0';
        add = digit/10;
    }
    if (a[i])
    {
        for(; a[i]; ++i)
        {
            int digit = add+a[i]-'0';
            result[i] = digit%10+'0';
            add = digit/10;
        }
    }else if (b[i])
    {
        for(; b[i]; ++i)
        {
            int digit = add+b[i]-'0';
            result[i] = digit%10+'0';
            add = digit/10;
        }
    }
    if (add) result[i++] = '1';
    if (i>=MAX_DIGITS)
    {
        fprintf(stderr, " (Overflow)");
        return 0; /* Overflow */
    }
    result[i] = 0;
    return 1;
}

size_t make_palindrome(number_t palindrome, const number_t number)
{
    size_t loops = 1;
    number_t reverse;
    strcpy(palindrome, number);

    while (!is_palindrome(palindrome))
    {
        reverse_number(reverse, palindrome);
        if (!add(palindrome, palindrome, reverse))
        {
            return 0;
        }
        ++loops;
        fprintf(stderr, ".");
    }
    return loops;
}

int main()
{
    const number_t one = "1";
    number_t number = "0";
    number_t palindrome;
    size_t loops;
    size_t i;
    for(i=0; i<20000; ++i)
    {
        number_t temp;
        reverse_number(temp, number);
        add(temp, temp, one);
        reverse_number(number, temp);
        fprintf(stderr, "%s ", number);
        loops = make_palindrome(palindrome, temp);
        if (!loops)
        {
            fprintf(stderr, " no palindrome found.\n");
        }else
        {
            reverse_number(palindrome, palindrome);
            fprintf(stderr, " => %s\n", palindrome);
        }
    }
}

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
07.06.2004, 16:40 Uhr
0xdeadbeef
Gott
(Operator)

Ein bisschen C++iger und lesbarer:

C++:

#include <algorithm>
#include <gmpxx.h>
#include <iostream>
#include <string>

const unsigned int max_iterations = 10;

bool is_palindrome(std::string s) {
  std::string t = s;
  std::reverse(t.begin(), t.end());
  return (s == t);
}

int main() {
  mpz_class i, n;
  std::string s;
  int count;

  for(i = 0;; ++i) {
    n = i;
    count = 0;
    while(!is_palindrome(n.get_str())) {
      std::cout << n << '\t';
      if(++count > max_iterations)
        break;
      s = n.get_str();
      std::reverse(s.begin(), s.end());
      n += mpz_class(s);
    }
    std::cout << n << std::endl;
    if(count > max_iterations)
      break;
  }

  return 0;
}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: