中南民族大学算法分析与设计实验报告.doc

组员

学号

姓名

实验名称

实验I：体验神奇的算法

实验室

S9205

实

验

目

的

或

要

求

本实验要求根据给定的正整数n计算第n个斐波那契数。请选择自己最熟悉的编程语言实现这些算法来体验算法求解问题的神奇，下列基本要求必须完成：

设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面。

对于相同的输入n值，利用五种方法（迭代、迭代改进、递归、显示公式、矩阵）计算第n个斐波那契数，并比较这五种方法的基本操作、基本操作次数、执行时间，以掌握对数、线性和指数增长率的极大差别。

利用迭代算法寻找不超过编程环境能够支持的最大整数的斐波那契数是第几个斐波那契数，给出执行时间。（32位：231-1forint,64位：263-1forint）

利用递归算法寻找不超过编程环境能够支持的最大整数的斐波那契数是第几个斐波那契数，给出执行时间。

根据第三步计算的最大的斐波那契数序号n，采用递归方式计算第n个斐波那契数，看其是否可以在1分钟内完成。

利用递归算法计算你的计算机能够在30秒内计算出的最大斐波那契数是第几个，计算出下一个斐波那契数的时间是多少，利用迭代算法求解同样的问题。

7、利用公式F(n)=[?n/sqrt(5)]快速计算第n个斐波那契数，找出出现误差时的最小n值。

实验

原理

（算法

基本

思想）

普通迭代算法：根据第一二位的数字求出第三位的数字，在令以前一二位的数字等于二三位的数字，以此类推依次往后求。

迭代改进：每次循环推进两位，因此循环次数减半，a+=b第一个数+第二个数生成第三个数，b+=a第三个数+第二个数生成第四个数。然后输出b,因此b输出的一定是偶数位（即n为奇数时正常输出），n从0开始，当n为奇数时实际有偶数个数，当n为奇数时，b输出的为偶数位上的数字。当n为偶数时，b输出的为奇数位上的数字。当n为奇数时，让数列从0开始；当n为偶数时，b输出为奇数位，要使其输出偶数位即将首位0去掉，让数列从n=1开始。让n为奇数时a=0,偶数时n=1,就可以让a=(n-1)1。

递归算法：直接调用自己或者通过一系列的调用语句间接地调用自己的函数求斐波拉些值。

显示公式：利用公式F(n)=[?n/sqrt(5)]快速计算第n个斐波那契数

矩阵求法：

编程环境能够支持的最大斐波拉契数：利用递归或迭代算法直至溢出，跳出循环

程

序

代

码

实

验

结

果

及

分

析

心

得

体

会

递归算法和迭代算法都是比较传统的方法，通过这次实验，学到了迭代算法的改进方法，用位运算可判断n的奇偶，以及输出规律提高计算速度。然后学习了斐波拉些数列的公式求法，和矩阵求法等新的方法，了解各个求法的差别。还学习了计算机能支持的最大斐波拉些数列的求法，收获了很多。大量递归的使用导致程序运行速度变得很慢，所以递归算法需要改进。迭代算法和迭代改进算法则是利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B，效率高，运行时间只因循环次数增加而增加。矩阵算法和公式法利用数学知识可以很快的求出所需值，若不考虑误差，则是最快速的解决方法。

成

绩

评

定

教师签名：

2022年月日

实验名称

实验II：检索算法的实现

实验室

S9205

实

验

目

的

或

要

求

本次实验拟解决生活中最常见的问题之一：检索问题（查找问题），该问题要求在一个列表中查找某个具体元素是否出现，若出现，返回具体元素在数组中的位置，否则返回-1。根据列表中元素的相对大小信息，有顺序检索、二分检索、三分检索等算法思路可供参考使用，本次实验需要学生根据所给列表的性质采取有效算法解决相关问题，并能分析各个算法所使用的算法设计技术和时间复杂度。下列基本要求必须完成：

设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面；

能够人工输入或随机生成一个长度为n的整数数组，要求数组任意两个元素都互不相同；

设计一个算法判断要求2中产生的整数数组是否为或未排序（输出0）、升序（输出1）、降序（输出2）、先升后降（输出3）、或先降后升（输出4）状态；

给定某具体元素，使用顺序检索算法判断该具体元素是否出现在要求2中产生的数组中，并统计关键字比较的次数；

给定某具体元素，使用多种方法（顺序查找、二分查找、三分查找、插值查找）判断该具体元素是否出现在要求2中产生的升序或降序的数组中，并统计关键字比较的次数；

附加：若出现，返回具体元素所在的位置，否则，返回小于最接近该具体元素的位置。

给定先升后降（或先降后升）数组，使用二分检索思路和三分检索思路查找该数组的最大值（或最小值），并统计关键字比较的次数。

7、给定无序数