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

starwing83

是274，你是对的。

starwing83

回复 12# fergon


    一百层？180396380815100901214157639

你验算下对不对。

starwing83

回复 23# Ager


    没嘲笑你用perl啊，可是用perl还比Python还长这个就不好了吧……

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
    

复制代码

starwing83

回复 35# gvim


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

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

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


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

starwing83

回复 40# pmerofc


    斐波拉契……

starwing83

回复 44# pmerofc


    斐波拉契的生成函数带根号5。

G.f.: x / (1 - x - x^2).
F(n) = ((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n*sqrt(5)).

starwing83

回复 54# Ager


    维基百科有LaTeX的数学模式渲染到图片的插件，不过我不太清楚。倒是2012年初维基百科宣称网站的渲染模块用Lua支持啥啥的

starwing83

回复 62# pmerofc


    这次是算留了一手吧？具体跳跃方法？