Lottoprogramm

Hallo,

ihr werdet über meine Frage sicher lachen, aber mir bereitet sie einiges Kopfzerbrechen. In der Aufgabe soll nur ein kleines Konsolenprogramm in C geschrieben werden, welches eine einfache zufällige Ziehung 6 aus 49 (ähnlich Lotto) simuliert und die 6 gezogenen Zahlen sortiert ausgibt. Dabei soll die vorgegebene Funktion "unsigned int rand32()" benutzt werden, die zufällige Werte zwischen 0 und 32767 liefert. Soweit ist das noch kein Problem. Ich rufe für jede zu ziehende Zahl einfach (rand32()%49+1) auf. Die bereits gezogenen Zahlen merke ich mir in einem Array "int gezogen[6]" und schaue nach, ob die neue Zahl bereits gezogen wurde. Wenn ja, dann muss ich neu "würfeln". Das mache ich einfach so oft, bis ich 6 verschiedene Zahlen "gewürfelt" habe und sortiere diese dann mit qsort().
Nun kommt aber der Pferdefuß an dieser Aufgabe, denn die Funktion rand32 soll nur ein einziges Mal aufgerufen werden! Wie soll das gehen, ich brauche doch sechs Zahlen?! Ich muss also sechs Durchläufe machen und jedes Mal eine Zahl ziehen! Dazu brauche ich mindestens sechs Aufrufe von rand32! Kann es sein, dass die Aufgabe falsch gestellt ist, und gemeint wurde, dass rand32() für jede Zahl nur einmal aufgerufen werden darf? Aber was ist dann mit eventuell doppelten Ziehungen? Darf ich davon ausgehen, dass Doppel sehr selten vorkommen, und deswegen nicht zu berücksichtigen sind.

Zwei Dinge geben mir an dieser Aufgabe zu denken. Ich hatte sie in weniger als 10 Minuten gelöst und ein lauffähiges Programm geschrieben. Nur brauche ich im Schnitt etwas mehr als 6 Zufallszahlen pro Ziehung, das Ergebnis ist aber richtig.
Seltsamerweise bringt die Lösung aber mehr Punkte als deutlich schwerere Teilaufgaben??
Und was hat es mit diesem ominösen rand32() auf sich und weshalb soll ich nicht das normale rand() benutzen, das wir bisher immer verwendet haben??

Die Erklärung ist bestimmt ganz einfach, aber ich sehe den Wald vor lauter Bäumen nicht.

Entschuldigt bitte, dass ich die Frage hier im C++ stelle, wo es doch eigentlich nur um C geht. Aber hier scheint mehr los zu sein und C ist schliesslich vollständig in C++ enthalten.

jetzt schon danke,
Steffan

1.)

...ihr werdet über meine Frage sicher lachen, ...

Nö, warum?

2.)

Dabei soll die vorgegebene Funktion "unsigned int rand32()" benutzt werden, die zufällige Werte zwischen 0 und 32767 liefert.

Glaub ich Dir nicht, das Ding wird wohl Werte von 0 bis 4294967295 (2^32-1) liefern, denn sonst macht die Aufgabenstellung keinen Sinn.
So ganz nebenbei bemerkt, bei einer k aus n Ziehung gibt es n!/((n-k)!*k!) (also in Deinem Fall 13983816) Möglichkeiten - Die üblichen Windoof-Implementierungen arbeiten aber nur mit 15 Bit - Merkste was?

3.)

Ich rufe für jede zu ziehende Zahl einfach (rand32()%49+1) auf ...

Keine wirklich glückliche Lösung. Vergessen wir mal die Tatsache, dass bei vielen Implementierungen die unteren Bits alles andere als zufällig sind. Übel wird's dann auf jeden Fall, wenn sowohl N/M als auch N%M klein sind, wobei N=RAND_MAX und M der rechte Operand von Modulo ist.
Machen wir mal ein kleines konkretes Beispiel mit N=32 und M=31. Jede der Zahlen 0..31 ist gleich wahrscheinlich. Die zu erzeugenden Zahlen liegen in 0..30. Schauen uns wir dabei mal die Wahrscheinlichkeit speziell für die 0 und die Zahlen 1..30 an. Wenn man genau hinguckt, dann sieht man schnell, dass die 0 doppelt so wahrscheinlich wie jede andere Zahl aus 1..30 ist (selber überlegen warum) - Na prima!
Aber egal, in Deinem Fall ist's nicht so krass und diese Modulo-Pfriemelei kann als Notnagel herhalten.

4.)

... und schaue nach, ob die neue Zahl bereits gezogen wurde ...

Unfug! Die Ziehung soll eh sortiert ausgegeben werden, warum sollen wir nicht annehmen, dass die in der n-ten Ziehung gezogene Zahl kleiner als die aller nachfolgenden Zihungen ist. Beim Ziehen der Zahl muss man bedenken, dass nach hinten hin noch "genug Luft" für die nachfolgenden Ziehungen bleibt. Für die Ziehung m muss also gelten x(m-1)<x(m)<=(n-k+m), x(0)=-1, m=1..k
Damit haben wir zwar immer noch k mal den Aufruf von rand32(), aber wir ersparen uns die Sortiererei und haben garantiert keine Doppel.

5.)

Kann es sein, dass die Aufgabe falsch gestellt ist, und dass wirklich gemeint war, dass rand32() für jede Zahl nur einmal aufgerufen werden darf?

Tja, könnte sein, glaub ich aber nicht. Wenn ich mit meiner Vermutung aus 2.) Recht habe, dann geht es wirklich mit nur einer einzigen Zufallszahl!
Tip:
Versteh das Ding als eine besonders seltsame Art zu Zählen, mit Stellen zu unterschiedlicher Basis. Anders gesagt, versuche eine bijektive Abbildung der Zahlenmenge 0..(n!/((n-k)!*k!) - 1) auf die Menge der Kombinationen zu finden. Gewissermassen ein Abzählschema - Selber machen macht schlau!

6.)

Seltsamerweise bringt die Lösung aber mehr Punkte als deutlich schwerere*(???)* Teilaufgaben??

Wundert Dich das jetzt noch?

7.)

Und was hat es mit diesem ominösen rand32() auf sich und weshalb soll ich nicht das normale rand() benutzen, das wir bisher immer verwendet haben??

Siehe 2.)

8.)

... und C ist schliesslich vollständig in C++ enthalten ...

Aaaargh! NEIN, NEIN und nochmals NEIN! Die Unterschiede der anscheinend gemeinsamen Sets sind klein aber (sehr) gemein!

David_pb

Hi!

Die Funktion rand32() zählt, meines Wissens, garnicht zu der Standard Bibliothek von C. Und warum liefert diese Werte von 0 - 32767 und nicht von 0 - 2^32-1 ??? Sehr mysteriös!

grüße

Ganz genau so seh ich's auch, der Wertebereich ist garantiert (0..2^32-1) - Sonst macht's nämlich keinen Sinn
Aber er sagt ja auch, dass rand32() eine vorgegebene Funktion sei - Standard ist die natürlich nicht.
Mal gucken, wie lang er braucht, um auf das ziemlich verquere Abzählschema zu kommen, die Aufgabe ist wirklich ziemlich fies *g*