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

Ager

zylthinking 发表于 2012-10-27 21:50
规律想了以下， 恩， 应该是无误的， 所谓到达第10层的方法数， 其实就是等于到达 7, 8, 9 层的方法数， 最 ...

对，就是这个方法！

所以我说是“算术”，就是最最简单的加法。（所以，最好用线性的方法，老老实实地做加法，挨个更新数组元素。）千万不要用函数做，更不要用递归！

folklore

回复 27# Ager


   
从小爱犯这种错

Ager

zylthinking 发表于 2012-10-27 21:50
规律想了以下， 恩， 应该是无误的， 所谓到达第10层的方法数， 其实就是等于到达 7, 8, 9 层的方法数， 最后都是一步到达第十层

是的。

所以，可以推广开来，如果小兔子有N种蹬步法（就是一次能上多少阶的“小方法数”），那么，求上指定T阶的总方法的total（“大方法数”）就是：构造长度不少于T的数列：数列中每一项等于它前面的连续N项之和（项不够，用0凑）。

starwing83

回复 31# Ager


    递归也是可以的，不过诀窍是把递归变成“尾调用”，比如说这样：

1. local function solve(n)
   
2.     local function _rec(n, n_3, n_2, n_1)
   
3.         if n == 0 then
   
4.             return n_1
   
5.         else
   
6.             return _rec(n-1, n_2, n_1, n_1+n_2+n_3)
   
7.         end
   
8.     end
   
9.     return _rec(n, 0, 0, 1)
   
10. end
    

复制代码

gvim

@Ager

你误会我说的母函数了，其实就是生成函数或者说递推公式，28L那个整理出来就是母函数嘛

starwing83

回复 35# gvim


    那个只能算母函数的系数数列……可以参看这篇：

http://www.matrix67.com/blog/archives/120

fergon

这个东东用来说明如何将递归转为秩代，是个好例子，比阶乘要好。

windoze

回复 9# Ager

这个数列的递推公式是
f(n)=f(n-1)+f(n-2)+f(n-3)

starwing83

这里有个很好的网站，可以轻松找出任何已知的序列的一些信息：http://oeis.org/A000073

楼主的序列是三斐波拉契数列= =我也不知道那个词怎么翻译= =tribonacci

这儿有个通项公式：a(n) = 3*c*((1/3)*(a+b+1))^n/(c^2-2*c+4) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3), c=(586+102*sqrt(33))^(1/3). The offset is 1. a(3)=2. Round off to the nearest integer. [Al Hakanson (hawkuu(AT)gmail.com), Feb 02 2009]

别问我，我没看懂这玩意儿到底怎么算……

还给出一个Python的代码：
(Python)
def a(n, adict={0:0, 1:0, 2:1}):
.if n in adict:
..return adict[n]
.adict[n]=a(n-1)+a(n-2)+a(n-3)
.return adict[n] #- David Nacin, Mar 07 2012


简而言之：这网站就是一装逼利器啊……