Consider again the machine of the preceding task. How many different ways there are to produce a number ?
For example, can be produced in the following ways:
In this case, the answer is .
In a file allsteps.py
, implement the function count_steps
that returns the number of ways to produce the number .
The function should be efficient when is in the range .
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