Tävlingsprogrammering/Uppgifter/Kängurumamman

Kängurumamman

En kängurumamma ska packa ner sina barn i sin pung. Hon har massor med barn. De två minsta väger bara ett gram var men sen väger varje barn lika mycket som de två föregående tillsammans. Hennes sex minsta barn väger alltså 1, 1, 2, 3, 5 och 8 gram. Mamman orkar bära högst X kilo (och inte ens ett gram mer). Hur många barn kan hon ta med sig?

Indatan består av en rad med ett heltal X, där 1≤X≤1000, det maximala antalet kilo mamman orkar bära. Programmet ska skriva en rad med ett heltal, det största antalet barn som tillsammans väger högst X kilo.

Lösning

Här fordras ingen effektiv lösning alls. Vikten på varje nytt barn räknas ut som summan av de två föregående och man fortsätter tills summan överstiger mammans kapacitet.

Den talföljd som kängurubarnens vikter följer kallas för Fibonaccis talföljd.

Lösning i Python:

from sys import stdin
X=int(stdin.readline())
W=[1,1]                      #Vikterna för de två första barnen
while(sum(W) <= X*1000):    #Så länge totalvikten är mindre än maxvikten...
   W.append(W[-1]+W[-2])   # ... så lägg till ett element i listan: summan av de två sista elementen.
print len(W)-1         #Vi har alltid lagt till ett barn för mycket så subtrahera ett.

Lösning i Haskell (av Anton Fors Hurdén):

f i b o n -- a c c i

        | n < 0         = o - 1
        | otherwise     = f b (i + b) (o + 1) (n - i)

main = readLn >>= print . f 1 1 0 . (1000*)