算法设计实验报告二

《算法设计实验报告二》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法设计实验报告一、实验内容：题目：1、编程实现最长公共子序列描述：如题，需要你做的就是写一个程序，得出最长公共子序列。tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（LongestCommonSubsequence）。其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。2、超级台阶描述：有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？注：规定从一级到一级有0种走法

2、。3、最大和描述：给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。例子：0-2-7092-62-41-41-180-2其最大子矩阵为：92-41-18其元素总和为15。4、剑客决斗描述：在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A比B强

3、，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，则最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。假设现在n个人围成一个圈，按顺序编上编号1~n。一共进行n-1场决斗。第一场，其中一人（设i号）和他右边的人（即i+1号，若i=n，其右边人则为1号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知n个人之间的强弱关系（即任意两个人之间输赢关系）。如果存在一种抽签方式使第k个人可能胜出，则我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。5、最

4、长上升子序列问题描述：有一个长为n的数列a0,a1,„„,an-1。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i

5、的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。7、背包问题描述：现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。8、田忌赛马描述：田忌赛马的故事大家应该都听过吧。田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚

6、力都差不多，马可分为上、中、下三等。于是孙膑对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和诸公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，拿您的上等马对付他们的中等马，拿您的中等马对付他们的下等马。”已经比了三场比赛，田忌一场败而两场胜，最终赢得齐王的千金赌注。现在题目的要求是这样的，给出田忌n匹马的速度，再给出公子n匹马的速度，运用上述思想，求田忌最多能赢几场比赛。我们规定，赢一场可得200两黄金，输一场就扣200量黄金。平局不得也不扣。求田忌最多

7、能赢多少黄金。9、硬币问题描述：有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在要用这些硬币来支付A元、最少需要多少枚硬币？假定本题至少存在一种支付方案。二、核心代码说明：1、gonggongzixulie.h#include#include#defineN100usingnamespacestd;inta[N][N];chars1[N],s2[N];intmax(inta,intb){returna>=b

8、?a:b;}intmain(){intcount,i,j,length1,length2;cout<<"输入需要测试几个数据：";cin>>count;while(count--){cin>>s1+1>>s2+1;length1=strlen(s1+1);length2=strlen(s2+1);for(i=0;i<=length1;i++){a[i][0]=0;}for(i=0;i<=length2;i++){a[0][i]