申論題

8. (20%) Finish a recursive function for solving a jumping Takahashi problem. Assuming that Takahashi is standing at coordinate 0 on a number line. He will now perform 4 jumps forward towards the positive direction. At each jump, he can take a stride of either 2 or 5 steps forward on the line. For example, after the first jump, he can reach coordinates {2, 5}.

(d) What is the lowest computational complexity one can possibly achieve for this problem? (You can get the score as long as you give the right order. After the examination, it could be a fun exercise if you try to achieve this lowest computation complexity by modifying the program only slightly. The run time will make a big difference when you jump for 100 steps) (5%)