f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
Probieren Sie es online!
Ein anderer Versuch
Seitdem ich diese Herausforderung gepostet habe, habe ich versucht, eine rekursive Lösung für dieses Problem zu finden. Ich habe zwar nicht mehr als Stift und Papier verwendet, aber ich habe es geschafft, die Formel für Golf in ein praktisches Problem zu verwandeln - zumindest für bestimmte Definitionen des Praktischen -, was die Analyse erleichtert hat.
Stellen Sie sich eine Spielshow mit k + m Kandidaten vor, die wie folgt funktioniert.
In Runde 1 müssen alle Kandidaten eine bestimmte Aufgabe so schnell wie möglich erledigen. Die k Kandidaten, die die Aufgabe am schnellsten erfüllen, gewinnen jeweils 1 k $ (ein Kilodollar) und kommen in Runde 3.
In Runde 2 erhalten die m verbleibenden Kandidaten eine zweite Chance, sich dem anderen k anzuschließen . Jedem Kandidaten wird eine Frage gestellt. Wenn sie die Frage richtig beantworten, gewinnen sie 1 k $ und steigen in Runde 3 auf. Wenn sie die Frage jedoch nicht beantworten, werden sie aus dem Spiel ausgeschlossen. Das bedeutet, dass in Runde 3 zwischen k und k + m Kandidaten stehen, je nachdem, wie viele ihre Fragen beantworten können.
Runde 3 besteht aus m weiteren Wettbewerben, die Runde 1 ähneln. In jedem Wettbewerb müssen die Teilnehmer eine bestimmte Aufgabe erfüllen. Im Gegensatz zu Runde 1 erhält nur ein Kandidat einen Preis, aber alle Kandidaten können am nächsten Wettbewerb teilnehmen. Jeder Wettbewerb zahlt doppelt so viel wie der vorhergehende Wettbewerb; der erste zahlt 2 k $ und der letzte 2 m k $ .
Da es sich bei allen Preisen um Zweierpotenzen handelt, wissen wir, ob ein Kandidat die dritte Runde erreicht hat und welchen Wettbewerb er gewonnen hat, wenn er weiß, wie viel Preisgeld er verdient hat.
Angenommen, Sie sehen sich die Spielshow an und Runde 1 ist bereits vorbei. Sie wissen also, welche k Kandidaten bereits Runde 3 erreicht haben und welche m Kandidaten noch in Runde 2 stecken. Auf welche Weise kann das verbleibende Preisgeld verteilt werden?
Sobald wir wissen, welche der m Kandidaten der zweiten Runde die dritte Runde erreicht haben, ist es einfach, die möglichen Ergebnisse für dieses spezielle Szenario zu berechnen. Wenn j Kandidaten vorrücken, gibt es in Runde 3 k + j Gesamtkandidaten und somit k + j mögliche Ergebnisse für jeden Wettbewerb. Mit m Einzelwettbewerben in Runde 3 ergibt dies (k + j) m Ergebnisse für alle m Wettbewerbe.
Jetzt kann j einen beliebigen Wert zwischen 0 und m annehmen, abhängig davon, welche Kandidaten in Runde 2 richtig antworten. Für jeden festen Wert von j gibt es m C j verschiedene Kombinationen von j Kandidaten, die bis Runde 3 hätten vorrücken können. Wenn wir callen Die Gesamtzahl der möglichen Ergebnisse für k Kandidaten der dritten Runde und m Kandidaten der zweiten Runde g (m, k) ergibt die folgende Formel.
Wenn wir k = 1 festlegen , erhalten wir den folgenden Sonderfall, der unseren neuen Ansatz zur Lösung des ursprünglichen Problems darstellt.
Eine rekursive Formel
Nehmen wir nun an, dass Sie während der Werbespots nach Runde 1 und wachte gerade rechtzeitig , um zu sehen, der den letzten Wettbewerb der Runde 3 gewonnen und damit den großen Preis von einschlief 2 m k $ . Sie haben keine weiteren Informationen, auch nicht, wie viel Preisgeld der Kandidat insgesamt gewonnen hat. Auf wie viele Arten kann das verbleibende Preisgeld verteilt werden?
Wenn der Sieger einer der m Kandidaten der zweiten Runde war, müssen sie bereits in die dritte Runde aufgestiegen sein . Wir haben also effektiv k + 1 Kandidaten in Runde 3, aber nur m - 1 Kandidaten in Runde 2. Da wir den Gewinner des letzten Wettbewerbs kennen, gibt es nur m - 1 Wettbewerbe mit ungewissen Ergebnissen, also gibt es g (m - 1, k + 1) mögliche Ergebnisse.
Wenn der Gewinner einer der k Kandidaten ist, die Runde 2 übersprungen haben, wird die Berechnung etwas kniffliger. Nach wie vor gibt es nur noch m - 1 Runden, aber jetzt haben wir noch k Kandidaten in Runde 3 und m Kandidaten in Runde 2. Da die Anzahl der Kandidaten für Runde 2 und die Anzahl der Wettbewerbe für Runde 3 unterschiedlich sind, können die möglichen Ergebnisse nicht mit einem einfachen Aufruf von g berechnet werden . Doch nach dem erste Runde 2 Kandidat beantwortet hat - zu Recht oder zu Unrecht - die Anzahl der Runde 2 Kandidaten paßt erneut die m - 1 Runde 3 Wettbewerbe. Wenn der Kandidat weiterkommt, gibt es k + 1 Kandidaten der dritten Runde und somit g (m - 1, k + 1).mögliche Resultate; Wenn der Kandidat eliminiert wird, bleibt die Anzahl der Kandidaten der dritten Runde bei k und es gibt g (m - 1, k) mögliche Ergebnisse. Da der Kandidat entweder weiterkommt oder nicht, gibt es g (m - 1, k + 1) + g (m - 1, k) mögliche Ergebnisse, die diese beiden Fälle kombinieren.
Wenn wir nun die potenziellen Ergebnisse für alle k + m Kandidaten addieren, die den Hauptpreis hätten gewinnen können, muss das Ergebnis mit g (m, k) übereinstimmen . Es gibt m Kandidaten der zweiten Runde, die jeweils zu g (m - 1, k + 1) möglichen Ergebnissen führen, und k Kandidaten der dritten Runde, die zu g (m - 1, k + 1) + g (m - 1, k) führen. Einsen. Zusammenfassend erhalten wir die folgende Identität.
Zusammen mit dem Basiskoffer
Diese beiden Formeln charakterisieren die Funktion g vollständig.
Eine golferische Umsetzung
Während
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(49 Byte, 0**m
ergibt 1, wenn m auf 0 abfällt ) oder sogar
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(48 Bytes, gibt True statt 1 zurück ) wären gültige Lösungen, es sind noch Bytes zu speichern.
Wenn wir eine Funktion f definieren , die die Anzahl n der Kandidaten der ersten Runde anstelle der Anzahl m der Kandidaten der zweiten Runde als erstes Argument verwendet, dh
Wir erhalten die rekursive Formel
mit Grundkoffer
Endlich haben wir
so die Python-Implementierung
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
( k/n
ergibt 1 einmal n = k ) löst die vorliegende Aufgabe mit 1-basierter Indizierung.