Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
31.01.2003, 14:04 Uhr
virtual
Sexiest Bit alive
(Operator)

Eine Natürliche Zahl N heißt vollkommen, wenn die Summe ihrer Teiler (außer N selbst) die Zahl selbst ergibt. So ist 6 vollkommen, weil 6 == 1 + 2 + 3 ist. Schreibe eine Funktion, welche ermittelt, ob die als Parameter übergebene Zahl vollkommen ist.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 31.01.2003 um 14:04 Uhr von virtual editiert.

Profil || Private Message || Suche

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

001
31.01.2003, 19:45 Uhr
Bruder Leif
dances with systems
(Operator)

Moin!

Hier mal der naive Ansatz:

C++:

int Vollkommen(int Zahl)
{
   int i, iBuffer=Zahl;

   /* Simpler Ansatz: Einfach alle Zahlen durchprobieren */
   /* Schneller wäre: Primfaktorzerlegung, Kombinationen der Primfaktoren addieren */
   for(i=1; i<Zahl; i++) if(!(Zahl % i)) iBuffer -= i;
   return !iBuffer;
}

#define OBERGRENZE 10000

int main()
{
   int i;

   printf("Vollkommene Zahlen im Raum bis %d:\n\n", OBERGRENZE);
   for(i=1; i<OBERGRENZE; i++) if(Vollkommen(i)) printf("%2d\t", i);
   return 0;
}

--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

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

002
31.01.2003, 20:11 Uhr
~0xdeadbeef
Gast

Na, der schnellste Algorithmus wäre wohl

C++:

bool isPerfect(unsigned long long llZahl) {
return (llZahl == 6 || llZahl == 28 || llZahl == 496 || llZahl == 8128 || lZahl == 33550336 || llZahl == 8589869056 || llZahl == 137438691328);
}

Wenn mich nicht alles täuscht, ist die nächste dann schon ne ganze Ecke größer, als ein heutiger Computer das fassen könnte.

Profil || Private Message || Suche

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

003
31.01.2003, 20:19 Uhr
~0xdeadbeef
Gast

Wenn du rechnen willst - Primfaktorzerlegung ist bei großen Zahlen sehr rechenintensiv, also würde ich mir folgendes Kriterium schnappen:

Eine Zahl ist genau dann vollkommen, wenn sie der Form 2^n *(2^(n+1) - 1) mit n aus N und 2^(n+1) - 1 prim ist. Dementsprechend würde ich das ganze so anpacken:

C++:

unsigned long long _zwei_hoch(int n) {
    if(n == 0) return 1;
    if(n % 2) return 2 * _zwei_hoch(n-1);
    return _zwei_hoch(n/2) * _zwei_hoch(n/2);
}

bool isPerfect(unsigned long long ullZahl) {
    int n;
    for(n = 0; !(ullZahl % 2); ++n) {
        ullZahl /= 2;
    }
    return ullZahl == (_zwei_hoch(n+1) - 1);
}

Habs jetzt nicht getestet, aber ich denke, so müsste es gehen.

Profil || Private Message || Suche

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

004
31.01.2003, 20:25 Uhr
~0xdeadbeef
Gast

O hoppla, fehlt noch zu testen, das _zwei_hoch(n+1) - 1 prim ist, also so:

C++:

unsigned long long _zwei_hoch(int n) {
    if(n == 0) return 1;
    if(n % 2) return 2 * _zwei_hoch(n-1);
    return _zwei_hoch(n/2) * _zwei_hoch(n/2);
}

bool isPrime(unsigned long long p) {
    if (p < 2 && !p%2) return false;
    for(unsigned long long x = 3; p > x*x; x += 2) if (!p%x) return false;
    return true;
}

bool isPerfect(unsigned long long ullZahl) {
    int n;
    unsigned long long p;
    for(n = 0; !(ullZahl % 2); ++n) {
        ullZahl /= 2;
    }
    p = _zwei_hoch(n+1) - 1;
    return ullZahl == p && isPrime(p);
}

Profil || Private Message || Suche

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

005
31.01.2003, 21:24 Uhr
Bruder Leif
dances with systems
(Operator)

Zitat:

~0xdeadbeef postete
Eine Zahl ist genau dann vollkommen, wenn sie der Form 2^n *(2^(n+1) - 1) mit n aus N und 2^(n+1) - 1 prim ist.

Vorsicht, da gibts zwei kleine Haken:

1. Ergebnisse aus der Zahlentheorie abzuleiten, ist eine Sache. Über ein Problem selbst nachzudenken, eine andere. Ich will Dir wirklich nicht zu nahe treten, aber ich glaube kaum, daß Du Dir "mal eben" Euklid's 36. Satz ausgedacht hast...

2. Der Satz ist in DER Form nicht so ganz richtig. Vorsicht: Subjunktion ist nicht gleich Bijunktion. Will sagen, es ist noch nicht bewiesen, daß eine Zahl, die dem Euklid'schen Test nicht standhält, grundsätzlich nicht vollkommen ist. Für Zahlen, mit denen ein heutiger PC umgehen kann, mag Deine Variante ausreichend sein, aber bei SEHR großen Zahlen kann es sein, daß sie eine vollkommene Zahl als "nicht vollkommen" zurückweist...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Dieser Post wurde am 31.01.2003 um 21:25 Uhr von Bruder Leif editiert.

Profil || Private Message || Suche

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

006
31.01.2003, 21:33 Uhr
Bruder Leif
dances with systems
(Operator)

Habs nochmal nachgelesen: Für GERADE Zahlen funktioniert Dein Algorithmus. Nur bei ungeraden wirds haarig...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

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

007
03.02.2003, 11:56 Uhr
~0xdeadbeef
Gast

Sofern es überhaupt ungerade vollkommene Zahlen gibt, sind diese größer als 10^300, und man versucht zu beweisen, dass es sie nicht gibt.

Profil || Private Message || Suche

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

008
15.02.2003, 19:39 Uhr
daniel

C++:

bool perfekt(unsigned int zahl)
{

    int x = 0;
    for(int i=1; i<zahl; i++)
    {
        if(zahl%i == 0)
        {
            x = x + i;
        }
        if(x>zahl)
        {
          return 0;
        }

    }

    if(x == zahl)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main()
{

    bool x = perfekt(y);
    if(x)
    {
        cout<<y<<" ist eine perfekte Zahl";
    }
    else
    {
        cout<<y<<" ist keine perfekte Zahl";
    }
    getchar();
    return 0;
}

funzt

--
Im uebrigen bin ich der Meinung, dass M$ zerstoert werden muesste.

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: