Question

楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,用C++或lua语言编一程序计算共有多少种不同的走法.分别用递归、

Answer 1

int recursive(int n)

{

if (n <= 2)

return n;

return recursive(n - 1) + 2 * recursive(n - 2);

}

int iterative(int n)

{

int f1 = 1, f2 = 2, f;

for (int i = 3; i <= n; ++i)

{

f = f2 + 2 * f1;

f1 = f2;

f2 = f;

}

return f;

}