Problem bei Errechnung merkwürdiger Zahlen



  • Das Mittel deiner Wahl in C++ wäre ein beliebiger Standardcontainer, z. B. std::vector. Warum das Ruby-Programm einen Hash-Container und kein Array benutzt, leuchtet mir nicht ein.

    Ob die Zahl als Teilsumme der Teiler darstellbar ist, überprüfst du, indem du alle Teilsummen in deinem Container speicherst.



  • Wie gesagt Container hatte ich noch nicht sondern es soll eine Übung zu Feldern (auch dynamisch) / Schleifen sein.

    Da ich ja nicht nur irgend ein Programm haben will, sondern es auch verstehen möchte, wäre ein Lösungsansatz auf der Basis nett.



  • Was meinst du mit Lösungsansatz? Wie das oben gepostete Programm vorgeht, hab ich doch schon gesagt. Welche Mittel du brauchen kannst auch. Was willst du noch? Was hast du denn bisher bewerkstelligt?



  • Also ich habe schon öfter begonnen, oben verstehe ich nicht wie zB beim 1. und 4. teiler Kombinationen geprüft werden (Also alle x-beliebigen Kombinationen). und eben das zwischenspeichern weil es eben unterschiedlich viele Teiler sind, wie ich das nur mit Feldern / Schleifen bewerkstelligen soll.
    Ich kann mich nochmal hinsetzen und den code soweitich komme erneut entwerfen, aber das hauptstück fehlt eben aus oben beschriebenen Gründen.



  • Beispielrechnung:
    n = 28

    subset_sums = { 0 }

    d = 1 teilt n => sums = { 0, 0+1 }
    d = 2 teilt n => sums = { 0, 0+1, 0+2, 0+1+2 }
    d = 3 teilt n nicht => sums bleibt
    d = 4 teilt n => sums = { 0, 1, 2, 0+4, 1+4, 2+4 }
    etc. pp.



  • Ich kann doch kein Ruby !
    Das ist ja mein Problem, ich verstehs nur in normalen C++



  • Hier ist ein altes Programm von mir für die Teilersumme

    unsigned teilersumme (unsigned x)
    {
       unsigned n = (unsigned)sqrt(x);
       unsigned i, sum=0;
       for (i=1; i<=n; i++)
       {
          if (x%i == 0)
          {
             sum += i;
             if (x/i != i)
                sum += x/i;
          }
       }
       return sum;
    }
    

    wenn Du die Teilersumme ohne die Zahl selbst willst, dann returniere sum-x.



  • Ok ich habe meinen Code jetzt insoweit nur mit Schleifen und Feldern fertig, das es mir die Teiler berrechnet, zwischenspeichert und die Zahlen auf vollkommenheit prüft: (Testweise nur alle Zahlen bis 100)

    #include <conio.h>
    #include <iostream.h>
    #include <iomanip.h>
    #include <math.h>
    
    int main() {
        int teiler[100],tanz=0,sum=0;
        for (int i = 0; i<100; i++) {
            teiler[i]=0;
            }
    
        for (int i = 1; i<101; i++) {
            cout<<i<<":  ";
            for (int j =1; j < i; j++) {
                if (i%j==0) {
                            cout<<setw(1)<<j<<"; ";
                            teiler[tanz]=j;
                            tanz=tanz+1;
                            sum=sum+j;
                            }
                } if (sum==i) cout<<" Vollkommen!!";
    
            sum=0;
                tanz=0;
                cout<<endl;
            }getch();
            getch();
    }
    

    So jetzt stellt sich mir die Frage wie ich am schnellsten alle möglichen Kombinationen nicht aller Teiler zum prüfen auf Pseudovollkommenheit teste. also Beispiel:
    4 Teiler

    Teiler
    1+2
    1+3
    1+4
    2+3
    2+4
    3+4
    1+2+3
    1+2+4
    1+3+4
    2+3+4
    

    Wie liese sich das für größere Teilermengen (relativ schnell) laufend realisieren (nachwievor nur Felder / Schleifen)
    Eine Möglichkeit die ich mir überlegt habe wäre das ganze mit

    randomize();
    for (i=0; i<999999; i++) {
    for (j=0; j<tanz; j++){
    sum=sum+teiler[random(tanz+1)]
    }
    if (i==sum) pseudovollkommen=1;
    }
    

    zu prüfen. aber das wäre sehr ungenau und langsam.
    Hoffe ihr habt ne bessere Idee, das Problem ist eben das man nicht nur alle Kombinationen aller Teiiler sondern auch nicht aller Teiler einbeziehen muss.

    mfG



  • n0sPh3r4tu schrieb:

    das Problem ist eben das man nicht nur alle Kombinationen aller Teiiler sondern auch nicht aller Teiler einbeziehen muss.

    Diesen Satz hätte ich gern nochmal von dir erklärt (mit einer so genauen Begründung, dass dir auffällt, dass du was falsch verstehst).



  • n0sPh3r4tu schrieb:

    Wie liese sich das für größere Teilermengen (relativ schnell) laufend realisieren (nachwievor nur Felder / Schleifen)
    Eine Möglichkeit die ich mir überlegt habe wäre das ganze mit

    randomize();
    for (i=0; i<999999; i++) {
    for (j=0; j<tanz; j++){
    sum=sum+teiler[random(tanz+1)]
    }
    if (i==sum) pseudovollkommen=1;
    }
    

    zu prüfen. aber das wäre sehr ungenau und langsam.

    Ja. Schau Dir nochmal das Sieb des Erathostenes an.
    Und mach aus
    feld[i]=true;
    ein
    feld[i]+=2;
    und am Ende lauf nochmal durch und ziehe bei allen Quadratzahlen einen Teiler ab.


Anmelden zum Antworten