日期:2014-05-20  浏览次数:20944 次

面试题,求思路!!!
有一个小和尚,从山脚到山顶共有n个台阶,假设小和尚可以一步迈一个台阶,也可以一步迈两个台阶,(排除其他特殊情况)请问小和尚到山顶共有多少种走法?请编写程序算出结果,并注释分析思路求教前辈,我一点思路都没..

------解决方案--------------------
这是一个递归问题。
f(n) = f(n-1) + f(n-2)。
如果我们第一部选1个台阶,那么后面就会剩下n-1个台阶,也就是会有f(n-1)种走法。如果我们第一部选2个台阶,后面会有f(n-2)个台阶。因此,对于n个台阶来说,就会有f(n-1) + f(n-2)种走法。


------解决方案--------------------
哟西,他要考你斐波那契数列,这是一个斐波拉契数列
你也可以百度百科看看
斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)


其实你也可以自己根据这题推算下他的一般式
首先他有两种跨步法,这是关键
我们假设他走到n阶梯有an中走法,我们照着高中数学里的思路来推他的一般式
设:
n=1 则a1=1//他只有一种走法
n=2 则a2=2//1.跨一跨一,2.跨二,共两种走法
n=3 则a3=?//1.跨一则剩余2阶梯,之后同n=2种走法。跨二则剩余1阶梯同n=1种走法
所以n=3共a21+a1种走法
n=4 则a4=?//跨一则剩余3阶梯,之后走法同n=3种走法。跨二则剩余2阶梯,之后走法同n=2中走法
所以n=4共a3+a2种走法
……………………
……………………
默想一下,穷举到这到此已经可以类推出一般式了 an=an-2+an-1//n-1、n-2是脚标哈
也就是说当前阶梯的走法是前两个阶梯走法之和,但是这里有特殊情况
当阶梯数小于三个(n<3)当前阶梯式前两个阶梯走法之和的条件是不成立的,因为前面阶梯都不够两个,何来两个阶梯之和
更一般的,如果他有三种跨步发,则就是当前阶梯走法是前三个阶梯之和
所以一般式为an=an-3 + an-2 + an-1
所以这面试题方法就很好写了,来个递归
 static void Main(string[] args)
{
Console.WriteLine(childThread(4));
Console.Read();
}
public static int childThread(int fblq)
{
if (fblq == 0) return 0;
else if (fblq == 1) return 1;
else if (fblq == 2) return 2;
else return childThread(fblq - 1) + childThread(fblq - 2);
}