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