每日打卡做题 [403] 神马数

每天坚持打卡做题

享受思考的乐趣

▲长按识别二维码或点击开始答题▼

点击开始答题

【昨天打卡问题】图书上架

将编号为1~n的n本书放入编号为1~n的n个书架上，要求编号为k的书只能放在编号为k-1或k或k+1的书架上，例如：当n=10时编号为1的书只能放在编号为1或2的书架上，编号为4的书只能放在编号为3或4或5的书架上，编号为10的书只能放在编号为9或10的书架上。那么，当n=4时一共有多少种放法？当n=10时又有多少种放法？

【解答】@子曰

用f(n)表示有n本书时的放法数，易知f(1)=1，f(2)=2。

下面考虑n>2的情况，因为编号为1的书本只能放在1号或2号书架上：

（1）若放在1号书架上，则剩下的n-1本书有f(n-1)种放法；

（2）若放在2号书架上，此时编号为2的书本只能放在1号或3号书架上，若放在3号书架上，则1号书架无书可放，所以编号为2的书要只能放在1号书架上，此时剩下的n-2本书有f(n-2)种放法。

故f(n)=f(n-1)+(n-2)(n>2)，事实上这是一个斐波那契数列。

有了这个递推关系，就可以得到f(3)=f(1)+f(2)=3，f(4)=(2)+f(3)=5，依次类推可得到f(10)=89。

即当n=4时一共有5种放法，当n=10时，一共有89种放法。

* 答案仅供参考，如有疑问请留言！

- END -