《算法实验报告.docx》由会员分享，可在线阅读，更多相关《算法实验报告.docx（12页珍藏版）》请在三一文库上搜索。
1、算法实验报告算法实验报告 .c .c实验一 分治与递归算法的应用一、实验目的1掌握分治算法的基本思想 （分-治- 合）、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤 （基准与递归方程） 。3学会利用分治算法解决实际问题。二 . 实验容金块问题老板有一袋金块（共n块，n是2的幕（n2）,最优秀的雇 员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设 有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻 的金块。并对自己的程序进行复杂性分析。三. 问题分析 :一般思路：假设袋中有n个金块。可以用函数M a x （程序1 - 3 1）通过 n-1 次比 较找到最 重的金块。找
2、到最重的金块后， 可以从余下的 n-1 个金块中用类似法通过 n-2 次比较找出最轻的 金块。这样，比较的总次数为 2n-3。分治法：当n很小时，比如说，nW2,识别出最重和最轻的金块， 一次比较就足够了。当 n较大时(n2),第一步，把这袋金块 平分成两个小袋A和B。第二步，分别找出在A和B中最重和最 轻的金块。设 A 中最重和最轻的金块分别为 HA 与 LA ，以此类 推，B中最重和最轻的金块分别为 HB和LB。第三步，通过比较 HA 和 H B ，可以找到所有金块中最重的；通过比较 LA 和 LB， 可以找到所有金块中最轻的。在第二步中，若 n 2,则递归地应 用分而治之方法程序设计据上
3、述步骤, 可以得出程序 1 4 - 1的非递归代码。该程序用于寻找到 数组 w 0 : n - 1 中的最小数和最大数, 若 n 1 ,则程序返回 f a l s e, 否则返回 t r u e。当n1时，程序1 4 - 1给M i n和M a x置初值以使w M i n 是最 小的重量, w M a x 为最大的重量。首先处理nW 1的情况。若n1且为奇数，第一个重量 w 0 将成为 最小值和最大值的候选值,因此将有偶 ,数个重量值 w 1 : n - 1 参与 f o r 循环。当 n 是偶数时, 首先将两个重量值放在 for 循环外进行比 较，较小和较大的重量值分别置为 Min和Max，
4、因此也有偶数个重 量值w2:n-1参与for循环。在 for 循环中,外层 if 通过比较确定 ( w i , w i + 1 ) 中的较大和 较小者。此工作与前面提到的分而治之算法步骤中的 2) 相对应,而 层的 i f 负责找出较小重量值和较大重量值中的最小值和最大值,这 个工作对应于3 )for循环将每一对重量值中较小值和较大值分别与 当前的最小值 w M i n 和最大值 w M a x 进行比较，根据比较结 果来修改M i n和M a x (如果必要)。源程序#includeiostream#includestring.h#includealgorithmusing namespac
5、e std; 0float max(float g1,float g2)/ 比较找大值return(g1g2g1:g2);float Search_Max(float g,int left,int right)/ 用二分法递归找最大值if(left=right)/当只有一个数时，直接返回该值foaf max- maxugmghF efum max- isghfCDftHHl) 宀foaf LM.RM-LMHg=e3RMHgrighF refu m(max( L M SS対甘猗LMHSeachlMax(gefLmidxRMHSeachlMax(Fmid2ghRM)xfoaf SearchlMin
6、(f_oaf g=5-f -eenf lighf)/sN、Mt 宀 if(-eftHHIIghf) 宀foaf mmminugrighq 八efum min八isghfCDftHHl)LMHg=e3 RMHgrighFr2.um(min(LME：VJt档资料06lDebugOO5ab沙討R4 y 的丈ke 环全墓y 至各金金沙討R4 y 的丈ke 环全墓y 至各金金an /入 S4 5to continue实验总结通过这次实验，我深刻了解到分治法的实用性，有效性。当遇到 规模较大的问题，用我们以前学过的方法就太不明智了。将原问题划 分成若干个较小规模的子问题，再继续求解，划分，能够简化问题。递
7、归法，是一个很重要的方法，具有结构自相似的特性，刚开始学_ 编写的时候遇到了很多问题，不知道要找边界，不知道如何划分问题。关于这次算法，我觉得，类的部分还是一个难点，也就是说，不会将 问题分解成抽象的概念，这也是我以后需要重点学_的地方。实验二 动态规划算法的应用一、实验目的1掌握动态规划算法的基本思想，包括最优子结构性质和基于 表格的最优值计算方法。2熟练掌握分阶段的和递推的最优子结构分析方法。3学会利用动态规划算法解决实际问题。二、实验容最长单调递增子序列问题设计一个0(n2)复杂度的算法，找出由n个数组成的序列的最 长单调递增子序列。思路分析1、把a1,a2,.,an排序，假设得到a1,
8、a2,.,an然后求a的a的最长公共子串，这样总的时间复杂度为o(nlg(n)+o(n2)=o(n2);2、动态规划的思路：另设一辅助数组b,定义bn表示以an结尾的最长递增子序列的 长度，则状态转移方程如下： bk=max(max(bj|ajak,jk)+1,1); (见状态转移方程) 状态转移方程设辅助数组b，定义bn表示以an结尾的最长递增子序列的 长度，状态转移方程表示为：bk = max ( max(bj|ajak, jk )+1, 1 )其中ov二kv二n-1，在ak前面找到满足ajak的最大bj，ak 作为后继，得到ak的最长递增子序列的长度，如果ak前面没有更小的aj，此时ak
9、形成序列，长度为1,继续计算，最后整个序列 的最长递增子序列：max(bk |0二k二n-1)，此时时间复杂度仍为0(n A2)。另外定义一数组 c, c 中元素满足 cbk=ak ,即当递增子序列 的长度为bk时子序列的末尾元素为cbk=ak。实现代码第一种思路：#includevstdio.h /时间复杂度 O(nA2) int main()int i,j,k,n,a100,b100,c100,max;while(scanf(%d,n)!=EOF)for(i=0;in;i+) scanf(%d,ai);b0=1; /初始化，以a0结尾的最长递增子序列长度为1c0=a0; k=1;for(i
10、=1;in;i+)bi=1;bi最小值为 1for(j=0;ji;j+)if(aiaj bj+1bi)bi=bi+1;for(max=i=0;in;i+)/求出整个序列的最长递增子序列的长度if(bimax)max=bi;printf(%dn,max);.C.Creturn 0;运行结果实验总结通过实现动态规划的这个题目，对动态规划算法有了进一步的了解。先分析问题，判断是否具有最优子结果和重叠字问题的性质实验三贪心算法的应用一、实验目的掌握贪心算法的基本概念和两个基本要素熟练掌握贪心算法解决问题的基本步骤。学会利用贪心算法解决实际问题。二、实验容题目三：程序存储问题设有n个程序1,2,3,n要
11、存放在长度为L的磁带上。程序i 存放在磁带上的长度是li,1 i n。要求确定这n个程序在磁带上的 一个存储方案，使得能够在磁带上存储尽可能多的程序。输入数据中， 第一行是2个正整数，分别表示程序文件个数和磁带长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。输出为最 多可以存储的程序个数。输入数据示例6 502 3 13 8 80 20.c.c输出数据5题目分析：题目要求计算给定长度的磁带最多可存储的程序个数，先对程序的长度从小到大排序，再采用贪心算法求解。3、算法设计：定义数组an存储n个程序的长度，s为磁带的长度；调用库函数sort （ a，a+n ）对程序的长度从小到大
12、排序；函数most （）计算磁带最多可存储的程序数，采用while循环依次对排序后的程序长度进行累加，用i计算程序个数，用sum计算程序累加长度（初始 i=0，sum=0 ）:sum=sum+ai；若sum=s ，i加1，否则i为所求；i=n时循环结束；若while循环结束时仍有sum=s ，则n为所求。源程序：#in cludeiostreamusing n amespace std#in cludealgorithmint a1000000;int most (int *a , intn , int s )int i=0, sum=0 ;while (in )sum二ai+sum ;if (sum=s )i+；else return i；return n ;mai n ()int i , n , s;scanf (%d %dn, n , s);for (i=0 ; in ; i+ )scanf (%d , ai);sort (a, a+n )；printf (%d , most (a, n, s);.C.Creturn 0;实验总结此次实验让我对贪心算法的思想有了初步的了解，并且学会了 用贪心算法解决一些实际问题。两个程序中都运用了循环语句，在编 写代码时，在循环语句的设置中遇到许多问题，经过调试最终解决。所以，以后应当多做一些循环语句的练_。通过实践加强编程的熟练 程度