算法分析与设计实验报告
****
院系：计算机科学学院
专业：计算机科学与技术
年级：
课程名称：算法设计与分析基础
班号:
组号:
指导教师：
年月日
设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大
致如下:
《算法设计与分析; 》实验
1
. 算法分析基础 一一Fibonacci 序列问题 2. 分治法在数值问题中的应用 - 最近点对冋题
3. 减治法在组合问题中的应用 - --8枚硬币问题
4. 变治法在排序问题中的应用 - --堆排序问题
5.
动态规划法在图问题中的应用一
—全源最短路径问题
99.退出本实验
请输入您所要执行的操作(1 , 2, 3, 4, 5, 99):
2)点击操作后进入相应的实验项目或是相应项目的下一级菜单; 3)可以反复执行，直到退出实验。
1.实验题目
算法实验主菜单的设计。
2. 实验目的
⑴熟悉实验环境VC ++ 6.0 ;
⑵ 复习C 、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度;
3. 实验要求
1)
本文档如对你有帮助，请帮忙下载支持! void Meun()
1
p rintf("\n\t\t \n");
p rintf("\n\t\t
《算法设计与分析》实验\n");
p rintf("\n\t\t \n");
p rintf("\n\t\t1
、算法分析基础 -- Fibonacci序列问题\n");
p rintf("\n\t\t2
、分治法在数值问题中的应用一一矩阵相乘问题\n");
p rintf("\n\t\t3
、减治法在组合问题中的应用一一枚硬币问题\n");
p rintf("\n\t\t4
、变治法在排序问题中的应用一一堆排序问题\n");
P rintf("\n\t\t4
、动态规划法在图问题中的应用一一全源最短路径问题\n");
动态规划法在图问题中的应用一一全源最短路径问题
P rintf("\n\t\t99
、退出本实验\n");
P rintf("\n\t\t ");
p rintf("\n\t\t }
void main()
{
int a;
请输入您所要执行的操作(1, 2，3，4，5，99)：");
程while(1) {
序Meun(); // 调用菜单函数显示菜单
scanf("%d", &a);
代switch(a)
{
码case 1:
{
Printf("\n\t\tFibonacci 序列问题\t\t\n");
fibonacci();
}
case 2:
{
break;
p rintf("\n\t\t 分治法在数值问题中的应用一一矩阵相乘问题\t\t\n");
matrix();
}
case 3:
{
break;
p rintf("\n\t\t 减治法在组合问题中的应用---- 8枚硬币问题\t\t\n");
COINFAKE();
case 5:
printf("\n\t\t
HEA P();
break;
printf("\n\t\t break;
case 99:
变治法在排序问题中的应用一一堆排序问题\t\t\n");
动态规划法在图问题中的应用一一全源最短路径问题\t\t\n");
printf(" 你选择退出本实验’\n ");
exit(0);
实验题目
给定一个非负整数 n 计算第n 个Fibonacci 数
实验目的
1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术
析）方法;
3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同,
复杂程度不同，效率也不同;
实验要求
1 ）使用教材2.5节中介绍的迭代算法 Fib （n ）,找出最大的n,使得 第n 个Fib on acci
数不超过计算机所能表示的最大整数，并给出具体的执行时间;
2）对于要求1）,使用教材2.5节中介绍的递归算法
F （n ）进行计算,同样给出具体的执
行时间，并同1）的执行时间进行比较;
对于输入同样的非负整数 n ,比较上述两种算法基本操作的执行次数; 对1）中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为@ 设计可供用户选择算法的交互式菜单（放在相应的主菜单下）。
实验名称 算法分析基础 一一Fibonacci 序列问
题
实验室
2）掌握并应用递归算法和迭代算法效率的理论分析
（前验分析）和实际分析（后验分
(1)；
本文档如对你有帮助，请帮忙下载支持!
F0 J F1 F1
J F2;
Retur n F2;
1、递归法基本思想
递归就是定义一个函数，让它自己调用自己。
Fib ( int n )
//输入整数n ,输出第n 个斐波那契数 {if(n=O)return 0;
（算
Else if(n=1)return 1;
Else return Fib( n-1)+Fib( n-2)
2、迭代法
这种方法相对于递归法来说在时间复杂度上减小了不少,
但代码相对就要复杂些了。
Fib ( int n )
//输入整数n ，输出第n 个斐波那契数 想）
{if(n=O)return 0;
Else if(n=1)return 1;
Else F0 J 0; F1 J1;
for(i=2;i< n-2;i++)
F2=f1+f0; 〃f1 表示当前的值