算法设计实验报告二.docx

算法设计实验报告一、实验内容：题目：1、编程实现最长公共子序列 描述：如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 2、超级台阶 描述：有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？注：规定从一级到一级有0种走法。3、最大和描述：给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 例子： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为：9 2 -4 1 -1 8 其元素总和为15。4、剑客决斗 描述：在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，则最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。假设现在n个人围成一个圈，按顺序编上编号1n。一共进行n-1场决斗。第一场，其中一人（设i号）和他右边的人（即i+1号，若i=n，其右边人则为1号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知n个人之间的强弱关系（即任意两个人之间输赢关系）。如果存在一种抽签方式使第k个人可能胜出，则我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。5、最长上升子序列问题描述：有一个长为n的数列a0,a1,an-1。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的ij都满足aiaj的子序列。（1n1000，0ai1000000）。输入第一行为n下面一行为a0an-1。输出最长上升子序列的长度。6、独木舟上的旅行 （贪婪法）描述：进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。7、背包问题描述：现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1=v,w=10）；如果给你一个背包它能容纳的重量为m（10=m=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。8、田忌赛马描述：田忌赛马的故事大家应该都听过吧。田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，马可分为上、中、下三等。于是孙膑对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和诸公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，拿您的上等马对付他们的中等马，拿您的中等马对付他们的下等马。”已经比了三场比赛，田忌一场败而两场胜，最终赢得齐王的千金赌注。现在题目的要求是这样的，给出田忌n匹马的速度，再给出公子n匹马的速度，运用上述思想，求田忌最多能赢几场比赛。 我们规定，赢一场可得200两黄金，输一场就扣200量黄金。平局不得也不扣。求田忌最多能赢多少黄金。9、硬币问题描述：有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。 现在要用这些硬币来支付A元、最少需要多少枚硬币？假定本题至少存在一种支付方案。二、核心代码说明：1、 gonggongzixulie.h#include#include#define N 100using namespace std;int aNN;char s1N,s2N;int max(int a,int b) return a=b?a:b;int main() int count,i,j,length1,length2;coutcount; while(count-) cins1+1s2+1;length1=strlen(s1+1);length2=strlen(s2+1); for(i=0;i=length1;i+) ai0=0; for(i=0;i=length2;i+)a0i=0;for(i=1;i=length1;i+) for(j=1;j=length2;j+) if(s1i=s2j) aij=ai-1j-1+1; else aij=max(ai-1j,aij-1); cout最长公共子序列：alength1length2endl; return 0;2、 chaojitaojie.cpp#includeusing namespace std;int main() int n,i,m; int a45; a1=0; a2=1; a3=2; for(i=4; in; while(n-) cinm; coutamendl; return 0; 3、 zuidahe.cpp#include #include using namespace std;int a102102; int main() int i,j,k,m,r,c,max,temp; coutr;coutendl;coutc; for(i=1;i=r;i+) for(j=0;jaij; aij=aij+ai-1j; for(i=1,m=a10;i=r;i+) for(j=i;j=r;j+) for(k=max=0;k=0?max:0)+temp; m=maxm?max:m; coutm; 4、 jiankejuedou#include using namespace std; #define MAX 502 bool meetMAXMAX; bool fightsMAXMAX; int main() int n,m; cinn; while(n-) cinm; memset(meet,0,sizeof(meet); for(int i=0;i!=m;i+) for(int j=0;j!=m;j+) cinfightsij; int end; for(int i=0;im;i+) meeti(i+1)%m=true; for(int i=2;i=m;i+) for(int start=0;start!=m;start+) end=(i+start)%m; for(int k=(start+1)%m;k!=end;k+,k%=m) meetstartend=meetstartend | meetstartk&meetkend & (fightsstartk|fightsendk); int count=0; for(int i=0;im;i+) if(meetii) count+; coutcount; 5、 shangshengzixulie#includeusing namespace std;int main()int a100, f100, n ,i, j; cinn; for(int i=0; iai; int max = 1; f0 = 1; for(i=1; i=0; j-) if(aj tm ) tm = fj; fi = tm + 1; if (fi max)max = fi; coutmaxendl; return 0;6、 tanlan#include using namespace std;int main() int n,w,m,i,a300,t; cinn; while(n-) cinw;cinm; int k=0,j=0; for(i=0;iai; for(i=0;im;i+) for(j=i+1;jaj) t=ai; ai=aj;aj=t; for(i=0,j=m-1;i=j;) if(ai+aj=w) i+; j-; k+; else if(i=j) k+; else j-; k+; coutk; return 0; 7、 beibaowenti#include #include using namespace std;struct Tint v,w;c10;int cmp(T a,T b)if(a.vt;while (t-)cinsm;for (i=0;ici.vci.w;sort(c,c+s,cmp);sum=0;for (i=0;is;i+)if(ci.w=m)sum+=ci.v*ci.w;m=m-ci.w;elsesum+=ci.v*m;break;coutsumendl;return 0;8、 tianjisaima#include#includeusing namespace std;int tian1005,king1005;bool cmp(int a,int b)return ab;int match(int n)sort(tian,tian+n,cmp);sort(king,king+n,cmp);int tl=0,tr=n-1,kl=0,kr=n-1,win=0,lose=0;while(tlkingkl)win+;tl+;kl+;else if(tiantrkingkr)win+;tr-;kr-;elseif(tiantrn)for(i=0;itiani;for(i=0;ikingi;coutmatch(n)endl;return 0;9、 yinbiwenti#include using namespace std; const int V6 = 1, 5, 10, 50, 100, 500;int C6 = 3, 2, 1, 3, 0, 2;int