Askeleet

Tarkastellaan vielä edellisen tehtävän konetta. Montako eri tapaa on tuottaa luku $x$ koneen avulla?

Esimerkiksi kun $x=17$, tavat ovat seuraavat:

• $1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 14 \rightarrow 17$
• $1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17$
• $1 \rightarrow 2 \rightarrow 5 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17$
• $1 \rightarrow 4 \rightarrow 7 \rightarrow 14 \rightarrow 17$
• $1 \rightarrow 4 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17$

Tässä tapauksessa tapojen määrä on $5$.

Toteuta tiedostoon allsteps.py funktio count_steps, joka ilmoittaa, monellako tavalla luku $x$ voidaan tuottaa koneen avulla.

Funktion tulee toimia tehokkaasti, kun $x$ on välillä $1 \dots 1000$.

def count_steps(x):
    # TODO

if __name__ == "__main__":
    print(count_steps(1)) # 1
    print(count_steps(2)) # 1
    print(count_steps(3)) # 0
    print(count_steps(4)) # 2
    print(count_steps(5)) # 1
    print(count_steps(17)) # 5
    print(count_steps(42)) # 0
    print(count_steps(100)) # 242
    print(count_steps(1000)) # 2948311