求证一个算法题目，小兔子上10楼一共有多少种方法

陈良乔

前几天遇到一道有趣的题目
一座楼有10层，兔子可以跳跃的层数可以为1,2或者3，那么兔子到达10层有多少种跳法并列出各种情况。（请用Java实现）我想了一下可以嵌套循环，可是感觉方法太笨，各位大牛有好方法吗？
我写了个程序算了一下，可以有274种方法
数学比较差劲，所以来这里求证，是不是一共274种方法？

Ager

为啥一定要用Java实现？难道（又）是作业题？

starwing83

是274，你是对的。

陈良乔

回复 2# Ager
估计是吧，在网上看到的题目，一个同学问的
先别管用什么语言了，想请教这里的算法达人，结果是不是274？


   

陈良乔

回复 3# starwing83
哇，老师你太厉害了！这么快就有结果了
又想起唐伯虎的那句“我对你的敬仰如滔滔江水连绵不绝了”


   

folklore

递归

非递归比较不好办

Ager

陈良乔 发表于 2012-10-27 19:31
回复 2# Ager
估计是吧，在网上看到的题目，一个同学问的
先别管用什么语言了，想请教这里的算法达人，结 ...

1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274。

口算一下即可，或是149或是274。

考虑到上2nd台阶的方法是2，那么F(2nd)=2，所以F(10th)=274。

解毕。

陈良乔

回复 7# Ager
太厉害了，赞

   

Ager

folklore 发表于 2012-10-27 19:37
递归

非递归比较不好办

非递归也可以，而且是O(1)的，就是用通项公式生成函数（仅限于求方法数sigma，不能dump出上阶梯的方法），不过我的直觉是通项公式生成函数里会有根号，从精度上说，不太可靠。

folklore

回复 7# Ager


    口算，牛人啊，我怎么没想到。
想和汉诺诺差不多吧