搜索
陕西科技大学实验报告姓名班级学号实验组别实验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：斐波那契数列实现算法及其分析实验目的：1.掌握分别用递归和非递归方法计算斐波那契（Fibonacci）数列。2.掌握算法性能测试的方法，并能进行计算分析和比较。掌握实验环境（硬/软件要求）：Windows2000,VisualC++6.0实验内容：二阶Fibonacci数列定义如下：F0=1,F1=1，F2=2，F3=3，F4=5，……,Fi=Fi-1+Fi-2(i=1)。是用递归和非递归两种方法写出计算Fn的函数。实验要求：1.完成计算Fn的递归函数Fib_rec。2.完成计算Fn的递归函数Fib_itc。3.当N=10，15，20，25，30，35，40，45时测试以上两种算法的执行时间并把测试结果填写在附表1-1中。N函数101520253035404589987109461213931346269149303511655801411836311903Fib_rec运行时间00000787818719Fib_itc运行时间00000000注：表格中填写的测试时间，单位ms。4.试解释两种算法在执行时间上的不同，并对两种算法进行算法分析。实验原理定义：斐波那契数列指的是这样一个数列0,1,1,2,3,5,8,13,21,34,55,89,144,233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368自然中的斐波那契数列自然中的斐波那契数列特别指出：第0项是0，第1项是第一个1。这个数列从第2项开始，每一项都等于前两项之和。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系有存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法。根据数据元素间的逻辑关系，数据结构可分为线性结构和非线性结构，本次试验数据结构为线性结构的顺序存储结构，是一种随机存取的存储结构。递归算法主要求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规摸更小的问题，并从这些更小问题的解制造规模较大的问题的解。递归算法的执行过程分为递推和回归两个阶段。在递归阶段，把较复杂的问题的求解推到比原问题简单一些的问题求解。在用递归算法时，必须有一个递归的截止条件。递归算法是把复杂的问题简单化，然后再由简单到复杂的过程，是我们生活中经常会用到的一种算法。【c语言程序】#includestdio.h#includetime.hlongFib_rec(intn){if(n==0||n==1)return(1);elsereturn(Fib_rec(n-1)+Fib_rec(n-2));}longFib_ite(intn){longfib1,fib2,fib;inti;fib1=1;fib2=2;for(i=3;i=n;i++){fib=fib1+fib2;fib1=fib2;fib2=fib;}returnfib;}voidmain(){clock_tus1,us2;intn;printf(请输入n:\n);scanf(%d,&n);us1=clock();printf(递归函数计算结果:%ld\n,Fib_rec(n));us2=clock();printf(递归函数执行时间%ld毫秒\n,us2-us1);us1=clock();printf(非执行函数计算结果:%ld\n,Fib_ite(n));us2=clock();printf(非递归函数执行时间%ld毫秒\n,us2-us1);}实验结果：实验小结：第一次实验是使用递归法计算斐波那契数列。在一开始时，主要是参照书上已经列好的函数代码，学习课本上编写程序的思想，但由于自身编写程序能力很差，所以一开始问了别人这个代码送头到尾每一步都干了些什么。在程序的最后是计算时间，使用时间函数，每次的答案都不一样，这与所使用的电脑以及电脑所处的转态有关，所以即使是输入同一个数据，在不同电脑甚至同一台电脑不同时间，所运行出来的答案都可能是不一样的。在使用递归法计算函数时，只是解决比较简单的数据，但随着数据的增大，运算量也增大，可以很明显的看到，运算所用的时间变长很多，再点击运行后，如果数字较大往往需要很久的时间来等待计算机运行出结果。所以递归算法只适合一些简单的问题的求解，并不适合其他复杂问题的解决。