《算法设计与分析》实验报告

《算法设计与分析》实验报告网络10-1李俊实验一分治与递归基本题一：基本递归算法四、程序清单：#include<iostream>usingnamespacestd;intq(intn,intm) { if((n<1)||(m<1))return0; if((n==1)||(m==1))return1; if(n<m)returnq(n,n); if(n==m)return q(n,m-1)+1; returnq(n,m-1)+q(n-m,m); }intmain(){ inta,b,c; intq(intn,intm); cout<<"pleaseinputaandb"<<endl; cin>>a>>b; c=q(a,b); cout<<"整数的划分为："<<c<<endl; return0;}测试数据及结果如下图所示：基本题二：棋盘覆盖问题程序清单：#include<iostream>#include<iomanip>usingnamespacestd;intBoard[1024][1024];//模拟棋盘inttile=0;//骨牌编号,从0开始voidChessBoard(inttr,inttc,intdr,intdc,intsize);voidOutputBoard(intsize);intmain(){intsize,dr,dc;cout<<"请输入方阵的规格k(方阵为k*k,须为2的幂):";cin>>size;cout<<"请输入特殊方格的行号(矩阵下标由零开始计算,即0~k-1):";cin>>dr;cout<<"请输入特殊方格的列号(矩阵下标由零开始计算,即0~k-1):";cin>>dc;ChessBoard(0,0,dr,dc,size);//覆盖特殊棋盘OutputBoard(size);//输出覆盖后的棋盘return0;}voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左角子棋盘if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中ChessBoard(tr,tc,dr,dc,s);else{//本棋盘中没有特殊方格Board[tr+s-1][tc+s-1]=t;//把三格板t放在右下角,将此棋盘转化为特殊棋盘ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余部分}//覆盖右上角棋盘if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中ChessBoard(tr,tc+s,dr,dc,s);else{//本棋盘中没有特殊方格Board[tr+s-1][tc+s]=t;//把三格板t放在左下角,将此棋盘转化为特殊棋盘ChessBoard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余部分}//覆盖左下角棋盘if(dr>=tr+s&&dc<tc+s)//特殊方格位于本棋盘ChessBoard(tr+s,tc,dr,dc,s);else{//本棋盘中没有特殊方格Board[tr+s][tc+s-1]=t;//把三格板t放在右上角,将此棋盘转化为特殊棋盘ChessBoard(tr+s,tc,tr+s,tc+s-1,s);//覆盖其余部分}//覆盖右下角棋盘if(dr>=tr+s&&dc>=tc+s)//特殊方格位于本棋盘ChessBoard(tr+s,tc+s,dr,dc,s);else{//本棋盘中没有特殊方格Board[tr+s][tc+s]=t;//把三格板t放在左上角,将此棋盘转化为特殊棋盘ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余部分}}voidOutputBoard(intsize){inti,j;for(i=0;i<size;i++){for(j=0;j<size;j++)cout<<setw(5)<<Board[i][j];cout<<endl;}}测试数据及结果如下图所示：提高题一：二分搜索设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。#include<iostream>usingnamespacestd;#definesize20intarray[size],n;boolBinarySearch(inta[],intn,intx);intmain(){ cout<<"请输入所要查找的序列一共有几个数:";cin>>n; cout<<"请依次输入查找序列,用空格隔开:"; for(intx=0;x<n;x++) cin>>array[x]; cout<<"请输入您所要查找的数:"; cin>>x;BinarySearch(array,n,x);return0;}boolBinarySearch(inta[],intn,intx){inti,j;intleft=0;intright=n-1;while(left<=right){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;cout<<"您所要查找的数在该序列内,它的序号是"<<i<<endl;returntrue;}if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;cout<<"您所要查找的数不在该序列内，小于它的最大元素的位置为"<<i<<","<<"大于它的最小元素位置为"<<j;cout<<endl;returnfalse;}运行结果实验二动态规划算法基本题一：最长公共子序列问题

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。#include<iostream>#include<stdlib.h>#include<string.h>usingnamespacestd;#defineN20voidLCSLength(intm,intn,charx[N+1],chary[N+1],intc[N+1][N+1],intb[N+1][N+1]){ inti,j; for(i=1;i<=m;i++)c[i][0]=0; for(i=1;i<=n;i++)c[0][i]=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } elseif(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } for(ints=1;s<=m;s++) { for(intt=1;t<=n;t++) { cout<<c[s][t]; }cout<<endl; } cout<<"所得最大公共子串长度："<<c[m][n]<<endl;}voidLCS(inti,intj,charx[N+1],intb[N+1][N+1]){ if(i==0||j==0)return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); cout<<x[i]; } elseif(b[i][j]==2) { LCS(i-1,j,x,b); } else { LCS(i,j-1,x,b); } }intmain(){ charstr1[N+1],str2[N+1]; intc[N+1][N+1]; intb[N+1][N+1]; intstr1_len,str2_len; cout<<"请依次输入两个字符串str1、str2"<<endl; cout<<"str1:"<<endl; cin>>str1+1; cout<<"str2:"<<endl; cin>>str2+1; str1_len=strlen(str1+1);cout<<"str1的长度："<<str1_len<<endl;str2_len=strlen(str2+1);cout<<"str2的长度："<<str2_len<<endl;LCSLength(str1_len,str2_len,str1,str2,c,b);LCS(str1_len,str2_len,str1,b); cout<<endl; return0;}运行结果基本题二：最大字段和问题

若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。#include<iostream>usingnamespacestd;intmaxsum(intn,inta[]);intmain(){ intarray[20],n; cout<<"请输入所要求解的个数:"; cin>>n; cout<<"请依次输入各数，用空格隔开:"<<endl; for(intx=0;x<n;x++) cin>>array[x];maxsum(n,array); return0;}intmaxsum(intn,inta[]){ intsum=0,b=0; for(inti=0;i<=n;i++) {if(b>0)b=b+a[i]; elseb=a[i]; if(b>sum)sum=b; } cout<<"最大字段和为:"<<sum; cout<<endl; return0;}运行结果实验三贪心算法

基本题一：多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。#include<iostream>usingnamespacestd;//作业typedefstructJob{ intID;//作业号 inttime;//作业花费的时间}Job;//作业链表的节点typedefstructJobNode{ intID; inttime; JobNode*next;}JobNode,*pJobNode;//链表的表头typedefstructHeader{ ints;//作业完成的时间 pJobNodenext;}Header,*pHeader;//在m台机器中找到最先完成作业的一台intSelectMin(Header*M,intm){ intk=1,i; for(i=1;i<=m;i++) { if(M[i].s<M[k].s) { k=i; } } returnk;}//从大到小排序voidSort(Job*pData,intnum){ JobTemp; inti,j;for(i=1;i<num;i++) { for(j=i+1;j<=num;j++) { if(pData[j].time>pData[i].time) { Temp=pData[i];pData[i]=pData[j];pData[j]=Temp; } } }}//贪心算法voidGreedy(Job*p,intm,intn){ HeaderH[100]; inti,temp,sum; for(i=1;i<=m;i++) { H[i].s=0; } for(i=1;i<=m;i++) { H[i].s=H[i].s+p[i].time; } for(i=m+1;i<=n;i++) { temp=SelectMin(H,m); H[temp].s=H[temp].s+p[i].time; } sum=H[1].s; for(i=1;i<=m;i++) { if(sum<H[i].s) { sum=H[i].s; } } cout<<"加工时间最短为"<<sum<<endl;}voidmain(){ intm,n,i; Job*job; cout<<"机器台数m："<<endl; cin>>m; cout<<"作业数n："<<endl; cin>>n;job=newJob[n]; for(i=1;i<=n;i++) { cout<<"第"<<i<<"个作业所需要的时间："<<endl; cin>>job[i].time; job[i].ID=i; } Sort(job,n); Greedy(job,m,n);}运行结果:提高题二：汽车加油问题

一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。#include<iostream.h>intmain(){intn,k,way[10];intsum=0,count=0,flag=1;cout<<"加满油后可行驶k公里，k为:";cin>>k;cout<<"沿途有n个加油站,n为:";cin>>n;cout<<"依次输入两个加油站之间的距离:";for(inti=0;i<=n;++i)cin>>way[i];for(intj=0;j<=n;++j){sum+=way[j];if(sum>n){++count;sum=way[j];}if(way[j]>n){flag=0;break;}}if(flag)cout<<"最少加油次数为:"<<count<<endl;elsecout<<"NoSolution";return0;}运行结果

实验四回溯算法和分支限界法基本题一：符号三角形问题下面都是“-”。下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。+

+

-

+

-

+

++

-

-

-

-

+-

+

+

+

-

-

+

+

-

-

+

-

-

-

+

在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。#include<iostream.h>classTriangle{friendintComputer(int);private:voidBacktrack(intt);intn,//第1行符号的个数half,//每个三角形总符号数的一半count,//统计减号的个数**p;//指向三角形的二维指针longsum;//统计符合条件的的三角形的个数};voidTriangle::Backtrack(intt){inti,j,k,s,f;if((count>half)||(t*(t-1)/2-count>half))return;//如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数if(t<=n)//回溯条件直到nfor(i=0;i<2;i++){p[1][t]=i;count+=i;for(j=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//判断下行符号count+=p[j][t-j+1];}if(t>=n){//输出符合条件的三角形f=0;for(j=1;j<=t;j++)for(k=1;k<=t-j+1;k++)f+=p[j][k];if(f==half){//如果减号是总符号数的一半则输出并将sum加1cout<<"第"<<++sum<<"个三角形"<<'\n';for(j=1;j<=t;j++){for(s=1;s<j;s++)cout<<"";//2个空格for(k=1;k<=t-j+1;k++){if(p[j][k]==1)cout<<"-";//3个空格elsecout<<"+";//3个空格}cout<<'\n';}cout<<'\n';}}Backtrack(t+1);//回溯for(j=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}intComputer(intn)//友元函数调用Triangle类的成员函数{inti,j;TriangleX;X.n=n;X.count=0;X.sum=0;X.half=n*(n+1)/2;if(X.half%2==1)return0;//如果是一个三角形符号的总数是奇数则不符合条件，返回0X.half=X.half/2;int**p=newint*[n+1];//分配新行for(i=0;i<=n;i++)p[i]=newint[n+1];//分配新列for(i=0;i<=n;i++)for(j=0;j<=n;j++)p[i][j]=0;//给p所指向的二维数组赋值为0X.p=p;X.Backtrack(1);returnX.sum;}voidmain(){inti,n;cout<<"请输入第一行的符号个数：";cin>>i;n=Computer(i);cout<<"共有"<<n<<"个符号三角形"<<endl;}运行结果基本题二：0—1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?#include<iostream.h>intn,c,bestp;//物品的个数，背包的容量，最大价值intp[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量