一道经典的程序员逻辑算法类笔试题

题目是这样的：

f(1)=1,f(2)=1;
f(3)=f(2)+f(1);
f(4)=f(3)+f(2);
......
f(n)=f(n-1)+f(n-2);
请使用两种方法以上实现f(100)的值

这道题几乎适用于所有编程语言，主要考验面试者的逻辑能力和代码书写功底，解答方法较多，下面列举几个用JavaScript实现的方法。

方法1：递归（该方法能体现出回答者扎实的基本功，但在js中这么写，会造成运算超时，思路不错，炫技可以，但实用性不强）。

<script type="text/javascript">
    function f(n){
        if (n==2 || n==1) {
            return 1;
        }
        return f(n-1)+f(n-2);
    }
    var re = f(100);
    document.write(re);
</script>

方法2：一种基于题目原意的算法。

<script type="text/javascript">
    var x=1,y=1,z;
    for (var i=3;i<=100;i++) {
        z = x+y;
        x = y;
        y = z;
    }
 document.write(z);
</script>

方法3：一种基于题目原意的拓展思路。

<script type="text/javascript">
    var arr =[1,1];
    for (var i=2;i<100;i++) {
        arr[i] = arr[i-2]+arr[i-1];
    }
    document.write(arr[99]);
</script>

大家也可以包到函数里，实现f(100)这类的效果，但按照题目要求来讲，既然限定了f(100)，应该只要算出f(100)的值就ok了。如果有其他更好的方法，可以在文章下面回复哦。