Question

有12根筷子,一次取1根或者2根,有多少种不同的取法?

Answer 1

用递归算法。规模不大，可以手工计算。

12根筷子为起点倒推。问题可以变成，11根的取法（+1根），10根的取法（+2根）。

11根筷子为起点倒推。问题可以变成，10根的取法（+1根），9根的取法（+2根）。

归纳一下，n根取法的方案数 f(n)=f(n-1)+f(n-2)。

也就是n根取法的方案数是(n-1)根、(n-2)根方案数量的和。

再看最小方案，1根的取法只有1种，2根的取法有2种（1+1，2）。

因此，列表计算。

根数    取法方案数    

1 ； 1

2 ； 2

3 ； 3

4 ； 5

5 ； 8

6 ； 13

7 ； 21

8 ； 34

9 ； 55

10 ； 89

11 ； 144

12    ；    233    

因此，一共有 233 种取法。

附：编程计算的结果以及程序代码