《算法设计实验报告二备考复习》由会员分享，可在线阅读，更多相关《算法设计实验报告二备考复习（46页珍藏版）》请在金锄头文库上搜索。
1、袆算法设计实验报告薄一、实验内容：袁题目： 1、编程实现最长公共子序列芀 描述：如题，需要你做的就是写一个程序， 得出最长公共子序列。 tip ： 最长公共子序列也称作最长公共子串 (不要求连续 )，英文缩写为 LCS (Longest Common Subsequence )。其定义是，一个序列 S ，如果分 别是两个或多个已知序列的子序列， 且是所有符合此条件序列中最长的， 则 S 称为已知序列的最长公共子序列。芇 2 、超级台阶芆 描述：有一楼梯共 m 级，刚开始时你在第一级，若每次只能跨上一级或二级， 要走上第 m 级，共有多少走法？莀 3 、最大和蚈描述：给定一个由整数组成二维矩阵（
2、 r*c ），现在需要找出它的一个子矩阵，使 得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。螄例子： 0 -2 -7 0蚃9 2 -6 2葿-4 1 -4 1聿-1 8 0 -2蒆其最大子矩阵为：蕿 -4 1蒀 -1 8其元素总和为 15 。蒅4剑客决斗描述：在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。 n 个人站 成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终 结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“ A 赢了 B”这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗， C 最终会赢，但如果 B
3、和 C 决斗在先，则最后 A 会赢。显然，他们三 人中的第一场决斗直接影响最终结果。人则为 1 号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知 n 个 人之间的强弱关系 （即任意两个人之间输赢关系） 。如果存在一种抽签方式使 第 k 个人可能胜出，则我们说第 k 人有可能胜出，我们的任务是根据 n 个人 的强弱关系，判断可能胜出的人数。蚆 5 、最长上升子序列问题芄描述：有一个长为n 的数列 a0,a1, , ,an-1 。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的ij都满足aiaj的子序列。（1 n 1000 , 0 Wai 1000000 ）。虿输入羈第一行
4、为 n莈下面一行为 a0an-1。蝿最长上升子序列的长度。荿 6、独木舟上的旅行 (贪婪法)螅描述：进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木 舟条数，并输出结果。螁 7 、背包问题衿描述：现在有很多物品(它们是可以分割的)，我们知道它们每个物品的单位重量的价值 v 和重量 w( 1=v,w=10 )；如果
5、给你一个背包它能容纳的重量为 m ( 10=m=20 ) ,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。薇描述：田忌赛马的故事大家应该都听过吧。田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，马可分为上、中、下三等。于是孙膑对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和诸公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，拿您的上等马对付他们的中等马，拿您的中等马对付他们的 下等马。”已经比了三场比赛，田忌一场败而两场胜，最终赢得齐王的千金赌 注。现在题目的要求是这样的，给出田忌 n 匹马的速度，再给出公子
6、 n 匹马的速 度，运用上述思想，求田忌最多能赢几场比赛。 我们规定，赢一场可得 200 两 黄金，输一场就扣 200 量黄金。平局不得也不扣。求田忌最多能赢多少黄金。螄9 、硬币问题罿描述：有 1元、 5元、 10元、 50元、 100 元、500 元的硬币各 C1、C5、C10、C50 、C100 、C500 枚。袆现在要用这些硬币来支付 A 元、最少需要多少枚硬币？假定本题至少存在一羅二、核心代码说明：1、2、 薃 gonggongzixulie.h聿#“ elude芇 #in elude蚇 #defi neN 100莂usingnamespace std;莂蚈int a NN;膅cha
7、r s1N,s2N;莅蒂int max( int a, int b)袇returna=b?a: b;蒀 int mai n()羃 int count,i,j,length1,length2;蚂coutvv 输入需要测试几个数据:蚇 cin co unt;肇 while (count-)肇len gth1=strle n( s1+1);蒄len gth2=strle n(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;jv=length2;j+)肁i
8、f (s1i=s2j)莇aij=ai-1j-1+1;肄else aij=max(ai-1j,aij-1);薆 cout最长公共子序列：alength1length2endl;芁 return 0;3、4、羄 chaojitaojie.cpp薂#“ elude莁usingnamespace std;薀 int mai n()螆蚅int n ,i,m;蒁int a45;螇 a1=0;蒇 a2=1;|莃 a3=2;蒁 for (i=4; in;薈while (n-)蚇羁cinm;蚁coutamvve ndl;罿肅 return 0;羄6、螀 zuidahe.cpp肆#“ elude螇#“ elude
9、螃usingnamespaee std;袀 int a102102;蒇 int mai n()芅薂 int i,j,k,m,r,c,max,temp;羀cout 输入矩阵行数：袈 cinr;羇coute ndl;薅cout 输入矩阵列数：肀cinc;艿 for (i=1;i=r;i+)莄莄for (j=0;j aij;膆aij=aij+ai-1j;肂膀祎 for (i=1,m=a10;i=r;i+)薄for (j=i;j=r;j+)袁芀for (k=max=0;k=O?max:O)+temp;蚈m=maxm?max:m;螄蚃葿coutm;聿蒆7、8、蒂 jia nkejuedou蕿#“ clu
10、de (+rlul!.o.l-u 一 )O4 矍(+E2o.ll-u 一)O4-(0) lu) 40 Ns00) lu)a)slu tu w-eaac-0Mu)CAAUO衆Eu -u 一 aou&lu luB-bcvIAl 一 bCVIAl 吕匸ooqn-kvIAl 一 UVIAI 一a) Eooq 櫟CXIogxvIAl euwptt噤2S oeds tueu 6srm螅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+)螄en d=(i+
11、start)%m;罿for (int k=(start+1)%m;k!=end;k+,k%=m)祎meetstarte nd=meetstarte nd |羅meetstartk&meetkend &薃(fightsstartk|fightse ndk);聿莂int coun t=0;莂for (int i=0;im;i+)蚈if (meetii) count+;膅coutco unt;莅蒂9、10、聿shangshengzixulie袇#“ clude膄usingnamespace std;薂 int mai n()蒀 int a100, f100, n ,i, j;莅 cinn;羃 for
12、 (int i=0; i ai;蚇 int max = 1; f0 = 1;肇 for (i=1; i=0; j-)蒄螅if (aj tm )袂tm = fj;蒈蒃if (fi max)羂max = fi;蚄 coutvvmaxvve ndl;节 return 0;羂11、12、羆tanlan莆#“ clude 肁usingnamespace std;肁 int mai n()袄 int n,w,m,i,a300,t;肄 cinn;賺 while (n-)薆cinw;袃cinm;芁int k=0,j=0;腿for (i=0;i ai;薂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+;羁elseif (i=j)蚁k+;罿else肅羄j-；螀
