算法设计与分析实验报告

四川师范大学计算机学院实验报告册院系名称：计算机科学学院课程名称：算法设计与分析实验学期2015年至2015年第二学期专业班级：软件工程姓名：沙夫都学号：2013110431指导教师：苏菡实验最终成绩：实验报告须知1．学生填写实验报告应按规范填写，填写格式见由任课老师给出的实验报告样本；2．学生应填写的内容包括：封面相关栏目、第一页中‘本学期（年）开设实验课程情况一览表’中的实验名称、学时数；每次报告中的实验性质、同组人姓名、实验日期、以及实验报告中的一至五项；3．教师填写内容为：实验评价、每次报告成绩、第一页中‘本学期（年）开设实验课程情况一览表’中成绩、及封面的实验最终成绩；4．学生实验结束后，教师应对学生实验结果进行核实，学生方可离开实验室。5、实验成绩等级分为（90－100分）优，（80－89分）良，(70-79分)中，（60－69分）及格，（59分）不及格。6．本实验册应妥善保管，本课程实验结束后应交回实验室。本学期（年）开设实验课程情况一览表序号实验名称（学生实验后填写）学时数成绩（分数或等级）1算法设计基础22递归与分治策略及其应用33动态规划及其应用34贪心算法及其应用25回溯法及其应用26分支限界法及其应用（选做）17线性规划问题的求解（选做）1实验报告（1）实验名称算法设计基础同组人姓名实验性质□基本操作□验证性□综合性□设计性实验日期实验成绩教师评价：实验预习□实验操作□实验结果□实验报告□其它□教师签名：一、实验目的及要求（1）巩固程序设计语言基础知识，熟悉文件操作等。（2）对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。二、实验内容（1）统计数字问题（P8）（2）字典序问题（P8）（3）最多约数问题（P9）（4）最大间隙问题（P10）（5）设计算法求解fibonacci数列的第110项的值。注：至少选择其中2题完成三、主要设备及软件四、实验流程、操作步骤或核心代码、算法片段（1）统计数字问题（P8）#includeiostream#includestdlib.h#includefstream.hifstreamfin(input.txt);ofstreamfout(output.txt);usingnamespacestd;inti,n,m;intpage;//page是书的总页数intnumber[10]={0};voidmain(){finpage;for(intj=1;j=page;j++){n=j;while(n){m=n%10;++number[m];n=n/10;}}for(i=0;i=9;i++){foutnumber[i]endl;}fin.close();fout.close();return;}（3）最多约数问题（P9）#includeiostream#includestdlib.h#includefstream.hifstreamfin(input.txt);ofstreamfout(output.txt);usingnamespacestd;voidmain(){inta,b,i,j,max;finab;intnumber[100]={0};//约数个数for(i=a;i=b;i++){for(j=1;j=i;j++){if(i%j==0)number[i]++;//若能被整除则约数个数加1}}for(i=a;ib;i++){if(number[i]number[i+1])max=number[i];elsemax=number[i+1];}foutmaxendl;fin.close();fout.close();}五、实验结果的分析与评价实验报告（2）实验名称递归与分治策略及其应用同组人姓名实验性质□基本操作□验证性□综合性□设计性实验日期实验成绩教师评价：实验预习□实验操作□实验结果□实验报告□其它□教师签名：一、实验目的及要求1.实验目的（1）进一步掌握递归算法的设计思想以及递归程序的调试技术。（2）提高应用分治法设计算法的技能（3）理解这样一个观点：分治和递归经常同时应用在算法设计中。2.实验要求（1）认真填写实验报告，附加源代码（主要代码）和运行记录；（2）对设计好的算法，要分析算法的时间和空间复杂度。二、实验内容（1）设计算法求解整数的划分问题，对给定的整数，输出划分数。（P14）（2）设计算法求解n个互异元素的全排列的算法并编程实现（P13），并在此基础上修改程序，使其能解决有重复元素的排列问题（P41算法实现题2-5）。（3）设计算法求解棋盘的覆盖问题，并编程实现（P20）。（4）设计一个求解Gray码的分治策略，并编程实现（P39算法分析题2-14）。（5）设计求解半数集问题的算法，并编程实现。（P40算法实现题2-3）（6）设计求解整数因子分解问题的算法，并编程实现。（P43算法实现题2-11）（7）设计求解双色hanoi问题的算法，并编程实现。（P43算法实现题2-11）注：至少选择其中3题完成三、主要设备及软件四、实验流程、操作步骤或核心代码、算法片段（1）设计算法求解整数的划分问题，对给定的整数，输出划分数。（P14）并思考如何实现输出每个具体的划分。#includeiostream#includestdlib.husingnamespacestd;intq(intm,intn){if((n1)||(m1))return0;if((n==1)||(m==1))return1;if(mn)returnq(m,m);if(m==n)returnq(m,n-1)+1;returnq(m,n-1)+q(m-n,n);}voidmain(){intn,m;cout分别输入m和n的值(m为被划分数，n为最大加数)endl;cinmn;cout划分数为：endl;coutq(m,n)endl;system(pause);}（2）设计算法求解n个互异元素的全排列的算法并编程实现（P13），并在此基础上修改程序，使其能解决有重复元素的排列问题（P41算法实现题2-5）。#includeiostream#includestdlib.h#includefstream.hifstreamfin(input.txt);ofstreamfout(output.txt);usingnamespacestd;intcount=0;intcheck(charlist[],intk,intm)//判断是否互异，重复返回0{if(mk)for(inti=k;im;i++)if(list[i]==list[m])return0;return1;}inlinevoidswap(char&a,char&b){chartemp;temp=a;a=b;b=temp;}voidperm(charlist[],intk,intm){//依次交换第一个元素进行排序if(k==m)//只剩下一个元素{count++;for(inti=0;i=m;i++)foutlist[i];foutendl;}else//还有多个元素，递归产生排列for(inti=k;i=m;i++){if(check(list,k,i)){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}return;}voidmain(){charnumber[100];inti=0,n=0;//n是总个数finnumber;//number数组为待排元素while(number[i]!='\0'){n++;i++;}perm(number,0,n-1);foutcount;fin.close();fout.close();system(pause);}（6）设计求解整数因子分解问题的算法，并编程实现。（P43算法实现题2-11）#includeiostream#includestdlib.h#includefstream.hifstreamfin(input.txt);ofstreamfout(output.txt);usingnamespacestd;voidmain(){intnumber,result;intcount=1;finnumber;//输入整数for(inti=2;inumber;i++){if(number%i==0){result=number/i;//result是因子for(inti=2;i=result;i++){if(result%i==0)count++;}}}foutcount;fin.close();fout.close();}五、实验结果的分析与评价实验报告（3）实验名称动态规划及其应用同组人姓名实验性质□基本操作□验证性□综合性□设计性实验日期实验成绩教师评价：实验预习□实验操作□实验结果□实验报告□其它□教师签名：一、实验目的及要求1.目的要求（1）理解动态规划算法的概念和基本要素，并能和分治法进行比较。（2）掌握设计动态规划算法的步骤，并编程实现有关算法。（3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。（4）对设计好的算法，要分析算法的时间和空间复杂度。二、实验内容（1）编程实现矩阵连乘问题的求解。（P47）（2）分别采用分治法和动态规划法求解实现最大子段和问题，并编程实现。（P54）（3）编程实现最长公共子序列(LCS)问题的求解。（P52）（4）编程实现0－1背包问题的求解。（P71）（5）设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。（P87算法分析题3-1）（6）设计算法求解独立任务最优调度问题，并编程实现。（P79算法实现题3-1）（7）设计算法求解石子合并问题编程实现。（P79实现题3-3）（8）设计算法求解数字三角形问题，并编程实现。（P80题3-4）（9）设计算法求解最小m段和问题，并编程实现。（P81题3-8）（10）设计算法求解最少费用购物问题，并编程实现。（P88算法实现3-14）注：至少选择其中3题完成三、主要设备及软件（1）PC机（2）TC、VC++、Java等任一编程语言四、实验流程、操作步骤或核心代码、算法片段（2）分别采用分治法和动态规划法求解实现最大子段和问题，并编程实现。（P54）#includeiostream#includestdlib.husingnamespacestd;intMaxSubSum(int*a,intleft,intright)//最大子段和分治法{intsum=0;if(left==right)sum=a[left]0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i=left;i--){lefts+=a[i];if(leftss1)s1=lefts;}ints2=0;intrights=0;for(i=center+1;iright;i++){rights+=a[i];if(rights2)s2=rights;}sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;}returnsum;}intMaxSumDongtai(intn,int*a)//最大子段和动态规划法//n表示前n个数字{intsum=0,b=0;for(inti=1;i=n;i++){if(b0)b+=a[i];elseb=a[i];if(bsum)sum=b;}returnsum;}vo