【SICP练习】126 练习3.57

2015/09/08 21:46
阅读数 3

练习3-57

原文

Exercise 3.57. How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay ) simply as (lambda () ), without using the optimization provided by the memo-proc procedure described in section 3.5.1.

分析

斐波那契中每个数都会由前两个数计算而来。因此斐波那契数列要求每一次求和时对空间的需求没有增加。当回头调用前面计算过的斐波那契数时不必重新计算。因为没有计算的是从0和1开始的,因此计算fib(n)至少需要fib(n)-1次加法。



感谢访问,希望对您有所帮助。 欢迎关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部