Question 1. Suppose there are n steps in a stair. Each time you can only take one or two steps. The relationship between n and the number of ways to go upstairs is shown in the following table. Calculate how many ways to go upstairs by using by writing:

a recursion program: int JUMP_R(int n);

a dynamic programming program: int JUMP_DP (int n).

Steps: n	Formula	Number
1	F(1)=1	1
2	F(2)=2	2
3	F(3)=F(1)+F(2)	3
4	F(3)=F(2)+F(3)	5
n	F(n)=F(n-2)+F(n-1)

Question 2. Implement the following program to solve the Hanoi tower problem by moving the plates from pillar a to pillar b with the help of pillar c. Draw the moving process for n=3.

void Hanoi(int n, int a, int b, int c)

{

if (n==1)

____________________;

else{

Hanoi(n-1, a, c, b);

Move(n, a, b);

____________________;

}

}