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

C#语言编程求解斐波那契数列宋薇湖北科技职业学院电信工程学院01020304问题分析知识拓展编程实现问题导入目录让我们首先从一个数列开始，它的前面几个数是：1、1、2、3、5、8、13、21、34、55、89、144。这个数列的名字叫做“斐波那契数列”。这个数列有什么应用的意义，为什么要求解斐波那契数列呢？让我们从naturebynumbers工作室制作的微电影中了解这一答案吧。一、问题导入意大利数学家列昂纳多.斐波那契二、问题分析公元1200年，意大利数学家列昂纳多.斐波那契在《计算之书》中第一次将斐波那契数列推上了历史的舞台。在数学上，费波那契数列是这样来定义的：F(1)=1F(2)=1F(3)=2F(4)=3F(5)=5F(6)=8F(7)=13F(8)=21F(9)=34F(10)=55F(11)=89F(12)=144F(13)=233F(14)=377F(15)=610F(16)=987F(17)=1597F(18)=2584F(19)=4181F(20)=6765F(21)=10946F(22)=17711F(23)=28657F(24)=46368F(25)=75025F(26)=121393F(27)=196418F(28)=317811F(29)=514229F(30)=823040F(31)=………..F(32)=………..F(33)=………..F(34)=………..F(35)=………..F(36)=………..F(37)=………..F(38)=………..F(39)=………..F(40)=?二、问题分析

F(38)

F(37)

F(37)…………….

F(3)

F(2)

F(1)

F(2)

F(2)

F(1)

1

1

1..….

1

1

F(3)

F(4)

1

F(2)

1

F(1)

1

F(1)……………...….二、问题分析递归的条件1.是把规模大的问题转化为规模小的相似的子问题来解决。2.在函数实现时，这个解决问题的函数必须有明显的结束条件，否则就会产生无限递归的情况。二、问题分析intfibRE(n){if(n<2)returnn;elsereturnf(n-1)+f(n-2);}三、编程实现在编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归return+Fib(4)Fib(3)return+

Fib(2)Fib(1)return+Fib(3)Fib(2)return

+

Fib(2)Fib(1)return1return1return1return1return111211132递归函数求解Fibonacci调用过程Fib(5)5F(3)=F(2)+F(1)F(5)=F(4)+F(3)FF2F1F(6)=F(5)+F(4)F(4)=F(3)+F(2)2=1+

13=2+15=3+28=5+

3F=F2+F1F1=F2F2=F迭代表达式用新值取代变量旧值四、知识拓展递归非递归(迭代）longFibIT(intn){if(n<=2)return1;longF1,F2,F3;F1=1,F2=1;for(inti=3;i<=n;i++){

F=F2+F1;F1=F2;F2=F;}returnF;}longFibRE(intn){if(n<=2)return1;elsereturnFibRE(n-1)+FibRE(n-2);}递归函数计算Fib(40)竟然用了6538毫秒!迭代函数计算Fib(40)只用了1毫秒!for(inti=3;i<=n;i++){

F=F2+F1;.F1=F2;.F2=F;}

return