实验1斐波那契数列的实现算法以及分析

1、陕西科技大学实验报告姓名 班级 学号 实验组别实验日期 室温 报告日期 成绩报告内容：(目的和要求、原理、步骤、数据、计算、小结等)实验名称：斐波那契数列实现算法及其分析实验目的：掌握分别用递归和非递归方法计算斐波那契(Fibonacci)数列。掌握算法性能测试的方法，并能进行计算分析和比较。掌握实验环境(硬/软件要求)：Windows 2000,Visual C+6.0实验内容：二阶 Fibonacci 数列定义如下：F0=1,F1=1，F2=2，F3=3，F4=5，,Fi=Fi-1+Fi-2(i=1)。是用递归和非递归两 种方法写出计算Fn的函数。实验要求：完成计算Fn的递归函数Fib_r

2、ec。完成计算Fn的递归函数Fib_itc。当N=10，15，20，25，30，35，40，45时测试以上两种算法的执行时间并把测试结果填写在附表1-1中。N 函数101520253035404589987109461213931346269149303511655801411836311903Fib_rec运行时间00000787818719Fib_itc运行时间00000000注：表格中填写的测试时间，单位ms。试解释两种算法在执行时间上的不同，并对两种算法进行算法分析。实验原理定义：斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

3、89, 144, 233577, 610，987, 1597， 2584， 4181， 6765， 10946， 17711， 28657， 46368 自然中的斐波那契数列 自然中的斐波那契数列特别指出：第0项是0，第1项是第一个1。这个数列从第2项开始，每一项都等于前两项之和。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系有存储单元的邻接 关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法。根据数据元素 间的逻辑关系，数据结构可分为线性结构和非线性结构，本次试验数据结构为线性结构的顺序存储结构，是一种随 机存取的存储

4、结构。递归算法主要求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题 的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规摸更小的问题，并从这些更小问题的解 制造规模较大的问题的解。递归算法的执行过程分为递推和回归两个阶段。在递归阶段，把较复杂的问题的求解推 到比原问题简单一些的问题求解。在用递归算法时，必须有一个递归的截止条件。递归算法是把复杂的问题简单化， 然后再由简单到复杂的过程，是我们生活中经常会用到的一种算法。【c语言程序】#include#includelong Fib_rec(int n)if(n=0|n=1)return(1)

5、;else return(Fib_rec(n-1)+Fib_rec(n-2);long Fib_ite(int n)long fib1,fib2,fib;int i;fib1=1;fib2=2;for(i=3;i=n;i+)fib=fib1+fib2;fib1=fib2;fib2=fib;return fib;void main()clock_t us1,us2;int n;printf(请输入 n:n)；scanf(%d,&n);us1=clock();printf(递归函数计算结果:ldn,Fib_rec(n);us2=clock();printf(递归函数执行时间%ld毫秒n,us2-u

6、s1);us1=clock();printf(非执行函数计算结果:ldn,Fib_ite(n); us2=clock();printf(非递归函数执行时间%ld毫秒n,us2-us1);实验结果：A函函归归葡归归递递秒89毫 :89葺 果间薄 篱算行iocess returned 0 execution tine : 2.281 sress any key to continue.7秒 7秒98毫 四3泉州 果间 荐算行 一n:数数 A.函函归归 一刖日一U-1-1 el请15蒯制非Process petupned 0 execution time : 4.953 s Press any ke

7、y to cont inue _C:U sesM en ovoDo cu m en tsC- F reeT em p函函归归 归归递递 EB递递北牌果: 10946 时间。毫秒 尊结果:理946 行时间。毫秒Process retuined 0 execution time : 4.516 s Press any key to continue.39 9313秒 13秒12毫 120S-1-:值 泉r局 篱算行数 函函归归 归归递递二0J果间Process returned 0 execution tine : 1.958 s Press any key to continue.C :U se

8、 rsl en ovoDo cu m en tsC-F reeT em pA 函函归归输归归递递请30递递非结果：1346269 时间。毫秒 尊结果= 1346269 行时间。毫秒Process retuined 0 Press any key to continue.execution time : 6.531 s入函函归归 输归归递递Mjgl35番事牌果：14930352 府间戏毫秒 尊结果:930352 行时间。毫秒Process retuined 0 execution time : 6.969 s Press any key to continue.801秒55s秒 55毫16毫 6

9、 1 : & :178果间 果间 荐算行请输入n ；置归函数计算 递归函数如亍 丰递归函教计 年递归函数册iocess petupned 0 execution time : 3.078 s ress any key to continue.n:数数函 入函函归归 输归归速递 请45递递素C :U sersl enovoDo cu m entsC- F reeT e m p5结果：1836311903 府间叩19毫秒 尊第果:1836311903 行府间。毫秒Process returned 0 execut ion time : 13.162 s Press any key to cont in Lie .实验小结：第一次实验是使用递归法计算斐波那契数列。在一开始时，主要是参照书上已经列好的函数代码，学习课本上编写 程序的思想，但由于自身编写程序能力很差，所以一开始问了别人这个代码送头到尾每一步都干了些什么。在程序 的最后是计算时间，使用时间函数，每次的答案都不一样，这与所使用的电脑以及电脑所处的转态有关，所以即使 是输入同一个数据，在不同电脑甚至同一台电脑不同