算法设计与分析实验报告

声明：此文档只作为学习参考，不得用作它途！《算法设计与分析》实验教学大纲实验学时：32实验个数：7实验学分：1课程性质：适用专业：计算机科学与技术、软件工程教材及参考书：1.《计算机算法设计与分析》，王晓东，北京：电子工业出版社，20122.《算法与数据结构》，傅清祥等著，北京：电子工业出版社，20033.《计算机算法导引—设计与分析》，卢开澄著，北京：清华大学出版社，2001大纲执笔人：刘芳大纲审定人：郭涛一、实验课的性质与任务算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非数值计算的常用算法。课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针对所给的问题设计和实现高效算法的基本能力。二、实验课程目的与要求计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技术，同时介绍算法的复杂性的概念通过对一些代表性算法的使用达到了解掌握与运用的目的。通过完成课程实验，使学生达到如下要求：1.熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。2.能对给定问题分析出恰当的数学模型，并设计出解决方案，将算法用高级语言（C，VC++等）编程实现。三、实验项目及内容提要算法设计与分析实验课程序实实验名称学必选学实验类型内容提要号验项目编号时做做分数基本操作验证综合设计11算法设计基础4√√通过本次实验，程序设计语言基础知识，熟悉文件操作等22递归与分治策略及其应用6√√√掌握递归算法的设计思想，提高应用分治法设计算法的技能33动态规划及其应用6√√√掌握设计动态规划算法的步骤，并编程实现有关算法。44贪心算法及其应用6√√√通过本次实验，掌握设计贪心算法的步骤，并编程实现有关问题的求解545回溯法及其应用6√√√通过本实验，理解回溯法的深度搜索策略，掌握用回溯法解题的算法框架。66分支限界法及其应用4√√√通过本实验，理解分支限界法的剪枝搜索策略，掌握用分支限界法算法框架77线性规划问题的求解4√√理解线性规划的算法模型，了解求解线性规划的单纯形算法，学会使用Excel求解线性规划问题。三、实验内容安排：实验一算法设计基础（验证型实验4学时）1.实验目的（1）巩固程序设计语言基础知识，熟悉文件操作等。（2）对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。2.实验要求（1）认真填写实验报告，附加源代码（主要代码）和运行记录；（2）对设计好的算法，测试运行实验数据，检查输出是否正确。并对算法的时间和空间复杂度进行分析。3.实验内容：（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;}（2）字典序问题（P8）（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();}（4）最大间隙问题（P10）（5）设计算法求解fibonacci数列的第110项的值。（6）设计算法求解尽可能多的完美数（完全数）。注：至少选择其中2题完成实验二递归与分治策略及其应用（验证型、设计型实验6学时）1.实验目的（1）进一步掌握递归算法的设计思想以及递归程序的调试技术。（2）提高应用分治法设计算法的技能（3）理解这样一个观点：分治和递归经常同时应用在算法设计中。2.实验要求（1）认真填写实验报告，附加源代码（主要代码）和运行记录；（2）对设计好的算法，要分析算法的时间和空间复杂度。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);}（3）设计算法求解棋盘的覆盖问题，并编程实现（P20）。（4）设计一个求解Gray码的分治策略，并编程实现（P39算法分析题2-14）。（5）设计求解半数集问题的算法，并编程实现。（P40算法实现题2-3）（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();}（7）设计求解双色hanoi问题的算法，并编程实现。（P43算法实现题2-11）注：至少选择其中3题完成实验三动态规划及其应用（验证型、设计型实验6学时）1.目的要求（1）理解动态规划算法的概念和基本要素，并能和分治法进行比较。（2）掌握设计动态规划算法的步骤，并编程实现有关算法。（3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。（4）对设计好的算法，要分析算法的时间和空间复杂度。2.实验内容（1）编程实现矩阵连乘问题的求解。（P47）（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;}voidmain(){inta[]={0,1,2,3,4,5,6,7};intn;coutMaxSubSum(a,0,7)endl;coutMaxSumDongtai(7,a)endl;return;}（3）编程实现最长公共子序列(LCS)问题的求解。（P52）（4）编程实现0－1背包问题的求解。（P71）#includestdlib.h#includeiostream#includestdio.husingnamespacestd;#definemax(a,b)(((a)(b))?(a):(b))//max(a,b)a,b中的最大值#definemin(a,b)(((