Zufallenzahlen sollen nicht doppelt vorkommen
-
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 Lottozahlensrand(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 49while (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' stehenif (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;
}
-
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
ifund nicht alselse ifergibt 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
ifund nicht alselse ifergibt 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-adaIst 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.
-
Michael E. schrieb:
hustbaer schrieb:
Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.
Stimmt, er funktioniert gar nicht.
(...)
Soll das Ergebnisarray vielleicht sortiert sein?Ja, soll sortiert sein. Da mir der Algorithmus bekannt ist, hab ich die Beschreibung nicht all zu genau gelesen nachden ich erkannt habe was hier beschrieben wird. Ist mir nicht aufgefallen dass die Info fehlt.
-
David W schrieb:
Wieso wird über die Laufzeit geredet?
Weil hier Informatiker/Programmierer verkehren?
-
Reintun sortiere schrieb:
Wenn du auf einem Linux-System bist, ist das mit dem Compiler kein Problem.
Ich bin aber nicht auf nem Linux-System. Selbst wenn ich das wäre, was würde mir das bringen? Zu sehen, dass dein Programm manchmal funktioniert?
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.
Das hab ich selber vermutet, noch bevor jemand gesagt hat, dass das nötig ist
-
Ihr braucht gar nicht so lange Texte zu schreiben, SeppJ hatte vollkommen Recht.
DANKE
Meistens übersieht man (ich) ja so kleine Fehler
Thema beendet!
-
Als Beispiel ziehe ich mal aus 1 .. 6
Du hast 2 Mengen die dir bekannt sind.
1. Die Menge der insgesamt möglichen Zahlen
2. Die Menge der bereits gezogenen ZahlenDaraus ergibt sich 3. die Menge der aktuell noch möglichen Zahlen.
Wenn du die Mengen als Felder aufschreibst, hast du beispielweise
1. { 1, 2, 3, 4, 5, 6 }
2. { 1, 2, 4, 6 }
3. { 3, 5 }Jetzt kannst du die Felder übereinander legen:
{ 1, 2, 3, 4, 5, 6 } { 1, 2, X, 4, X, 6 } { X, X, 3, X, 5, X }Indizes der Mengen:
{ 1, 2, 3, 4, 5, 6 } { 1, 2, X, 3, X, 4 } { X, X, 1, X, 2, X }In dem Verfahren ziehst du jetzt zufällig einen der Indizes der noch verfügbaren Zahlen. Hier ist es eine 1 oder eine 2. Die Verteilung ist also wie bei jedem Zug aus dem Zufallsgenerator. Alle übrigen Zahlen sind möglich und werden mit gleicher Wahrscheinlichkeit gezogen.
Jetzt musst du nur noch den Index finden, den die Zufallszahl in der Menge der insgesamt möglichen Zahlen (1.) entspricht. Beim Ziehen einer 1 ist es die 3, beim Ziehen einer 2 die 5. Das sind genau die beiden noch fehlenden Zahlen. Und sie werden mit einer gleich verteilten Wahrscheinlichkeit gezogen. Dieses Verfahren funktioniert für beliebige Mengen 1 und 2, wobei Menge 2 natürlich Teilmenge aus 1 sein muss.
Du benötigst nur 2 Informationen pro Mengenelement: Einen Zahlenwert und ein Index. Den Zahlenwert speicherst du, der Index ergibt sich aus der Position in der Datenstruktur (oder einem Start- und Endwert wie 1 .. 49 im Beispielprogramm). Daher ist es auch wichtig die Datenstruktur sortiert zu halten. Der Index muss zur Zahl passen.
-
Mathe2107 schrieb:
Ihr braucht gar nicht so lange Texte zu schreiben, SeppJ hatte vollkommen Recht.
DANKE
Meistens übersieht man (ich) ja so kleine FehlerThema beendet!
Das was der sagte, hab ich schon am Anfang gesagt.
hustbaer schrieb:
David W schrieb:
Wieso wird über die Laufzeit geredet?
Weil hier Informatiker/Programmierer verkehren?
Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".
-
codetagger schrieb:
hustbaer schrieb:
David W schrieb:
Wieso wird über die Laufzeit geredet?
Weil hier Informatiker/Programmierer verkehren?
Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".
Wenn du meinst dass es wertlos ist sich Gedanken über theoretische Programmierprobleme zu machen, auch wenn man sie nicht gerade aktuell implementieren muss und/oder die aktuelle Problemgrösse so klein ist, dass es keinen Unterschied macht...
Den Rest kannst du dir vermutlich denken.
-
Reintun sortiere schrieb:
Als Beispiel ziehe ich mal aus 1 .. 6
Es ist lieb von dir, dass du dir so viel Mühe machst, aber seit ich rausgefunden habe, dass das Array sortiert sein soll, hab ich keine Probleme mit dem Algorithmus
Vielleicht hilfts ja jemand anderem.
-
hustbaer schrieb:
codetagger schrieb:
hustbaer schrieb:
David W schrieb:
Wieso wird über die Laufzeit geredet?
Weil hier Informatiker/Programmierer verkehren?
Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".
Wenn du meinst dass es wertlos ist sich Gedanken über theoretische Programmierprobleme zu machen, auch wenn man sie nicht gerade aktuell implementieren muss und/oder die aktuelle Problemgrösse so klein ist, dass es keinen Unterschied macht...
Den Rest kannst du dir vermutlich denken.Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.
-
codetagger schrieb:
Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.
Aber irgendjemand muß sich auch Gedanken darüber machen, wie man am allerbesten nicht wiederholende Zufallszahlen zieht und wie man am besten was sortiert und und und... Wie kommst Du drauf, dass das alles weniger "kompiliziert" sei als Softwaredesign und Architektur.
-
codetagger schrieb:
Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.
Ich sehe jetzt keinen grossen Vorteil darin, wenn das Design bzw. die Architektur gut ist, dafür aber die Implementierung Mist.
-
@codetagger: Man sollte als Informatiker schon in der Lage sein die beste Datenstruktur und den schnellsten Algorithmus für ein gegebenes Problem zu finden bzw. einzusetzen. Das hat noch nichts mit "premature optimization" zu tun. Wenn du dann hergehst und einen in O-Notation optimalen Algorithmus verschnellerst in dem du zwei Zeilen Assembler hier und eine unleserliche Umstellung anderswo verwendest um zwei Ticks in genau deinem Fall und sonst in keinem Fall einzusparen, dann befindest du dich dort. Wenn du aber statt O(n) einfach mal ein O(n^4) hinnimmst und das als "mini" bezeichnest...
MfG SideWinder
-
Jester schrieb:
codetagger schrieb:
Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.
Aber irgendjemand muß sich auch Gedanken darüber machen, wie man am allerbesten nicht wiederholende Zufallszahlen zieht und wie man am besten was sortiert und und und... Wie kommst Du drauf, dass das alles weniger "kompiliziert" sei als Softwaredesign und Architektur.
Weil es sogar hier im Forum Unmengen an Beiträge über das ziehen von solchen Zahlen gibt.
hustbaer schrieb:
codetagger schrieb:
Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.
Ich sehe jetzt keinen grossen Vorteil darin, wenn das Design bzw. die Architektur gut ist, dafür aber die Implementierung Mist.
Ne schlechte Implementierung läßt sich bei einer guten Architektur schnell austauschen, aber ne schlechte Architektur austauschen ist viel aufwendiger. Außerdem ist mir noch keiner begegnet, der gute Architektur designt, aber schlecht ziemlich implementiert, aber schon viele die nen schnellen Algo implementieren können, aber keine gute Architektur hinbekommen.
SideWinder schrieb:
@codetagger: Man sollte als Informatiker schon in der Lage sein die beste Datenstruktur und den schnellsten Algorithmus für ein gegebenes Problem zu finden bzw. einzusetzen. Das hat noch nichts mit "premature optimization" zu tun. Wenn du dann hergehst und einen in O-Notation optimalen Algorithmus verschnellerst in dem du zwei Zeilen Assembler hier und eine unleserliche Umstellung anderswo verwendest um zwei Ticks in genau deinem Fall und sonst in keinem Fall einzusparen, dann befindest du dich dort. Wenn du aber statt O(n) einfach mal ein O(n^4) hinnimmst und das als "mini" bezeichnest...
Ja, ja, ganz billiger Versuch mir die Worte im Mund umzudrehen oder bist wirklich so dumm den Zusammenhang zu verstehen. Ich habe dieses Lottospiel als "mini" bezeichnet, O(n^4) hast du gerade hergezaubert. Premature Optimization ist das Optimieren von Programmteilen die keinen messbaren Unterschied bringen. Und irgendwas mit Assembler besser an eine Hardware anzupassen, muss auch nicht immer Premature Optimization sein, wenn man es zum richtigen Zeitpunkt an der richtigen Stelle macht.
