算法课程设计题目12个.docx
- 文档编号:5973391
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:32
- 大小:227.05KB
算法课程设计题目12个.docx
《算法课程设计题目12个.docx》由会员分享,可在线阅读,更多相关《算法课程设计题目12个.docx(32页珍藏版)》请在冰点文库上搜索。
算法课程设计题目12个
1、打包行李
宰勋每次不到旅行前日都绝不会打包行李,今天也是到了登机的前一天才坐下来开始打包的。
航空公司规定每人只能携带1件行李,而宰勋要带的东西比较多,1个行李箱肯定是不够的。
下面的目录列出了他想要带的每件物品的体积和必要程度。
物品
笔记本电脑
相机
XBOX365
咖啡研磨机
哑铃
百科全书
体积
4
2
6
4
2
10
必要程度
7
10
6
7
5
4
因行李箱的空间有限,所以能够放进去的物品总体积不能超过w。
编写程序计算出必要程度总和最大的物品目录。
示例输入值:
2
610
laptop47
camera210
xbox66
grinder47
dumbbell25
encyclopedia104
617
laptop47
camera210
xbox66
grinder47
dumbbell25
encyclopedia104
示例输出值:
243
laptop
camera
grinder
304
laptop
camera
xbox
grinder
2、计算第k个答案
摩尔斯电码字典
在没有电话的时代,摩尔斯电码是无线电传输领域中的一种常用代码。
电码以短信号(短点,o)和长信号(长点,-)的不同组合表示各种文字。
例如:
o—表示英文字母J,而—表示英文字母M。
假设有一本以n个长点和m(n、m<=100)个短点组成的、包含所有信号的字典。
例如:
n=m=2,就会包含如下信号。
--oo
-o-o
-oo-
o--o
o-o-
oo--
这些信号已按照字典顺序排列好了。
-的ASKII码是45,而o的ASCII码是111。
因此,按照字典顺序,-在前,o在后。
给定n和m时,编写代码计算出此字典的第k(k<=1,000,000,000,000)个信号。
例如:
上述字典的第四个信号是o--o。
3、剑客决斗
在路易十三和红衣主教黎塞留当权的时代,发生了一场决斗。
n个人站成一个圈,依次抽签。
抽中的人和他右边的人决斗,负者出圈。
这场决斗的最终结果关键取决于决斗的顺序。
现书籍任意两决斗中谁能胜出的信息,但“A赢了B”这种关系没有传递性。
例如,A比B强,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个人的强弱关系,判断可能胜出的人数。
输入
第一行是一个整数N(1<=N<=20)表示测试数据的组数。
第二行是一个整数n表示决斗的总人数。
(2<=n<=500)
随后的n行是一个n行n列的矩阵,矩阵中的第i行第j列如果为1表示第i个人与第j个人决斗时第i个人会胜出,为0则表示第i个人与第j个人决斗时第i个人会失败。
输出
对于每组测试数据,输出可能胜出的人数,每组输出占一行
样例输入
1
3
010
001
100
样例输出
3
4、第k个最大递增子序列
某个整数序列中,去掉0个以上的数字后,剩余的部分就是原序列的子序列。
例如,{7,4,9}、{10,4}、{10,9}等是{10,7,4,9}的子序列。
而序列{10,4,7}具有不同于原序列的排列顺序,因而不属于{10,7,4,9}的子序列。
严格递增的子序列称为递增子序列。
序列的递增子序列中,最长的序列称为最大递增子序列(LIS)。
例如:
{5,20,21,22,8,9,10}的最大递增子序列是{5,8,9,10}。
(不唯一)
给出以不同数字组成(无重复数字)的序列时,请编写程序,计算此序列的LIS中按照字典序排在第k个位置的LIS。
输入
第一行输入测试用例的个数C(C<=50)。
各测试用例的第一行输入序列中元素的个数n(1<=n<=500)和k(1<=k<=2*109)。
第二行输入序列的n个元素。
各元素是大于等于1而小于等于100,000的整数,且同一数字只出现1次。
可以假设序列的LIS至少有k个。
输出
每个测试用例在第一行输出LIS的长度l,第二行以l个整数输出第k个LIS。
示例输入:
3
86
51643287
84
21436587
82
56781234
示例输出:
3
148
4
1368
4
5678
5、津巴布韦
由于计划经济失败,津巴布韦称为世界上通胀率最高的国家。
这里的物价即使在一天中也会持续上涨,所以必须实时更新物品价格。
例如:
1个鸡蛋的价格为35亿津巴布韦元,所以超市做了每位数字的活动标价牌。
钟旭在穆加贝超市打工,有一天遇到了一位比较麻烦的客人。
这位客人要退回刚才买走的鸡蛋,但是他不仅丢失了发票,而且连购买鸡蛋的数量也记不清了。
鸡蛋价格已经在此期间上涨了1次,所以广告牌上已经写上新的价格。
辛亏钟旭还记得如下两件事情。
1)最近一次价格上涨的时候,钟旭只是交换了塑料板的顺序。
也就是说,没有添加其他塑料板,也没有去掉过广告牌中的塑料板。
2)看到最近一次上涨的价格时,钟旭心里曾经想过,“哇,这些钱刚好能购买m个糖果”。
所以,最后的鸡蛋价格是m的倍数。
(因为糖果的价格已经上涨,所以不能计算出鸡蛋的价格了)。
输入
第一行输入测试用例的个数C(C<=50)。
之后的C行里面每行输入两个自然数e和m(1<=e<=1014,2<=m<=20)。
当前鸡蛋的价格不能以0开始,但是之前的价格可以以0开始。
输出
每个测试用例在1行内输出可能的价格个数除以1000000007的余数。
示例输入值:
4
3213
1233
4222
127381739127
示例输出值
5
0
2
11033
示例输入输出值的说明
第一个示例输入值:
以前鸡蛋的价格可能是123元、132元、213元、231元、312元。
第二个示例输入值:
无论怎样重新排列123元的数字,结果都会比123元大,故无解。
第三个示例输入值:
224元和242元是可能的价格。
第四个示例输入值:
鸡蛋简直太贵了。
6、完全覆盖
有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。
但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?
由于游戏难度增加他自己已经没法解决了,于是他希望大家能用程序来帮他把问题解决了。
输入
有多组数据。
每组数据占一行,有两个正整数n(0 当n,m等于0时输入结束 输出 每组数据输出占一行,输出完全覆盖的种数。 样例输入 22 23 24 211 411 00 样例输出 2 3 5 144 51205 7、逃狱的汉尼拔博士 杀人狂魔汉尼拔博士逃狱了。 通缉令发布后,大量军警出动并实施全天候追捕,不过狡猾的汉尼拔博士并没有落网。 过了d日后,束手无策的警察们拜访了有着“编程天才”之称的查理教授。 查理教授对汉尼拔博士留在监狱的笔记本进行分析后,做出了如下假设。 1)汉尼拔博士为了避开检查,只走山路; 2)汉尼拔博士越狱当天选择了与监狱相邻的村子之一作为藏身之处; 3)汉尼拔博士为了逃避追捕,每天往一个相邻的村子逃窜。 为了验证假设,教授找到了与监狱所在村子以山路连接的n个村子的地图。 汉尼拔博士会按照此假设行动,而且会随机选择一个备选的村子。 编写程序计算d日后汉尼拔博士在各个村子的概率。 例如监狱在第三个村子,逃狱后的汉尼拔博士会在0、1、2、4、5中任意选择一个村子藏身。 因此,1天后汉尼拔博士藏在第0号村子的概率是1/5,两天后藏在第1号村子的概率是1/15。 输入 第一行输入测试用例的个数C(1≤C≤50)。 之后各行输入地图上显示的村子个数N(2≤N≤50)和逃狱后经过的天数D(1≤D≤100),以及监狱所在村子的号码P(0≤P 之后N行里各输入N个整数,形成一个序列A。 第i行j列的数值A[i][j]如果等于1,就表示从第i号村子到第j号村子有山路可走;如果是0,则表示无路可通。 接下来的一行输入要计算概率的村子的个数T(0≤T 如果一个村子与另一个村子相连,那么相反的路径也必定存在。 可假设一个村子连接到自身的路径不存在。 输出 每个测试用例以T个实数输出汉尼拔博士可能藏匿的概率。 存在小于10-7的绝对/相对误差的答案将被视为正确答案。 示例输入值 2 520 01110 10001 10000 10000 01000 3 024 823 01110000 10010000 10010000 11101100 00010011 00010001 00001000 00001100 4 3126 示例输出值 0.833333330.000000000.16666667 0.433333330.066666670.066666670.06666667 8、回转寿司 algospot内部举行的解题投注比赛中,积累的罚金实在太多,于是运营团队决定举行一次会餐,地点选择在回转寿司店。 来到回转寿司店的运营团队并没有急于品尝寿司,而是开了一个“策略”会议。 寿司店里共有n种菜品,团队对各个菜品标上了如下等级。 寿司种类 鸡蛋 三文鱼 鳗鱼 金枪鱼 牛排 炸鸡 价格 2500 3000 4000 5000 10000 15000 等级 7 9 10 12 20 1 运营团队要在不超过预算的情况下吃到等级总和最大的菜品。 假设可供购买的寿司不限量,那么能吃到的最大等级之和是多少呢? 输入 第一行输入测试用例的个数C(1<=C<=5)。 各测试用例的第一行输入寿司的种类n(1<=n<=20)和团队的总预算m(1<=m<=109)。 之后的n行中,每行输入一种寿司的价格和等级。 价格是2000以下的整数,但必须是100的倍数。 等级是20以下的自然数。 输出 每个测试用例在1行内输出可能的最大等级之和。 示例输入值 2 610000 25007 30009 400010 500012 1000020 150001 6543975612 25007 30009 400010 500012 1000020 150001 9、龙曲线 龙曲线是以简单的数学规则画出一种曲线,它具有以下形态。 曲线从一个简单的线段起始,按照一定规则变换此线段完成整个曲线。 每形成一次变换称为“完成了一次变换代”,而每完成一代,曲线会进化到更复杂的形式。 像这种“放大其一小部分的形状时,表现出与整个形状极为相似构造的图形”,就是分形。 画出龙曲线的方法暂且就称为龙曲线字符串吧! 龙曲线字符串由X、Y、F、+、-组成。 那么,要画出龙曲线就从一个点起始画出如下曲线即可。 F: 向前方移动一格并画线。 +: 向左旋转90度。 -: 向右旋转90度。 X、Y: 忽略。 画出第0代龙曲线的字符串是FX。 从下一代开始,按照如下方式利用前一代字符串进行字符替换,从而获得当前一代的龙曲线字符串。 X->X+YF Y->FX+Y 根据上面的替换式,就有如下的1、2代龙曲线字符串。 第一代: FX+YF 第二代: FX+YF+FX-YF 我们想要求出第n代龙曲线字符串。 不过,考虑到答案有可能很长,所以只想计算出第p个字符起始长度为l个字符的字符串。 请编写程序实现这种功能。 输入 第一行输入测试用例的个数C(C<=50)。 各测试用例的第一行分别输入3个整数,即龙曲线的世代n(0<=n<=50)、p以及l(1<=p<=1000000000、1<=l<=50)。 第n代龙曲线字符串的长度可假设成总是大于等于p+l的数值。 输出 每个测试用例在1行内输出第n代龙曲线字符串的第p个字符开始,输出l个字符。 示例输入 4 012 115 265 4276485347530 示例输出 FX FY+YF +FX-Y FX-YF-FX+YF+FX-YF-FX+YF-FX-YF- 10、通配符 通配符在很多操作系统中只用部分文件名指定文件。 这些加有通配符的字符串就是通配符范式,这种范式与文件名类似,但常常是包含特殊字符“*”或“? ”的字符串。 从通配符范式的第一个字符开始与文件名比较,如果所有字符都一致,那么通配符范式与文件名相对应。 通配符范式中的“? ”字符可以充当任何一个字符,而“*”字符可以充当长度大于等于0的任一字符串。 例如,通配符范式he? p可表示help、heap,但不能表示helpp。 而通配符范式“*p*”可表示help、papa,但不能表示hello。 下面给定通配符范式和文件名集合,编写程序找出对应于通配符范式的文件名。 输入 第一行输入测试用例的个数C(1<=C<=10)。 各测试用例的第一行输入通配符范式W,第二行输入文件名数量n(1<=n<=50)。 接下来的n行中,每行输入1个文件名。 通配符范式由大小写英文字母、数字、*、? 组成,文件名由大小写英文字母和数字组成。 所有字符串的长度都大于等于1小于等于100,且不包含空格。 输出 每个测试用例将按照字母顺序每行显示1个对应于通配符范式的文件名。 示例输入 3 he? p 3 help heap helpp *p* 3 help papa hello *bb* 1 babbbc 示例输出 heap help help papa babbbc 设计通配符匹配算法,其中*号可以匹配任意多个字符,? 号可以匹配任意一个字符。 例如12345和12*、12*? 以及12*4? 等都匹配。 函数原型为: boolmatch(constchar*str,constchar*strpattern); 分析: 利用动态规划来解决。 此题类似与LCS问题。 假设字符串A[i]代表前i+1个子字符串,B[j]代表前j+1个子字符串,那么A[i]与B[j]是否匹配可以由A[i-1],B[j-1];A[[i-1],B[j];以及A[i]B[j-1]结合当前A[i]与B[j]的字符来确定。 A[i]与B[j]匹配需进行如下判断 1、若(strpattern[j-1]=='? '&&str[i-1]! ='\0')或者strpattern[j-1]==str[i-1],即A[i]与B[j]的最后一个字符必须“相同”(这里相同是指必须占用一个字符),则只需判断A[i-1]和B[j-1]是否匹配; 2、若strpattern[j-1]=='*',则只需A[i]和B[j-1]匹配或者A[i-1]和B[j-1]匹配或者A[i-1]和B[j]匹配即可确定A[i]与B[j]匹配. 代码如下: [cpp] viewplaincopy 1.bool match_string(const char* str, const char* strpattern) 2.{ 3. int nStr = strlen(str); 4. int nPatt = strlen(strpattern); 5. int** pTable = new int* [nStr+1]; 6. for(int k = 0; k <= nStr; k++) { 7. pTable[k] = new int [nPatt+1]; 8. memset(pTable[k],0,(nPatt+1)*sizeof(int)); 9. } 10. 11. if(strpattern[0] == '*') 12. { 13. for(int i = 0; i <= nPatt; ++i) 14. { 15. pTable[0][i] = 1; 16. } 17. } 18. pTable[0][0]=1; 19. 20. for (int j = 1; j <= nPatt; ++j) 21. { 22. for (int i = 1; i <= nStr; ++i) 23. { 24. if((strpattern[j-1] == '? ' && str[i-1] ! = '\0') || strpattern[j-1]==str[i-1]){ 25. pTable[i][j] = pTable[i-1][j-1]; 26. } else if(strpattern[j-1] == '*'){ 27. if(pTable[i][j-1] == 1 || pTable[i-1][j] == 1 ||pTable[i-1][j-1]==1) 28. pTable[i][j] = 1; 29. } 30. } 31. } 32. 33. bool ret = (pTable[nStr][nPatt] == 1 ? true : false); 34. for(int k = 0; k <= nStr; k++) 35. delete [] pTable[k]; 36. delete pTable; 37. 38. return ret; 39.} 测试代码如下: [html] viewplaincopy 1.int main(int argc, char** argv) 2.{ 3. if(match_string(argv[1],argv[2])) 4. { 5. cout << argv[1] << " and " << argv[2] << " matched! " << endl; 6. } 7. else 8. cout << argv[1] << " and " << argv[2] << " are not matched! " << endl; 9. 10. return 0; 11.} 1.简述 题目描述: Str1中可能包含的字符: 除了'*'和'? '以外的任意字符。 Str2中可能包含的字符: 任意字符。 其中,'? '表示匹配任意一个字符,'*'表示匹配任意字符0或者多次。 给出这样两个字符串,判断Str2是否是Str1的子串,如果是输出第一个匹配到的子串,如果不是,输出"不是子串"。 2.分析 对于'? '的处理,只要在匹配的时候将代码由: if(str1[i]==str2[j])改为if(str1[i]==str2[j]||str2[j]=='? ')即可。 对于'*'的处理,可以将str2根据其中的'*'分为若干个片段,然后依次在str1中分别匹配这几个片段即可,而且对于这几个片段分别匹配,如果第k个片段在str1中匹配不到,后面也可以结束了。 这里举例说明一下: 对于str1="Ohyear.Totayisweekend! ",str2=*ye*a*e*",实际上就是在str1中匹配"ye","a","e"这三个片段。 Ohyear.Totayisweekend! yea e yea e yea e ye a e ye a e ye a e 实际上,能够匹配到上面6种情况,按照我们的如果从左到右的匹配每个片段返回的是第一种情况。 这里主要分析这种情况的处理,对于所有情况的输出后面再简单说明一下。 首先处理str2,根据'*'分成若干个部分,然后依次在str1中进行匹配,使用kmp算法即可。 这样判断能否匹配或者只找第一个匹配的子串的负责度是O(m+n) 3.代码实现 其中利用了kmp算法,为了使用方便,稍微改了下kmp算法的输入参数,即pat字符串的长度不用'\0'确定,用指定参数确定。 #include #include using namespace std; // KMP算法,pat长度由len_pat指定 void get_next(const char pat[], int next[], int pat_len) { // int len = strlen(pat); int len = pat_len; int i,j; next[0] = -1; for(i=1; i for(j=next[i-1]; j>=0 && pat[i-1]! =pat[j]; j=next[j]) ; if(j<0 || pat[i-1]! =pat[j]) next[i] = 0; else next[i] = j+1; // if (pat[i]==pat[next[i]]) next[i]=next[next[i]]; } for(int i=0; i if(pat[i] == pat[next[i]]) next[i] = next[next[i]]; } } // KMP算法,str长度由'\0'判断,pat长度由len_pat指定 int kmp_next(const char text[], const char pat[], int pat_len) { int t_length = strlen(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 课程设计 题目 12