算法分析与设计实验报告

1、百度文库- 让每个人平等地提升自我*院系：计算机科学学院专业：计算机科学与技术年级：课程名称：算法设计与分析基础班号：组号：指导教师：年月日1百度文库- 让每个人平等地提升自我组员实验名称实验目的或要求学号姓名算法实验整体框架的构建实验室1. 实验题目算法实验主菜单的设计。2实验目的熟悉实验环境VC ； 复习 C、 C+ 语言以及数据结构课程的相关知识，实现课程间的平滑过度；3. 实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：算法设计与分析实验1. 算法分析基础 Fibonacci 序列问题2. 分治法在数值问题中的应用 最近点对问题3. 减治法

2、在组合问题中的应用 8 枚硬币问题4. 变治法在排序问题中的应用 堆排序问题5. 动态规划法在图问题中的应用全源最短路径问题99. 退出本实验请输入您所要执行的操作（1， 2，3， 4， 5， 99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。2程序代码百度文库- 让每个人平等地提升自我void Meun()printf("nttn");printf("ntt算法设计与分析实验 n");printf("nttn");printf("ntt1、算法分析基础 Fibonacci 序

3、列问题 n");printf("ntt2、分治法在数值问题中的应用矩阵相乘问题n");printf("ntt3、减治法在组合问题中的应用枚硬币问题n");printf("ntt4、变治法在排序问题中的应用堆排序问题n");Printf("ntt4、动态规划法在图问题中的应用全源最短路径问题n");动态规划法在图问题中的应用全源最短路径问题printf("ntt99、退出本实验 n");printf("ntt");printf("ntt请输入您所要执行的操作

4、（ 1，2， 3， 4， 5，99）： ");void main()int a;while(1)Meun();3百度文库- 让每个人平等地提升自我4百度文库- 让每个人平等地提升自我5百度文库- 让每个人平等地提升自我6百度文库- 让每个人平等地提升自我7百度文库- 让每个人平等地提升自我4f4f4f8百度文库- 让每个人平等地提升自我9百度文库- 让每个人平等地提升自我10百度文库- 让每个人平等地提升自我;elseif(l=h)printf("第%d枚硬币是假的，它的重量是%d。 ",l,coinl);elseif(h-l=1)if(l>1)if(coi

5、nl=coin1)printf(" 第 %d枚硬币是假的，它的重量是 %d。 ",h,coinh); elseprintf("第 %d枚硬币是假的，它的重量是%d。 ",l,coinl);elseif(h<n)if(coinh=coinn)printf("第 %d枚硬币是假的，它的重量是%d。 ",l,coinl);elseprintf("第 %d枚硬币是假的，它的重量是%d。 ",h,coinh);elseif(l<h)ps=(h-l+1)/3;sum1=0;sum2=0;for(i=1;i<=

6、ps;i+)sum1+=coinl+i-1;sum2+=coinh-i+1;if(sum1=sum2)FakeCoin_1(coin,n,l+ps,h-ps);elseif(sum1=coinl+ps*ps)FakeCoin_1(coin,n,h-ps+1,h);elseFakeCoin_1(coin,n,l,l+ps-1);11百度文库- 让每个人平等地提升自我void FakeCoin()int i=1,n, coin100;printf("请输入硬币的个数: ");scanf("%d",&n);printf("请输入硬币的重量:n

7、");for(i=1;i<=n;i+)scanf("%d",&coini);FakeCoin_1(coin,n,1,n);实验结果及分析通过这个实验，理解并掌握了减治法的设计思想并理解了它与分治法的区别。在写这个算法前，一定要建立正确的求解模型。12百度文库- 让每个人平等地提升自我实验名称实验目的或变治法在排序问题中的应用 堆排实验室序问题实验题目用基于变治法的堆排序算法对任意一组给定的数据进行排序实验目的1）深刻理解并掌握变治法的设计思想；2）掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆；3）提高应用变治法设计算法的技能。实验要求1）

8、设计与实现堆排序算法；要求2）待排序的数据可以手工输入( 通常规模比较小，10 个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，15003000 个数据左右），用以检验 ( 用计数法 ) 堆排序算法的时间效率。实堆排序利用了大根堆 ( 或小根堆 ) 堆顶记录的关键字最大( 或最小 ) 这一特征， 使得在当前无序区中选取最大 ( 或最小 ) 关键字的记录变得简单。验(1) 用大根堆排序的基本思想（ 2）大根堆排序算法的基本操作原理（算法基本思想）特点 :堆排序 (HeapSort) 是一树形选择排序。堆排序的特点是： 在排序过程中， 将 Rl.n看成是一棵完全二叉树的顺

9、序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系 ( 参见二叉树的顺序存储结构) ，在当前无序区中选择关键字最大( 或最小 ) 的记录堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。它是 不稳定 的排序方法。13程序代码百度文库- 让每个人平等地提升自我动生成2.手动输入3.结束 n");scanf("%d",&choice);switch(choice)case 1:for(i=1;i<=n;i+)ai=rand();printf("产生的随机数为:");for(i=1;i<=n;i+

10、)printf("%d ",ai);printf("n");break;case 2:printf("输入要排序的数：n");for(i=1;i<=n;i+)scanf("%d",&ai);break;case 3:return;default:printf("输入错误！ n");return;m=n;while(m>1)Dui_1(a,m);for(i=1;i<=n;i+)printf("%d ",ai);printf("n")

11、;t=a1;a1=am;am=t;m=m-1;for(i=1;i<=n;i+)printf("%d ",ai);printf("n");printf("输出排序的结果:");for(i=1;i<=n;i+)printf("%d ",ai);system("pause");14百度文库- 让每个人平等地提升自我实验结果及分析经过这次实验，理解了变治法的设计思想，同时还掌握了堆的概念以及如何用变治法把任意给定的一组数据改变成堆。15百度文库- 让每个人平等地提升自我经过这几次的实验，对算

12、法的分析能力有了较大的提高。算法分析对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法 ,采用不同的分析方法。说说Fibonacci心序列问题， 这个实验让我们更好的理解递归算法和迭代算法的设计思想以及递归程序的调式技术，并应用递归算法和迭代算法效率的理论分析( 前验分析 ) 和实际分析 ( 后验分析 ) 方法。得这次实验也让我们理解了蛮力法、分治法、减治法、变治法的设计思想，提高应用蛮力法、分治法、减治法、变治法设计算法的技能。并且理解了几个重要观点：不同的算法可体以解决相同的问题，这些算法的解题思路不同，复杂程度不