f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
Wypróbuj online!
Inne podejście
Od kiedy opublikowałem to wyzwanie, starałem się znaleźć rekurencyjne rozwiązanie tego problemu. Chociaż nie udało mi się użyć wyłącznie długopisu i papieru, udało mi się przekształcić formułę w golfa w praktyczny problem - przynajmniej w przypadku niektórych definicji praktycznych - co ułatwiło analizę.
Wyobraź sobie teleturniej za pomocą k + m kandydatami na który działa w następujący sposób.
W rundzie 1 wszyscy kandydaci muszą wykonać określone zadanie tak szybko, jak to możliwe. Do k kandydatów, które realizują zadania najszybszym wygrać 1 k $ (jeden kilodollar) każda i przejść do 3 rundzie.
W drugiej rundzie m pozostałych kandydatów otrzymuje drugą szansę na dołączenie do drugiego k . Każdemu kandydatowi zadawane jest pytanie. Jeśli odpowiedzą poprawnie na pytanie, wygrają 1 tys. $ I przejdą do rundy 3. Jeśli jednak nie odpowiedzą na pytanie, zostaną wyeliminowani z gry. Oznacza to, że runda 3 będzie miała wartość od k do k + m kandydatów, w zależności od liczby osób, które odpowiedzą na ich pytania.
Runda składa się z 3 m więcej konkursów, które są podobne do okrągły 1. W każdym konkursie, uczestnicy mają do wykonania określonego zadania. W przeciwieństwie do pierwszej rundy tylko jeden kandydat otrzymuje nagrodę, ale wszyscy kandydaci mogą wziąć udział w następnym konkursie. Każdy konkurs płaci dwa razy więcej niż konkurs przed nim; pierwszy płaci 2 tys. $, a ostatni 2 mln $ .
Zauważ, że ponieważ wszystkie nagrody są potęgami dwóch, wiedza o tym, ile wygranych wygrał kandydat, oznacza, że wiemy, czy awansowali do trzeciej rundy i który z konkursów w trzeciej rundzie wygrał.
Załóżmy, że oglądasz teleturniej, a runda 1 już się zakończyła, więc wiesz, którzy k kandydaci osiągnęli już rundę 3, a którzy m utknęli w rundzie 2. Na ile sposobów można rozdzielić pozostałe nagrody pieniężne?
Raz wiemy, który z drugiej turze za m kandydatów awansowały do rundy 3, to łatwo obliczyć ewentualne skutki dla tego konkretnego scenariusza. Jeśli j kandydatów awansuje, w rundzie 3 jest łącznie k + j kandydatów, a tym samym k + j możliwych wyników dla każdego konkursu. Przy m pojedynczych konkursach w rundzie 3 daje to (k + j) m wyników dla wszystkich m zawodów.
Teraz j może przyjąć dowolną wartość od 0 do m , w zależności od tego, którzy kandydaci odpowiadają poprawnie w rundzie 2. Dla każdej stałej wartości j istnieją m C j różne kombinacje j kandydatów, które mogłyby przejść do rundy 3. Jeśli zadzwonimy całkowitą liczbę możliwych wyników dla k 3 kandydatów rundy i m 2 kandydatów rundy g (m, k) otrzymujemy następującą formułę.
Jeśli naprawimy k = 1 , otrzymamy następujący specjalny przypadek, który stanowi nasze nowe podejście do rozwiązania pierwotnego problemu.
Formuła rekurencyjna
Załóżmy teraz, że zasnąłeś podczas reklam po pierwszej rundzie i obudziłeś się w samą porę, aby zobaczyć, kto wygrał ostatni konkurs w rundzie 3, a tym samym główną nagrodę w wysokości 2 mln k $ . Nie masz żadnych innych informacji, a nawet łącznej kwoty nagród wygranych przez kandydata. Na ile sposobów można rozdzielić pozostałe nagrody pieniężne?
Jeśli zwycięzca był jednym z m kandydatów drugiej rundy, już teraz musieliśmy awansować do trzeciej rundy . Zatem efektywnie mamy k + 1 kandydatów w rundzie 3, ale tylko m - 1 kandydatów w rundzie 2. Ponieważ znamy zwycięzcę ostatniego konkursu, jest tylko m - 1 konkursów z niepewnymi wynikami, więc jest g (m - 1, k + 1) możliwe wyniki.
Jeśli zwycięzcą jest jeden z k kandydatów, którzy pominęli rundę 2, obliczenia stają się nieco trudniejsze. Jak poprzednio, pozostało tylko m - 1 rund, ale teraz nadal mamy k kandydatów w rundzie 3 i m kandydatów w rundzie 2. Ponieważ liczba kandydatów w rundzie 2 i liczba konkursów w rundzie 3 są różne, możliwe wyniki nie mogą oblicza się za pomocą zwykłego wywołania g . Jednak po tym, jak kandydat z pierwszej rundy 2 odpowiedział - słusznie lub niesłusznie - liczba kandydatów z drugiej rundy ponownie odpowiada m-1 konkursom z 3 rundy. Jeśli kandydat awansuje, jest k + 1 runda 3 kandydatów i tym samym g (m - 1, k + 1)możliwe rezultaty; jeśli kandydat zostanie wyeliminowany, liczba rund 3 kandydatów pozostaje na poziomie k, a możliwe są g (m - 1, k) wyniki. Ponieważ kandydat albo posuwa się naprzód, albo nie, istnieje g (m - 1, k + 1) + g (m - 1, k) możliwe wyniki łączące te dwa przypadki.
Teraz, jeśli dodamy potencjalne wyniki dla wszystkich kandydatów k + m, którzy mogliby wygrać nagrodę główną, wynik musi być zgodny g (m, k) . Jest m 2 zawodników z 2 rundy, które prowadzą do potencjalnych wyników g (m - 1, k + 1) , oraz k 3 zawodników z rundy, które prowadzą do g (m - 1, k + 1) + g (m - 1, k) te. Podsumowując, otrzymujemy następującą tożsamość.
Wraz z podstawą
te dwie formuły całkowicie charakteryzują funkcję g .
Implementacja golfa
Podczas
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(49 bajtów, 0**m
daje 1 raz m spada do 0 ) lub nawet
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)
(48 bajtów, zwraca True zamiast 1 ) byłyby poprawnymi rozwiązaniami, wciąż są bajty do zapisania.
Jeśli zdefiniujemy funkcję f, która jako pierwszy argument przyjmuje liczbę n kandydatów z 1. rundy zamiast liczby m kandydatów z 2. rundy, tj.
otrzymujemy rekurencyjną formułę
z podstawą
Wreszcie mamy
więc implementacja Pythona
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
( k/n
daje 1 raz n = k ) rozwiązuje bieżące zadanie za pomocą indeksowania 1.