算法设计与分析实验报告

1、精选优质文档-倾情为你奉上四川师范大学计算机学院实 验 报 告 册院系名称： 计算机科学学院 课程名称： 算法设计与分析 实验学期 2015 年至 2015 年 第 二 学期专业班级： 软件工程 姓名： 沙夫都 学号： 指导教师： 苏菡 实验最终成绩： 实验报告须知1学生填写实验报告应按规范填写，填写格式见由任课老师给出的实验报告样本；2学生应填写的内容包括：封面相关栏目、第一页中本学期（年）开设实验课程情况一览表中的实验名称、学时数；每次报告中的实验性质、同组人姓名、实验日期、以及实验报告中的一至五项；3教师填写内容为：实验评价、每次报告成绩、第一页中本学期（年）开设实验课程情况一览表中成绩

2、、及封面的实验最终成绩；4学生实验结束后，教师应对学生实验结果进行核实，学生方可离开实验室。5、实验成绩等级分为（90100分）优，（8089分）良，(70-79分)中，（6069分）及格，（59分）不及格。6本实验册应妥善保管，本课程实验结束后应交回实验室。 本学期（年）开设实验课程情况一览表序号实验名称（学生实验后填写）学时数成绩（分数或等级）1算法设计基础22递归与分治策略及其应用33动态规划及其应用34贪心算法及其应用25回溯法及其应用26分支限界法及其应用（选做）17线性规划问题的求解（选做）1实验报告（1）实验名称 算法设计基础同组人姓名实验性质 基本操作 验证性 综合性 设计性实

3、验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求（1） 巩固程序设计语言基础知识，熟悉文件操作等。（2） 对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。二、实验内容（1）统计数字问题（P8）（2）字典序问题（P8） （3）最多约数问题（P9） （4）最大间隙问题（P10） （5）设计算法求解 fibonacci 数列的第 110 项的值。 注：至少选择其中 2 题完成 三、主要设备及软件 四、实验流程、操作步骤或核心代码、算法片段（1） 统计数字问题（P8） #include "iostream" #i

4、nclude <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int i,n,m; int page;/page 是书的总页数 int number10=0; void main() fin>>page; for (int j=1;j<=page;j+) n=j; while(n) m=n%10; +numberm; n=n/10; for (

5、i=0;i<=9;i+) fout<<numberi<<endl; fin.close(); fout.close(); return; （3） 最多约数问题（P9） #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int a,b,i

6、,j,max; fin>>a>>b; int number100=0;/约数个数 for ( i=a;i<=b;i+) for (j=1;j<=i;j+) if( i%j=0) numberi+;/若能被整除则约数个数加 1 for( i=a;i<b;i+) if(numberi>numberi+1) max=numberi; else max=numberi+1; fout<<max<<endl; fin.close(); fout.close(); 五、实验结果的分析与评价实验报告（2）实验名称递归与分治策略及其应用同

7、组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1.实验目的 （1） 进一步掌握递归算法的设计思想以及递归程序的调试技术。 （2） 提高应用分治法设计算法的技能 （3） 理解这样一个观点：分治和递归经常同时应用在算法设计中。 2.实验要求 （1） 认真填写实验报告，附加源代码（主要代码）和运行记录； （2） 对设计好的算法，要分析算法的时间和空间复杂度。二、实验内容（1） 设计算法求解整数的划分问题，对给定的整数，输出划分数。 （P14）（2） 设计算法求解 n 个互异元素的全排列的算法并编程

8、实现（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 题完成 三、主要设备及软件 四、实验流程、操作步骤或核心代码、算法片段

9、（1） 设计算法求解整数的划分问题，对给定的整数，输出划分数。 （P14）并思考如何实现输出每个具体的划分。 #include "iostream" #include <stdlib.h> using namespace std; int q(int m,int n) if (n<1)|(m<1) return 0; if (n=1)|(m=1)return 1; if (m<n) return q(m,m); if (m=n) return q(m,n-1)+1; return q(m,n-1)+q(m-n,n); void main() i

10、nt n,m; cout<<"分别输入 m 和 n 的值(m 为被划分数，n 为最大加数)"<<endl; cin>>m>>n; cout<<"划分数为："<<endl; cout<<q(m,n)<<endl; system("pause"); （2） 设计算法求解 n 个互异元素的全排列的算法并编程实现（P13），并在此基础上修改程序，使其能解决有重复元素的排列问题（P41算法实现题 2-5）。 #include "iostre

11、am" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int count=0; int check(char list,int k ,int m ) /判断是否互异，重复返回 0 if( m > k) for(int i = k ; i< m ; i+) if( listi = listm ) return 0 ; ret

12、urn 1 ; inline void swap(char &a,char &b) char temp; temp=a;a=b;b=temp; void perm(char list,int k,int m) /依次交换第一个元素进行排序 if(k=m) /只剩下一个元素 count+; for(int i=0;i<=m;i+) fout<<listi<<" " fout<<endl; else /还有多个元素，递归产生排列 for(int i=k;i<=m;i+) if(check(list,k,i) swa

13、p(listk,listi); perm(list,k+1,m); swap(listk,listi); return; void main() char number100; int i=0,n=0; /n 是总个数 fin>>number; /number 数组为待排元素 while(numberi != '0') n+; i+; perm(number,0,n-1); fout<<count; fin.close(); fout.close(); system("pause"); （6） 设计求解整数因子分解问题的算法，并编程实

14、现。 （P43 算法实现题 2-11） #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int number,result; int count=1; fin>>number;/输入整数 for(int i=2;i<number;i+) if(n

15、umber%i=0) result=number/i; /result 是因子 for(int i=2;i<=result;i+) if(result%i=0) count+; fout<<count; fin.close(); fout.close(); 五、实验结果的分析与评价 实验报告（3）实验名称 动态规划及其应用同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1.目的要求 （1） 理解动态规划算法的概念和基本要素，并能和分治法进行比较。 （2） 掌握设计动态规划算

16、法的步骤，并编程实现有关算法。 （3） 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 （4） 对设计好的算法，要分析算法的时间和空间复杂度。二、实验内容（1） 编程实现矩阵连乘问题的求解。 （P47） （2） 分别采用分治法和动态规划法求解实现最大子段和问题，并编程实现。（P54） （3） 编程实现最长公共子序列(LCS)问题的求解。 （P52） （4） 编程实现 01 背包问题的求解。 （P71） （5） 设计一个 O(n2)时间的算法，找出由 n 个数组成的序列的最长单调递增子序列。（P87 算法分析题 3-1） （6） 设计算法求解独立任务最

17、优调度问题，并编程实现。 （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） #inclu

18、de "iostream" #include <stdlib.h> using namespace std; int MaxSubSum(int *a,int left,int right) /最大子段和 分治法 int sum=0; if(left=right) sum=aleft>0 ? aleft :0; else int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0; in

19、t lefts=0; for(int i=center;i>=left;i-) lefts+=ai; if(lefts>s1) s1=lefts; int s2=0; int rights=0; for( i=center+1;i<right;i+) rights+=ai; if(right>s2)s2=rights; sum=s1+s2; if(sum<leftsum)sum=leftsum; if(sum<rightsum)sum=rightsum; return sum; int MaxSumDongtai(int n,int *a) /最大子段和 动

20、态规划法 /n 表示前 n 个数字 int sum=0,b=0; for(int i=1;i<=n;i+) if(b>0) b+=ai; else b=ai; if(b>sum) sum=b; return sum; void main() int a=0,1,2,3,4,5,6,7; int n; cout<<MaxSubSum(a,0,7)<<endl; cout<<MaxSumDongtai(7,a)<<endl; return; （4） 编程实现 01 背包问题的求解。 （P71） #include <stdlib

21、.h> #include "iostream" #include <stdio.h> using namespace std; #define max(a,b) (a) > (b) ? (a) : (b) /max(a,b) a,b 中的最大值 #define min(a,b) (a) < (b) ? (a) : (b) /min(a,b) a,b 中的最小值 template <typename Type> void Knapsack(Type* v, int *w, int c, int n, Type *m) /递归初始条件

22、/v 价值,w 重量,c 容量,n 件数,m 价值数 int jMax = min(wn - 1, c); for (int j=0; j<=jMax; j+) /背包的重量 mnj = 0; for (j=wn; j<=c; j+) /背包的价值 mnj = vn; /m(i,j) 背包容量为 j，可选择物品为 i,i+1n 时 0-1 背包的最优值 for (int i=n-1; i>1; i-) jMax = min(wi - 1, c); for (int j=0; j<=jMax; j+) mij = mi+1j; for (j=wi; j<=c; j+

23、) mij = max(mi+1j, mi+1j-wi+vi); m1c = m2c; if (c >= w1) m1c = max(m1c, m2c-w1+v1); cout<<m1c<<endl; template <typename Type> void TraceBack(Type *m, int *w, int c, int n, int* x) /物品装入 xi为 1，反之为 0；背包容量 c 减少当前装入物品的重量 for (int i=1; i<n; i+) if(mic = mi+1c) xi = 0; else xi = 1;

24、 c -= wi; xn = (mnc)? 1:0; void main(int argc, char* argv) int n = 6,c = 20,x7; /n 个物品，用 x7来记录每个物品是否装入，c 背包容量 int w7 = -2, 5, 10, 9, 5, 2, 1; /每个物品的重量 int v7 = -1, 6, 3, -4, 4, 6, 0; /每个物品的价值 int *ppm = new int*n+1; for (int i=0; i<n+1; i+) ppmi = new intc+1; Knapsack<int>(v, w, c, n, ppm);

25、 TraceBack<int>(ppm, w, c, n, x); for ( i=1; i<=n; i+) cout<<xi; return; （8） 设计算法求解数字三角形问题，并编程实现。 （P80题 3-4） #include <stdio.h> void main() int a100100; int i,j,n; printf("输入行数：") ; scanf("%d",&n) ; for(i = 1 ; i <= n ; i + ) printf("输入第%d 行数：n&qu

26、ot;,i); for( j =1 ;j <= i; j+) scanf("%d",&aij ) ; for(i = n-1;i>0;i-) for(j = i;j>0;j-) aij += ai+1j+1 > ai+1j?ai+1j+1 : ai+1j; /aij选 ai+1j+1,ai+1j中最大的 printf("最大路径和是：%dn",a11 ) ; return; 五、实验结果的分析与评价实验报告（4）实验名称 贪心算法及其应用同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习

27、 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1.目的要求： （1） 理解贪心算法的概念和基本要素； （2） 掌握设计贪心算法的步骤，并编程实现有关问题的求解。二、实验内容（1） 编程实现活动安排问题的求解。 （P91） （2） 设计算法求解会场安排问题，并编程实现。（P108，算法实现题 4-1）。 （3） 编程实现最优装载问题的求解。 （P95） （4） 编程实现背包问题的求解。 （P94） （5） 编程实现多机调度问题的求解。 （P106） （6） 设计算法求解汽车加油问题，并编程实现。（P111，算法实现题 49）； （7） 设计算法求解删数问题，并编程实现。（P1

28、12，算法实现题 4-11）； （8） 设计算法求解数列级差问题，并编程实现。 注：至少选择其中 3 题完成。三、主要设备及软件（1） PC 机 （2） TC、VC+、Java 等任一编程语言 四、实验流程、操作步骤或核心代码、算法片段（1） 编程实现活动安排问题的求解。 （P91） void sort(int f,int n) /结束时间 f排序 int temp; for(int i=1;i<n;i+) for(int j=0;j<i;j+) if(fj>fj+1) /结束时间按从早到晚排序 temp=fj; fj=fj+1; fj+1=temp; cout<<

29、;"排序结果："<<endl; for(int i=0;i<n;i+) cout<<fi<<" " int greedySelector(int s, int f, bool A) /活动安排算法 int n=s.length-1,j=1,count=1; A1=true; for(int i=2;i<=n;i+) if(si>=fj) /若下一活动开始时间晚于上一活动，则下一活动可安排，活动数count 加 1 Ai=true; j=i; count+; else Ai=false; return

30、count; （3） 编程实现最优装载问题的求解。 （P95） #include "iostream.h" void sort(int *w,int *t,int n) /按照 weight 的升序进行排序 t for(int i=0;i <=n;i+) int minweight=w0;/最小值 for(int j=i;j <=n;j+) int temp=j; for(int k=i;k <=j;k+) if(wk <wtemp) minweight=wk; temp=k; tj=temp; void loadling(int x,int w,i

31、nt c,int n) int *t=new intn+1;/指向物品的序号 sort(w,t,n); for(int i=1;i <=n;i+) xi=0; for(i=1;i<=n&&wti<=c;i+) xti=1; c-=wi; cout<<"输出所装载的物品序列号以及它的重量为：" <<ti<<" "<<wi<<endl; void main() int n,c; cout<<"请输入要装载物品的数量"<<e

32、ndl; cin>>n; int *w=new intn+1;/指向物品的重量 int *x=new intn+1; for(int i=1;i <=n;i+) xi=0; cout<<"请输入该所能够装载的最大重量："<<endl; cin>>c; cout<<"请输入装载的物品的重量"<<endl; for( i=1;i<n+1;i+) cin>>wi; loadling(x,w,c,n); return; （4） 编程实现背包问题的求解。 （P94） v

33、oid Sort(int n,float v,float w) /按单位价值为物品排序 float l = v/w+v%w; void bubblesort(sqlist &l) /冒泡排序 int lastexchangeindex; int i,j; RcdType temp20; i=l.length; while(i>1) lastexchangeindex=1; for(j=1;j<l.length;j+) if(l.rj+1.key<l.rj.key) tempj=l.rj; l.rj=l.rj+1; l.rj+1=tempj; lastexchangei

34、ndex=j; i=lastexchangeindex; void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; float c = M; for(i = 1;i <= n;i+) xi = 0; /初始化 xi for(i = 1;i <= n;i+) if(wi>c) break; xi = 1; c-=wi; if(i<=n) xi = c/wi; return; （6） 设计算法求解汽车加油问题，并编程实现。（P111，算法实现题 49）； #include <std

35、io.h> void greedy(int d,int n,int k) int num = 0; /加油次数 for(int i = 0;i <= k;i+) /若加油站距离大于最大行驶距离，则无解 if(di > n) printf("No Solutionn"); return; int s = 0; for(i = 0;i <=k;i+) /若下站与下下站距离之和大于最大行驶数，则加油，反之不加 s += di; if(s > n) num+; s = di; printf("%dn",num); void main

36、() int i,n,k,d1000; /最多行驶 n 千米，k 个加油站，每个加油站距离 d; printf("请输入汽车加满油最大行驶距离n"); scanf("%d",&n); printf("请输入加油站个数n"); scanf("%d",&k); printf("请依次输入每个加油站距上一站距离n"); for(i = 0;i <= k;i+) scanf("%d",&di); greedy(d,n,k); return; 五、实验结果

37、的分析与评价实验报告（5）实验名称回溯法及其应用同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1.目的要求： （1） 理解回溯法的深度搜索策略，掌握用回溯法解题的算法框架； （2） 掌握设计回溯算法的基本技巧和实际问题的分析求解。二、实验内容（1） 设计算法从前 m 个大写字母(m26)种取出 n 个字母的所有排列（组合），并编程实现。 （2） 设计算法求解子集合问题，并编程实现。 （P151，算法实现题 5-1） （3） 设计算法求解工作分配问题，并编程实现。（P156，算法实现题 5-

38、13） （4） 设计算法实现 01 背包问题，并编程实现。（P159，算法实现题 5-22） （5） 设计算法求解旅行售货员问题，并编程实现。 （P139） （6） 设计算法求解 n 后问题，并编程实现。（P129）（7） 设计算法完成图的 m 着色问题，并编程实现。 （P137） （8） 设计算法用 L 形覆盖一个正方块组成的正方形，要求不重不漏(若边长不刚好，还需要挖掉 1 块)。 （9） 设计算法求解最佳调度问题，并编程实现。（P156，算法实现题 5-15） （11） 设计算法求解无优先级运算问题，并编程实现。（P156，算法实现题 5-16） 注：至少选择其中 3 题完成。三、主要设

39、备及软件（1） PC 机 （2） TC、VC+、Java 等任一编程语言 四、实验流程、操作步骤或核心代码、算法片段（4） 设计算法实现 01 背包问题，并编程实现。（P159，算法实现题 5-22） （关键代码） /*0-1 背包改进算法*/ int bestp;/最优结果 /*限界函数*/ int bound(int i,int cw,int cp) cw+=xi*wi; cp+=xi*pi; int cleft=c-cw; int b=cp; for(int j=i+1;j<=n&&wj<=cleft;j+) b+=pj; cleft-=wj; if(j<

40、;n) b+=pj*(cleft)/wj; return b; bool check(int i,int cw,int cp) if(cw+xi*wi>c)|(bound(i,cw,cp)<bestp) return false; else return true; void output(int i) cout<<i; /*功能函数*/ void tryload(int i;int cw;int cp) /cw 当前背包容量,cp 当前背包价值 if(i>n) /输出一个可行解 output(i); else for(int j=1;j>=0;j-) xi

41、=j; if(check(i,cw,cp) cw+=xi*wi; cp+=xi*pi; tryload(i+1,cw,cp); cw-=xi*wi; cp-=xi*pi; /*主函数*/ void main() tryload(1,0,0); （5） 设计算法求解旅行售货员问题，并编程实现。 （P139） 关键代码 #include "iostream.h" #include "stdlib.h" #define noedge 10000 int n,*bestx,*a,bestc; /顶点数,最优解，G 的邻接矩阵，最优值 /*主函数*/ void m

42、ain() getdata(); bestc=noedge; for(int i=1;i<=n;i+) bestxi = xi = i; traveling(2,0); cout<<bestc; for(int i=1;i<=n;i+) cout<<bestxi; /*约束、限界函数*/ bool check(int i,int cc) if(axi-1xi != noedge && cc+axi-1xi < bestc) return true; else return false; /*功能函数*/ bool traveling(i

43、nt i;int cc) if(i>n) else for(int j=i;j<=n;j+) swap(xi,xj); if(check(i,cc) cc+=axi-1xi; traveling(i+1,cc); cc-=axi-1xi; swap(xi,xj); if(axn1!=noedge) for(int k=1;k<=n;k+) cout<<xk; cc+=axnx1; cour<<cc; （6） 设计算法求解 n 后问题，并编程实现。（P129） #include "stdio.h" #include "std

44、lib.h" #include "math.h" #include "iostream" using namespace std; int n;/皇后个数 int *x; int count=0; bool check(int i) for(int k=1;k<i;k+) if(xk=xi)|fabs(xk-xi)=fabs(k-i) return false; else return true; void output(int i) cout<<i; int queue(int i) if(i>n) output(i)

45、; return 0; else for(int j=1;j<=n;j+) xi=j; if(check(i) i+; count+; return queue(i+1); void main() cout<<"请输入皇后个数："<<endl; cin>>n; x=new intn+1; queue(1); cout<<"可行方案有"<<count<<"种"<<endl; （7） 设计算法完成图的 m 着色问题，并编程实现。 （P137） 关键代

46、码 #include "iostream.h" #include "stdlib.h" void main() getdata(); count=0; trycolor(1); cout<<endl<<" " void trycolor(int i) if(i>n) output(); else for(int j=1;j<=m;j+) xi = j; if(check(i) trycolor(i+1); bool check(int i) for(int k=1;k<=i+1;i+) if(aki) = 1 && (xk = xi) return false; return true; 五、实验结果的分析与评价实验报告（6）实验名称分支限界法及其应用同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求（1） 理解分支限界法的基本思想和剪枝搜索策略； （2） 掌握设计分支限界法的基本技巧和实际问题的分析求解。二、实验内容（1） 编程实现 0/1 背包问题的队列式/优先队列式分支限界算法； （2） 编程实现队