Zufallenzahlen sollen nicht doppelt vorkommen



  • Antoras: Du verzerrst aber die Wahrscheinlichkeitsverteilung mit deinem Algorithmus.

    Angenommen im ersten Durchlauf ziehst du die Zahl x. Dann ist die Wahrscheinlichkeit für x+1 im nächsten Durchlauf nicht 1/(n-1), sondern 2/(n-1), da das Ergebnis "x+1" für die Ereignisse "x" und "x+1" geschrieben würde usw. Dadurch können Ketten entstehen, sodass deine tatsächliche Wahrscheinlichkeitsverteilung nicht mehr viel mit der Gleichverteilung zu tun hat.

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$


  • Mod

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee. Man muss die Methode zum Zahlenziehen bloß ein bisschen anpassen: Man erstellt ein Array der Größe k. Nun zieht man eine Zahl zwischen 1 und N und speichert sie im ersten Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl gleich der ersten Zahl, so nimmt man stattdessen N. Die Zahl speichert man in das zweite Feld. Als nächsten zieht man eine Zahl von 1 bis N-2. Ist die Zahl gleich einer der ersten gezogenen Zahl, nimmt man stattdessen N. Ist die Zahl gleich der zweiten gezogenen Zahl, nimmt man stattdessen N-1. Muster fortführen bis k Zahlen gezogen wurden.

    Dies hat eine Komplexität von k² Vergleichen, was gut sein kann, da k<N (aber es ist nicht zwangsläufig besser als Komplexität N des shuffles). Außerdem ist die Anzahl der Zufallszahlen gleich k und nicht wie beim shuffle N. Und die Zufallszahlzieherei ist im Vergleich zu Vergleichen 😉 eine teure Operation. Wieder ist k (möglicherweise deutlich) kleiner als N.



  • SeppJ schrieb:

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee.

    Das sollte eigentlich ne Komplexitätsschätzung für Antoras' Algorithmus sein. Denk dir einfach ein k statt nem n. Was würdest du denn sagen, was dieser Algorithmus für ne Komplexität hat?

    Man muss die Methode zum Zahlenziehen bloß ein bisschen anpassen: Man erstellt ein Array der Größe k. Nun zieht man eine Zahl zwischen 1 und N und speichert sie im ersten Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl gleich der ersten Zahl, so nimmt man stattdessen N. Die Zahl speichert man in das zweite Feld. Als nächsten zieht man eine Zahl von 1 bis N-2. Ist die Zahl gleich einer der ersten gezogenen Zahl, nimmt man stattdessen N. Ist die Zahl gleich der zweiten gezogenen Zahl, nimmt man stattdessen N-1. Muster fortführen bis k Zahlen gezogen wurden.

    Das ist ne coole Idee, auch wenn dadurch manche Kombinationen unmöglich werden. Aber ich denke, diese Bedenken kann man getrost vergessen, wenn man bedenkt, wie schlecht std::rand oftmals implementiert ist 😉

    Wenn k deutlich kleiner ist als n und ich nicht in garantierter Zeit die nächste Zahl liefern muss, würde ich wahrscheinlich einfach solange rand aufrufen, bis es mir ne Zahl liefert, die ich bisher noch nicht hatte.


  • Mod

    Michael E. schrieb:

    SeppJ schrieb:

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee.

    Das sollte eigentlich ne Komplexitätsschätzung für Antoras' Algorithmus sein. Denk dir einfach ein k statt nem n. Was würdest du denn sagen, was dieser Algorithmus für ne Komplexität hat?

    Ähnlich wie mein Vorschlag, da ist aber noch ein statistisches Element drin, dass ich zu dieser späten Stunde nicht analysieren mag. Worst-Case dürften aber k² Vergleiche sein. Und natürlich auch wieder k Zufallszahlen, was für kleine k deutlich teurer sein kann als die Vergleiche.

    Das ist ne coole Idee, auch wenn dadurch manche Kombinationen unmöglich werden. Aber ich denke, diese Bedenken kann man getrost vergessen, wenn man bedenkt, wie schlecht std::rand oftmals implementiert ist 😉

    Wenn k deutlich kleiner ist als n und ich nicht in garantierter Zeit die nächste Zahl liefern muss, würde ich wahrscheinlich einfach solange rand aufrufen, bis es mir ne Zahl liefert, die ich bisher noch nicht hatte.

    Och, den Anspruch habe ich aber, so etwas wenn überhaupt, dann perfekt zu machen*. Ein Lottoprogramm welches so arbeitet, würde ich mich ein bisschen für schämen. Und es ist natürlich auch ganz nützlich, sich über so etwas Gedanken zu machen, wenn man mal in die Bereiche k=N/2 kommt (bei k>N/2 kann man ja auch ziehen, welche Zahlen man nicht nimmt), damit der Algorithmus schnell terminiert.

    *: Das ist aber auch so eine Macke von mir. Ich bin viel zu perfektionistisch und verschwende deswegen viel zu viel Zeit.



  • Du kannst das Array in dem du die gezogenen Zahlen reinlegst auch sortiert halten. Dann brauchst du höchstens einmal über das Array iterieren. Eine Hälfte des Arrays um die einzufügende Position zu suchen und die neue Zahl einzufügen, die zweite um nach dem Einfügen die anderen Elemente nach hinten zu swappen.

    Du ziehst nach wie vor K-N (K die Gesamtanzahl der Elemente, N die bereits gezogenen), kannst dann aber nach dem Finden der richtigen Position den aktuellen Arrayindex aufaddieren. Du ziehst also praktisch aus der Anzahl der noch übrigen Elemente und überspringst dann diejenigen, die davor liegen. Vergiss nicht, auch zum Vergleichen den aktuellen Index aufzuaddieren!

    O(N) erreicht.



  • Vorweg: ich nenne die Anzahl der zu ziehenden Zahlen N und die grösse der Menge aus der gezogen wird M.
    (K und N wie Antoras in seinem Beitrag verwendet hat verwirrt mich hier zu sehr *g*)

    Also wir ziehe N=6 aus M=49.

    Random-Shuffle wurde erwähnt, Komplexität ist hier O(M). Bei grossen M also doof. Bei kleinen M ideal.

    @Michael E.:

    1. Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich. Weiss nicht wie du darauf kommst.
      Ist im Prinzip dasselbe wie wenn man einen Pot (z.B. std::vector) voll mit Zahlen von 1 bis M macht, und dann immer zufällig eine rausnimmt (=löscht). Das zerstört in keiner Weise irgendwas, das ist so zufällig wie es nur sein kann. Nur dass man sich das Erstellen des Pot und das Rausnehmen auch sparen kann, was die Sache bei grossen M deutlich schneller macht.
      Und was dabei rauskommt wenn man den Pot wegoptimiert hat Antoras beschrieben, ist nichts anderes.

    2. Die Komplexität des von Antoras beschriebenen Algorithmus ist O(N^2) wenn man ihn trivial implementiert:

    Man macht N Ziehungen.
    Bei jeder Ziehung muss man eine Zahl ermitteln und diese abspeichern. Das zählen wir als eine Operation (Zahl ermitteln sollte O(1) sein und Anhängen an einen std::vector/std::list/array/... ist O(1))
    Bei der 1. Ziehung kommt sonst nichts dazu.
    Bei der 2. Ziehung kommt ein Vergleich mit der ersten Zahl dazu, sowie möglicherweise ein Inkrement. Vergleich + Inkrement zählen wir auch als eine Operation. -> die 2. Ziehung braucht 2 Operationen.
    Bei der 3. Ziehung kommt 2x (Vergleich + Inkrement) dazu (sind ja schon 2 Zahlen in der Liste): 3 Operationen
    4. Ziehung: 4 Operationen
    ....
    N. Ziehung: N Operationen
    In Summe: 1+2+3+4+ ... +N Operationen, und das ist O(N^2).

    Das Ganze sollte sich optimieren lassen, wenn man statt eine einfachen Containers (wie std::vector) einen passenderen Container verwendet, so dass folgende Operationen in O(N log N) möglich sind:
    * Suchen einer Zahl im Container
    * Einfügen einer neuen Zahl
    * Ermitteln wie viele kleinere Zahlen im Container enthalten sind
    IMO müsste das mit den meisten Bäumen gehen (z.B. 2-3 Baum oder auch beliebige B-Bäume).
    (EDIT: wenn man den Algorithmus leicht modifiziert fällt die ist die letzte Anforderung an den Container, d.h. man kann gleich std::set oder ähnliches verwenden)

    Damit sollte der gesamte Algorithmus dann O(N log N) haben. Ich gehe davon aus dass das die bestmögliche Komplexität für den Fall M >> N ist.

    Das so für eine Hausaufgabe zu implementieren ist natürlich Overkill.

    @Antoras:

    Siehe oben.
    Der von dir beschriebene Algorithmus ist nicht O(N) sondern bestenfalls O(N log N), und so wie du ihn beschrieben hast sogar O(N^2).

    -----

    Zurück zum Thema.
    Wenn N=6 und M=49 feststehen würde ich ohne grösser zu überlegen eine von zwei (drei) Möglichkeiten wählen:

    * Wenn die Verwendung der Standard-Library etc. erlaubt ist: Random-Shuffle (M=49 ist definitiv ausreichend klein).

    * Wenn die Verwendung der Standard-Library nicht erlaubt ist, und man alles "zu Fuss" programmieren soll (und keine "Echtzeit" gefordert ist): Zahlen ziehen, merken, auf Duplikate checken und Duplikate verwerfen (neu ziehen). Die oben beschriebene Variante ist zwar in der Theorie besser, allerdings spielt das bei kleinen N, M keine Rolle. Und die "Verwerfen" Methode ist einfacher zu verstehen und einfacher zu implementieren. Natürlich ist dieser Algorithmus auch nicht deterministisch, spielt aber in der Praxis keine Rolle, da er immer ausreichend schnell terminiert. Mal vorausgesetzt dass der RNG kein kompletter Müll ist.

    Und wenn doch Echtzeit gefordert ist würde ich vermutlich die triviale Implementierung des von Antoras' beschriebenen Algorithmus implementieren. Eine O(N log N) wäre bei N = 6 ziemlich sicher langsamer, und ausserdem ... wen interessiert's für ne Hausaufgabe 🙂



  • Reintun sortiere schrieb:

    Du kannst das Array in dem du die gezogenen Zahlen reinlegst auch sortiert halten. Dann brauchst du höchstens einmal über das Array iterieren. Eine Hälfte des Arrays um die einzufügende Position zu suchen und die neue Zahl einzufügen, die zweite um nach dem Einfügen die anderen Elemente nach hinten zu swappen.

    Du ziehst nach wie vor K-N (K die Gesamtanzahl der Elemente, N die bereits gezogenen), kannst dann aber nach dem Finden der richtigen Position den aktuellen Arrayindex aufaddieren. Du ziehst also praktisch aus der Anzahl der noch übrigen Elemente und überspringst dann diejenigen, die davor liegen. Vergiss nicht, auch zum Vergleichen den aktuellen Index aufzuaddieren!

    O(N) erreicht.

    Nein, das ist genau so O(N^2).



  • Wieso wird über die Laufzeit geredet? Ist ein Shuffle halt teuer, ist doch egal.
    Bei dem echten Lotto wird auch ne Weile die Trommel gerührt 😃

    - Liste mit den Zahlen erstellen
    - User Sagt "Start"
    - Das Programm ruft so lange Shuffle auf bis der Benutzer auf "Stop" klickt
    - Zahl wird genommen (und aus der Liste entfernt) und wieder weiter geshufflet bis der User erneut auf Stop klickt...

    Wie beim echten Lotto.



  • Ah, ich habe gerade gesehen, dass Antoras das gleiche Verfahren schon erwähnt hatte. Das O(N) bezog ich auf das einmalige Ziehen einer Zahl mit N := Anzahl der bereits gezogenen Zahlen. Ich habe dazu noch ein Snippet herumliegen. Das Ziehen sieht dort so aus:

    procedure Random (This   : in out Generator;
                      Number :    out Integer) is
       use Number_Storage;
    
       Random_Number : Integer;
       Number_Count  : Natural := Natural(This.Stored_Numbers.Length);
    
       Cursor : Number_Storage.Cursor;
    begin
       Random_Number := Random_Integer (This.Random_Generator,
                                        This.First,
                                        This.Last - Number_Count);
    
       if Number_Count <= 0 then
          This.Stored_Numbers.Append (Random_Number);
          Number := Random_Number;
       elsif Random_Number + Number_Count > Element (This.Stored_Numbers.Last) then
          This.Stored_Numbers.Append (Random_Number + Number_Count);
          Number := Random_Number + Number_Count;
       else
          Cursor := This.Stored_Numbers.First;
          while Random_Number + To_Index (Cursor) >= Element (Cursor) loop
             Next (Cursor);
          end loop;
          Number := Random_Number + To_Index (Cursor);
          This.Stored_Numbers.Insert (Cursor, Random_Number + To_Index (Cursor));
       end if;
    end Random;
    


  • @hustbaer
    Danke für deine Erklärung. Ich hatte das ein bisschen missverständlich ausgedrückt - hätte gleich auf die zwei Parameter eingehen sollen und nicht nur auf einen.

    Wenn man eine einfache Lösung haben will, dann ist ein Shuffle mit Sicherheit die beste Wahl, ansonsten kann man sich den Algo ja echt mal angucken.



  • Hier gibt es einen älteren Thread zum Thema Würfeln:
    http://www.c-plusplus.net/forum/47483?highlight=w�rfel



  • hustbaer schrieb:

    Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

    Stimmt, er funktioniert gar nicht.

    Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

    Nun zieht man eine Zahl von 1 bis N-2.

    Angenommen, du ziehst eine 2.

    Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

    Nö, 2 < 3.

    Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

    Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

    Diese Zahl kommt nun ins dritte Feld.

    Also ist das Ergebnisarray [3, 2, 3].

    Soll das Ergebnisarray vielleicht sortiert sein?



  • ´@codetagger
    ich habe am anfang meines kompletten programms "int m=0" gesetzt... war vllt. ungünstig nur einen teil meines programms hier zu posten, aber das ist eben der teil der nicht funktioniert ...



  • erst einmal danke für die vielen beiträge... leider bin ich jetzt nicht schlauer als vorher.
    wie erwähnt bin ich c++ anfänger und weiß daher gar nicht, was Random-Shuffle und Komplexität in einem programm bewirken.

    außerdem wüsste ich gerne, was in MEINEM programmstück nicht richtig läuft, also meinen fehler finden und daraus lernen und nicht eine komplett andere idee benutzen. das ist ja nicht sinn der übung.
    (also nein, es ist keine prüfungsaufgabe, ich bin noch in meiner modulteilleistung)

    ich kann natürlich noch einmal mein ganzes programm posten, vllt. weiß ja dann jemand eher etwas... also:

    #include <iostream>
    #include <cstdlib>
    #include <ctime>

    using namespace std;
    int main ()
    {
    int z; // Zahlen von 1-49
    int n; // Laufvariable für n Speicherplätze
    int m;
    int l[6]; // Speicherplatz für 6 Lottozahlen

    srand(time(NULL)); // Zufallsgenerator initialisieren

    for (n=0; n<6; n=n+1)
    {
    l[n] = rand()%49 + 1; // 1 <= l <= 49 ~~> Lottozahlen im Bereich von 1 bis 49

    while (m<n)
    {
    if (l[n] != l[m])
    {m=m+1; continue;}
    else
    { l[n] = rand()%49 + 1;
    m = 0; continue;}
    }
    }

    for (z=1; z<50; z=z+1)
    { // Statt der Zufallszahl soll ein 'X' stehen

    if (z == l[0] || z == l[1] || z == l[2] || z == l[3] || z == l[4] || z == l[5])
    cout << " X ";
    else
    if (z<10) // Vor einstelligen Zahlen ein Leerzeichen
    cout << " " << z << " ";
    else
    cout << z << " ";

    if ((z%7)!=0) // Neue Zeile beginnen nach Zahl, die durch 7 teilbar ist
    ; // leerer Rumpf
    else
    cout << "\n";
    }

    return 0;
    }


  • Mod

    Erster Fehler: m wird vor Benutzung nicht initialisiert. Weiter habe ich jetzt nicht gelesen sondern bloß überflogen, aber dies sollte es sein.



  • @Michael E.
    Ich sehe gerade, dass ich vergessen habe zu erwähnen, dass die Zahlen geordnet sein müssen. Es reicht also nicht sie nur im nächsten Array-index abzuspeichern, das hab ich falsch erklärt.

    Weiterhin wird bei jedem Durchlauf immer nur die gezogene Zahl um eins hochgezählt, nicht die noch verfügbaren.

    Bsp mit 6 aus 49:

    1. Zahl = 7 (aus 49 verfügbaren):
    Zahl wird unverändert gespeichert.
    2. Zahl = 3 (aus 48 verfügbaren):
    Da sie kleiner als 1.Zahl ist wird sie auch unverändert gespeichert.
    3. Zahl = 6 (aus 47 verfügbaren):
    Sie ist größer als die erste Zahl, die 3, also wird sie um 1 erhöht. Nun haben wir eine 7 welche gleich der bereits gespeicherten 7 ist. Sie wird nochmals um 1 erhöht. Eine 8 wird abgespeichert.
    4. Zahl = 46 (aus 46 verfügbaren):
    Sie ist größer als alle anderen Zahlen, also wird 4 addiert. Eine 49 wird abgespeichert.
    5. Zahl = 1 (aus 45 verfügbaren):
    Sie ist kleiner als alle anderen Zahlen. Also wird sie unverändert abgespeichert.
    6. Zahl = 6 (aus 44 verfügbaren):
    Sie ist größer als die 3. Eins wird addiert. Nun ist sie gleich der nächsten Zahl, der 7. Es wird nochmal 1 addiert. Die neue Zahl ist gleich der 8 also wird nochmal 1 addiert und eine 9 abgespeichert.

    Ergebnis: 1,3,6,7,8,49
    Alle Zahlen bleiben verfügbar. Und die Wahrscheinlichkeitsverteilung ändert sich auch nicht. Wichtig ist wirklich nur, dass die Zahlen geordnet abgespeichert werden.



  • Michael E. schrieb:

    hustbaer schrieb:

    Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

    Stimmt, er funktioniert gar nicht.

    Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

    Nun zieht man eine Zahl von 1 bis N-2.

    Angenommen, du ziehst eine 2.

    Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

    Nö, 2 < 3.

    Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

    Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

    Diese Zahl kommt nun ins dritte Feld.

    Also ist das Ergebnisarray [3, 2, 3].

    Soll das Ergebnisarray vielleicht sortiert sein?

    Es funktioniert definitv. Probier es doch aus:

    -- random_x_of_y.ads
    with Ada.Numerics.Float_Random; use Ada.Numerics;
    with Ada.Containers.Vectors; use Ada.Containers;
    
    package Random_X_Of_Y is
    
       package Number_Storage is new Vectors (Index_Type   => Natural,
                                              Element_Type => Integer);
    
       type Generator is limited private;
    
       procedure Reset (This : in out Generator; First, Last : in Integer);
    
       procedure Random (This   : in out Generator;
                         Number :    out Integer);
    private
       type Generator is record
          Random_Generator : Float_Random.Generator;
          Stored_Numbers : Number_Storage.Vector;
          First : Integer;
          Last  : Integer;
       end record;
    end Random_X_Of_Y;
    
    -- random_x_of_y.adb
    package body Random_X_Of_Y is
       ----------------------------------------------------------------------------
       procedure Reset (This : in out Generator; First, Last : in Integer) is
       begin
          This.First := First;
          This.Last  := Last;
          Float_Random.Reset (This.Random_Generator);
          Number_Storage.Set_Length (This.Stored_Numbers, 0);
       end Reset;
       ----------------------------------------------------------------------------
       function Random_Integer (G         : Float_Random.Generator; 
                                Low, High : Integer) return Integer is
          M : Integer := High - Low + 1;
       begin      
          return Low + (Integer(Float(M) * Float_Random.Random(G)) mod M);
       end Random_Integer;
       ----------------------------------------------------------------------------
       procedure Random (This   : in out Generator;
                         Number :    out Integer) is
          use Number_Storage;
    
          Random_Number : Integer;
          Number_Count  : Natural := Natural(This.Stored_Numbers.Length);
    
          Cursor : Number_Storage.Cursor;
       begin
          Random_Number := Random_Integer (This.Random_Generator,
                                           This.First,
                                           This.Last - Number_Count);
    
          if Number_Count <= 0 then
             This.Stored_Numbers.Append (Random_Number);
             Number := Random_Number;
          elsif Random_Number + Number_Count > Element (This.Stored_Numbers.Last) then
             This.Stored_Numbers.Append (Random_Number + Number_Count);
             Number := Random_Number + Number_Count;
          else
             Cursor := This.Stored_Numbers.First;
             while Random_Number + To_Index (Cursor) >= Element (Cursor) loop
                Next (Cursor);
             end loop;
             Number := Random_Number + To_Index (Cursor);
             This.Stored_Numbers.Insert (Cursor, Random_Number + To_Index (Cursor));
          end if;
       end Random;
       ----------------------------------------------------------------------------
    end Random_X_Of_Y;
    

    Und zum Testen:

    -- lotto.adb
    with Ada.Text_IO; use Ada.Text_IO;
    with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
    
    with Random_X_Of_Y;
    
    procedure Lotto is
       subtype Lotto_Type is Natural range 1 .. 49;
    
       Generator : Random_X_Of_Y.Generator;
       Number    : Lotto_Type;
    begin
       Random_X_Of_Y.Reset (Generator, Lotto_Type'First, Lotto_Type'Last);
       for I in 1 .. 6 loop
          Random_X_Of_Y.Random (Generator, Number);
          Put (Integer(Number));
          New_Line;
       end loop;
    end Lotto;
    

    Zum besseren Testen kannst du auch mal 6 aus 6 ziehen.

    Angenommen du ziehst 6 aus 1..6 und hast 1, 2 und 4 bereits gezogen. Dann ziehst du nur aus 0..2 und der Inhalt des Arrays der gezogenen Zahlen sieht so aus:
    (1, 2, 4)

    Dieser Inhalt beschreibt praktisch die Positionen in einem Array für eine Maske, die du dann für die restlichen 3 Zahlen verwendest:
    (-, -, 1, -, 2, 3)

    Ziehst du eine 1, dann vergleichst du die 1 mit der Zahl an Position 0. 0 + 1 ist größer gleich der 1 im ersten Feld, also vergleichst du mit dem nächsten Feld an Index 1. 1 + 1 ist größer gleich der 2 an Position 1, also vergleichst du mit dem dritten Feld an Index 2. dort steht eine 4 drin. 1 + 2 ist nicht größer gleich dieser 4, dein neues Ergebnis ist also 1 + 2 = 3. Dieses Ergebnis sortierst du jetzt ein:
    ( 1, 2, 3, 4)



  • Reintun sortiere schrieb:

    Michael E. schrieb:

    hustbaer schrieb:

    Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

    Stimmt, er funktioniert gar nicht.

    Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

    Nun zieht man eine Zahl von 1 bis N-2.

    Angenommen, du ziehst eine 2.

    Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

    Nö, 2 < 3.

    Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

    Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

    Diese Zahl kommt nun ins dritte Feld.

    Also ist das Ergebnisarray [3, 2, 3].

    Soll das Ergebnisarray vielleicht sortiert sein?

    Es funktioniert definitv.

    Dann wäre es nett, mir zu sagen, was ich bei meinem Beispiel falsch gemacht haben soll, statt mir 100 Zeilen Code hinzuknallen in einer Sprache, für die ich nicht mal nen Compiler hab, sodass das Ausprobieren etwas schwierig wird 🙄



  • Reintun sortiere schrieb:

    Es funktioniert definitv. Probier es doch aus:

    Nein, so wie es beschrieben wurde,funktioniert es offenbar nicht:

    007EF6C9  mov         dword ptr [ebp-8Ch],eax 
    007EF6CF  mov         edx,dword ptr [ebp-8Ch] 
    007EF6D5  mov         dword ptr [ebp-5Ch],edx 
    007EF6D8  mov         dword ptr [ebp-4],4 
    007EF6DF  mov         eax,dword ptr [ebp-34h] 
    007EF6E2  or          eax,2 
    007EF6E5  mov         dword ptr [ebp-34h],eax 
    007EF6E8  mov         ecx,dword ptr [ebp-5Ch] 
    007EF6EB  mov         edx,dword ptr [ecx] 
    007EF6ED  mov         dword ptr [ebp-54h],edx 
    007EF6F0  mov         eax,dword ptr [ebp-54h] 
    007EF6F3  mov         dword ptr [ebp-50h],eax 
    007EF6F6  mov         ecx,dword ptr [ebp-5Ch] 
    007EF6F9  mov         edx,dword ptr [ecx] 
    007EF6FB  mov         eax,dword ptr [edx-8] 
    007EF6FE  mov         dword ptr [ebp-58h],eax 
    007EF701  mov         ecx,dword ptr [ebp-58h] 
    007EF704  mov         dword ptr [ebp-4Ch],ecx
    


  • Mathe2107 schrieb:

    erst einmal danke für die vielen beiträge... leider bin ich jetzt nicht schlauer als vorher.
    wie erwähnt bin ich c++ anfänger und weiß daher gar nicht, was Random-Shuffle und Komplexität in einem programm bewirken.

    außerdem wüsste ich gerne, was in MEINEM programmstück nicht richtig läuft, also meinen fehler finden und daraus lernen und nicht eine komplett andere idee benutzen. das ist ja nicht sinn der übung.
    (also nein, es ist keine prüfungsaufgabe, ich bin noch in meiner modulteilleistung)

    Mit Komplexität brauchst du dich erstmal nicht beschäftigen. Random-Schuffle ist eine Funktion, die die Elemente einer Datenstruktur zufällig durcheinanderwürfelt.

    Nutze bitte die Code-Tags des Forums, dann kann man deinen Quelltext auch besser lesen.

    Bevor du aber das Programm schreibst, wäre es gut sich ein funktionierendes Verfahren zu überlegen und erst einmal darüber zu reden.

    Dann wäre es nett, mit zu sagen, was ich bei meinem Beispiel falsch gemacht haben soll, statt mir 100 Zeilen Code hinzuknallen in einer Sprache, für die ich nicht mal nen Compiler hab, sodass das Ausprobieren etwas schwierig wird 🙄

    Wenn du auf einem Linux-System bist, ist das mit dem Compiler kein Problem.

    zypper install gcc-ada
    gnatmake lotto.adb
    zypper remove gcc-ada
    

    Ist sogar einfacher, als wenn das in C oder C++ geschrieben und der Compiler bereits installiert wäre. 🙂

    Was an deinem Beispiel falsch ist, hat Antoras ja schon gesagt: Du musst die neu gezogene Zahl an der richtigen Stelle einfügen, damit das Array immer sortiert bleibt.


Anmelden zum Antworten