diff options
Diffstat (limited to 'buffet_lotterie.md')
| -rw-r--r-- | buffet_lotterie.md | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/buffet_lotterie.md b/buffet_lotterie.md new file mode 100644 index 0000000..8a125c0 --- /dev/null +++ b/buffet_lotterie.md @@ -0,0 +1,63 @@ +Buffet-Lotterie +=============== + +Das Programm besteht aus der Funktion `denke(Anzahl_Teilnehmer, Silben_als_Liste)`, die die Lösung auf der Konsole ausgibt. + +Gedanken dazu +------------- + +* Es ist egal, wer welche Silbe sagt. Wichtig ist nur, wer die letzte spricht und wie oft das Geburtstagskind die Möglichkeit hat, zwei zu sprechen. +* Es ist - für das Geburtstagskind - egal, in welcher Reihenfolge es Eine und Zwei Silben spricht, solange die Anzahl an Zweisilbern insgesamt gleich bleibt, denn +* Es ist von Anfang an klar, nach wie vielen Runden das Geburtstagskind drankommt und wie viele Silben es spricht. Bei der gleichen Anzahl an Silben und Start-Teilnehmern ist die Anzahl an Runden, die das Geburtstagskind braucht, um zum Essen zu kommen konstant. + +Lösung +------ + +Nach langem Nachdenken ergaben sich die Formeln +``` +e = floor((len(silben) + offset) / teilnehmer) +offset = ((len(silben) + offset - 1) % teilnehmer) % (teilnehmer - 1) +``` +wobei `e` die Anzahl Runden darstellt, die das Geburtstagskind eine Silbe sagen durfte, bis jemand zum Essen ging und +`offset` - mit dem Startwert 0 - die Nummer des Teilnehmers, der als nächstes anfangt hat. +Um dann noch auszurechnen, wie weit diese Teilnehmernummer `offset` vom Geburtstagskind entfernt ist, kann man +``` +fehlt_noch = (offset - 1) % (teilnehmer - 1) + 1 +``` +benutzen. +Diese Berechnungen werden in einer Schleife durchgeführt. Um zu berechnen, wie oft das Geburtstagskind optimalerweise zwei Silben sagen muss, ist es nötig, die Gesamtzahl an `e`s zu behalten. Das geschieht in `einfluss`. +Jedes Mal, nachdem ein Teilnehmer in der Rechnung die Runde verlässt, wird geprüft, ob der `einfluss` groß genug ist, um die Lücke `fehlt_noch` auszugleichen. Wenn ja, ist die Aufgabe gelöst und das Geburtstagskind kann `fehlt_noch`-mal zwei Silben nennen und früher Essen gehen. +Die Lösung wird durch Zustands-Nachrichten verständlicher gemacht. + +Beispiele +--------- + +6 Teilnehmer mit "Informatik kann uns..." +``` +>>> import buffet_lotterie +>>> buffet_lotterie.denke(6, ['In', 'for', 'ma', 'tik', 'kann', 'uns', 'wei', 'sen', 'wer', 'als', 'Nächs', 'ter', 'kommt', 'zum', 'Spei', 'sen']) +Nach 2 Runden fängt der 4. an. Es sind dann noch 5 Teilnehmer im Spiel. +Es fehlten 3 bis zum Geburtstagskind +Nach 3 Runden fängt der 4. an. Es sind dann noch 4 Teilnehmer im Spiel. +Es fehlten 3 bis zum Geburtstagskind +Das Geburtstagskind muss erst 3-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist. +``` + +28 Teilnehmer, wie in der Aufgabe +``` +>>> buffet_lotterie.denke(28, ['In', 'for', 'ma', 'tik', 'kann', 'uns', 'wei', 'sen', 'wer', 'als', 'Nächs', 'ter', 'kommt', 'zum', 'Spei', 'sen']) +Nach 0 Runden fängt der 16. an. Es sind dann noch 27 Teilnehmer im Spiel. +Nach 1 Runden fängt der 4. an. Es sind dann noch 26 Teilnehmer im Spiel. +Es fehlten 3 bis zum Geburtstagskind +Nach 0 Runden fängt der 19. an. Es sind dann noch 25 Teilnehmer im Spiel. +Nach 1 Runden fängt der 9. an. Es sind dann noch 24 Teilnehmer im Spiel. +Es fehlten 8 bis zum Geburtstagskind +Nach 1 Runden fängt der 1. an. Es sind dann noch 23 Teilnehmer im Spiel. +Es fehlten 23 bis zum Geburtstagskind +Nach 0 Runden fängt der 16. an. Es sind dann noch 22 Teilnehmer im Spiel. +Nach 1 Runden fängt der 9. an. Es sind dann noch 21 Teilnehmer im Spiel. +Es fehlten 8 bis zum Geburtstagskind +Nach 1 Runden fängt der 3. an. Es sind dann noch 20 Teilnehmer im Spiel. +Es fehlten 2 bis zum Geburtstagskind +Das Geburtstagskind muss erst 2-mal 'zwei Silben' und dann nur noch 'eine Silbe' sagen, bis es dran ist. +``` |