feng

飘逸~~~~~life

javascript求Fibonacci的问题

在学习javascript,一本书上后面有个习题:
编写一个计算Fibonacci数的程序,要求让用户输入n值,并显示计算结果。
Fibonacci的定义为:Fn=Fn-1+Fn-2,F1=1,F2=1,n=3,4....前几个Fibonacci数为:1,1,2,3,5,8,13........
首先是我自己写的
<html>
<head><script language="javascript">

var a=1;
var b=1;
var i=2;
var current;
function dell(n){
  current=a+b;
   b=a;
   a=current;
   i++;
   if(i==n){
   return current;
    }
   else{
   return dell(n);
   }
 }
</script></head>
<body>
<script language="javascript">
var userinput=eval(prompt("请输入N的置:",""));
var total=dell(userinput);
alert(total);
</script>
</body>
</html>
我里面dell函数的思路是用current来记录当前的Fibonacci的值,我初始了i=2,也就是没有管n=1,2的时候,检测i的值是否和n值相同,相同就返回当前的
current
否则继续递归dell函数
我看了参考答案,是这样写的
<html>
    <head><title> 7-4参考答案 </title>
    <script language=javascript>
        <!--
        function Fibonacci(n){  // 定义函数
            if ((n==1) || (n==2)) {
               return 1;
            }
            else {
               return (Fibonacci(n-1)+Fibonacci(n-2));
            }
        }
        //-->       
    </script>
    </head>
    <body>
      <script language="JavaScript">
         <!--
         var userinput=eval(prompt("请输入计算第几个Fibonacci数:", ""));
         var total=Fibonacci(userinput);  //调用递归函数
         alert("第"+ userinput +"个Fibonacci为:"+total);
         //-->       
      </script>
    </body>
    </html>
我发现在运行参考答案的时候,n的数值太大的时候就有问题了,浏览器非常卡,并且提示

这个是否说明我的程序比较有效率,是什么原因造成的?知道的人指点下

posted on 2008-01-10 11:15 feng 阅读(1484) 评论(4)  编辑  收藏

Feedback

# re: javascript求Fibonacci的问题 2008-01-11 06:19 马夺元

Fibonacci,在提到他的时候一般都是在说递归。
你自己写的里面其实已经不能完全说是递归了,已经有点循环的概念了(毕竟,递归是可以转换为循环),只是没有完全转换为循环。
你写的应该是比参考答案的效率高,因为调用函数的开销是很高的(就像参考但按中的那样)。
但递归有它自己的优点:结构(逻辑)清晰,可读性强。缺点就是效率低,相差一两个数量级是很常见的。
在实际当中,真正用递归的地方很少。  回复  更多评论   

# re: javascript求Fibonacci的问题 2008-10-14 16:49 hoho

递归的方法垃圾。  回复  更多评论   

# re: javascript求Fibonacci的问题 2008-10-14 17:35 hoho

这里设n取5,第一次递归:Fibonacci(5)=Fibonacci(4)+Fibonacci(3);
第2次递归:Fibonacci(5)=Fibonacci(4)+Fibonacci(3);
Fibonacci(4)=Fibonacci(3)+Fibonacci(2)
=Fibonacci(3)+1 ;
Fibonacci(3)=Fibonacci(2)+Fibonacci(1)=1+1=2;//n值为1or2,
第3次递归:Fibonacci(5)=Fibonacci(4)+Fibonacci(3);
Fibonacci(4)=Fibonacci(3)+Fibonacci(2)
=Fibonacci(3)+1 ;
Fibonacci(3)=Fibonacci(2)+Fibonacci(1)=1+1=2;
Fibonacci(3)=Fibonacci(2)+Fibonacci(1)=1+1=2;
1:f(5)
2:f(4)+f(3)
3:f(3)+f(2)+f(2)+f(1)
4:f(2)+f(1)+f(2)+f(2)+f(1)

如果n为6的话,几乎多了一倍的分解。f(6)=f(5)+f(4);
f(5) 为上面的。f(4)类似.
也就是说n+1的话,执行时间比n几乎多一倍。
  回复  更多评论   

# re: javascript求Fibonacci的问题 2008-10-14 17:43 hoho


<html>
<head>
<title>ex2.html</title>
</head>

<body>
<script type="text/javascript">
var n=eval(prompt("",""));
var i=0;
var lo=1;
var hi=1;
while(i<n-2){
hi=lo+hi;
lo=hi-lo;
i++;
}
alert(hi);
</script>
</body>
</html>  回复  更多评论   



只有注册用户登录后才能发表评论。


网站导航: