1.假设一个人的头发不超过30000根,某城市有50000人,那么这个城市中至少有多少人的头发根数相同?

1.假设一个人的头发不超过30000根,某城市有50000人,那么这个城市中至少有多少人的头发根数相同?

2.有一段楼梯,它有10级台阶,规定每一步只能上一级或两级,那么要登上10级台阶共有多少种不同的走法?

说明思路.

问答/202℃/2024-05-06 08:51:52

优质解答：

假设第1个人1根

第2个人2根

以此类推

第30000个人有30000根

从30001个人起就会相同

所以相同的人数为

50000-30000=20000

至少有2个人同样多

-------------------

这是一个经典的递归问题.也就是费波纳西级数.

f(n) = f(n-1) + f(n-2).

如果我们第一部选1个台阶,那么后面就会剩下n-1个台阶,也就是会有f(n-1)种走法.如果我们第一部选2个台阶,后面会有f(n-2)个台阶.因此,对于n个台阶来说,就会有f(n-1) + f(n-2)种走法.

因此,1个台阶f(1) = 1.

f(2) = 2,

f(3) = 3

f(4) = 5

f(5) = 8

f(6) = 13

f(7) = 21

f(8) = 34

f(9) = 55

f(10) = 89

加油

我来回答

猜你喜欢