C#语言编程求解斐波那契数列--湖北科技职业学院.

二、问题分析
公元1200年，意大利数学家列昂纳多.斐波 那契在《计算之书》中第一次将斐波那契数 列推上了历史的舞台。在数学上，费波那契 数列是这样来定义的：
1, n 1; Fib(n) 1, n 2; Fib(n 1) Fib(n 2), n 2.
意大利数学家列昂纳多.斐波那契
C#语言编程求解斐波那契数列
湖北科技职业学院 电信工程学院
宋薇
目录
问题分析
01
02 03
问题导入
知识拓展
编程实现
04
一、问题导入
• 让我们首先从一个数列开始，它的前面几个数是：1、1、2、 3、5、8、13、21、34、55、89、144。这个数列的名字 叫做“斐波那契数列”。这个数列有什么应用的意义，为什 么要求解斐波那契数列呢？ • 让我们从nature by numbers工作室制作的微电影中了解这 一答案吧。
二、问题分析
F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5 F(6)=8 F(7)=13 F(8)=21 F(9)=34 F(10)=55
F(11)=89 F(12)=144 F(13)=233 F(14)=377 F(15)=610 F(16)=987 F(17)=1597 F(18)=2584 F(19)=4181 F(20)=6765
递归函数计算Fib(40)
竟然用了6538毫秒!
long FibIT( int n ) 迭代函数计算Fib(40) { if ( n<=2) 只用了1毫秒! return 1; long F1,F2,F3; F1 = 1, F2 = 1; for for(int (int i=3; i=3;i<=n; i<=n;i++) i++) { { F2+F1; FF == F2+F1; F1= F2; F1= F2; F2 F2 == F;F; } } return F; }
F(21)=10946 F(22)=17711 F(23)=28657 F(24)=46368 F(25)=75025 F(26)=121393 F(27)=196418 F(28)=317811 F(29)=514229 F(30)=823040
F(40)=?
F(31)=……….. F(32)=……….. F(33)=……….. F(34)=……….. F(35)=……….. F(36)=……….. F(37)=……….. F(38)=……….. F(39)=………..
. .
非 递 归( 迭 代）
五、小结
了解斐波那契数列的应用与递推公式; 掌握迭代法与递归法的求解过程；
提升编写程序的成就感。
下节预告：将递归算法转换为非递归算法的第二种方法 间接变换法（堆栈）
三、编程实现
int fibRE(n) { if(n <2) return n; else return f(n-1) + f(n-2); }
在编写递归调用的函数的时候 ，一定要把对简单情境的判断 写在最前面，以保证函数调用 在检查到简单情境的时候能够 及时地中止递归
递归函数求解Fibonacci调用过程
Fib(5) 5 return return Fib(3) + Fib(4) + Fib(3)
3 Fib(2)
1 return 1
2
return Fib(2) + 1 return 1 Fib(1) 1 return 1
2 return Fib(2) 1 return 1 +
Fib(1) 1 return 1
四、知识拓展
用新值取代变量旧值 F(3)=F(2)+F(1)
F
2 = 3 = 5 = 8 =
F2
1 + 2 + 3 + 5 +
F1
1 1 2 3
F(4)=F(3)+F(2) F(5)=F(4)+F(3)
F(6)=F(5)+F(4) 迭 代 表 达 式 F =F2+F1
F1=F2
F2=F
递归
long FibRE( int n ) { if ( n<=2) return 1; else return return FibRE(n-1)+FibRE(n-2); FibRE(n-1)+FibRE(n-2); }
二、问题分析
F(40)
F(39) F(38)
F(38)
…………….
ห้องสมุดไป่ตู้
F(37)
F(37)
F(36)
…………….
F(4)
F(3)
..….
F(2)
F(1)
..….
F(1)
F(3)
F(2)
F(2)
F(1)
1
1
1
F(2)
F(1)
1
1
1
1
1
二、问题分析
递归的条件
• 1.是把规模大的问题转化为规模小的相似的子问题来 解决。 • 2.在函数实现时，这个解决问题的函数必须有明显的 结束条件，否则就会产生无限递归的情况。