Problem bei Errechnung merkwürdiger Zahlen



  • Ich bin gerade dabei Programmieren zur lernen, bin in C++ jetz ein stück über Felder, Prototyping, Arrays usw. hinaus, eine "schwere" Aufgabe, zur Prüfung dieser Themen soll ein Programm zur überprüfung ob eine Zahl abdundant, Pseudovollkommen, oder Merkwürdig ist sein. Ich bekomme hier aber nichts laufendes Zustande 😞 Wäre nett wenn mir jemand helfen könnte.
    Meine bisjetzigen Codes geben nicht viel her, da ich noch keine gute Idee habe wie ich Beispielsweise die unterschiedliche Anzahl an Teilern ( je nach Zahl) abspeichere und zurückgebe.

    Ich habe im Netz einen Quellcode hierzu in einer andren Spreache gefunden:

    #!/usr/bin/ruby

    # Break early version, checking if a number is weird
    def weird_number(n)
    sum = 0
    subset_sums = Hash.new
    subset_sums[0] = true
    for d in 1...n
    next unless n % d == 0
    # Calculate sum of all divisors
    sum += d
    # Calculate sums for all subsets
    subset_sums.keys.each do | s |
    return false if s + d == n
    subset_sums[s + d] = true
    end
    end
    sum > n
    end

    def weird_numbers(range)
    range.select { | n | weird_number(n) }
    end

    # Argument parsing
    raise "Input exactly one number" unless ARGV.length == 1

    max = ARGV[0].to_i

    # Call it
    puts weird_numbers(1..max)

    Würde mir denke ich zum Verständniss sogar schon reicehn wenn mir den jmd. in D++ übersetzen könnte.

    PS: Werr etwas mehr Zeit hat mir das zu erklären könnte sich über ICQ 452810 melden. danke.

    mfG



  • Dieser Thread wurde von Moderator/in Christoph aus dem Forum Mathematik und Physik in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Das Programm geht etwa folgendermaßen vor, um zu testen, ob eine Zahl n merkwürdig ist:

    subset_sums ist eine Ansammlung von allen Teilsummen der bisher gefundenen Teiler. Im anfänglichen Zustand ist nur die 0 in subset_sums.

    Man setzt d = 1, ..., n - 1. Wenn d ein Teiler von n ist, dann wird x + d in subset_sums gespeichert für alle x, die schon in subset_sums drin waren. Somit aktualisiert man subset_sums. Wenn x + d == n ist, ist n perfekt und nicht merkwürdig. Wenn dies aber bis zum Ende nicht passiert und die Summe aller Teiler größer ist als n, ist n merkwürdig.

    Das in C++ umzuschreiben, wäre ungefähr genauso viel Arbeit, wie es neu zu schreiben 😉



  • Ich brauche ja auch keine Volle Übersetzung, sondern, eher einen Ablaufplan für das Programm, mein größtes Problem ist wiegesagt, wie ich die unterschiedliche Anzahl an echten Teilern zwischenspeichere und wie ich teste ob die Zahl durch eine beliebige Kombination der Teiler ausdrückbar ist.
    mfG



  • 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.


Log in to reply