算法课程设计题目12个Word文件下载.docx
《算法课程设计题目12个Word文件下载.docx》由会员分享，可在线阅读，更多相关《算法课程设计题目12个Word文件下载.docx（32页珍藏版）》请在冰点文库上搜索。
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
样例输出
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<
=500）和k（1<
=k<
=2*109）。
第二行输入序列的n个元素。
各元素是大于等于1而小于等于100,000的整数，且同一数字只出现1次。
可以假设序列的LIS至少有k个。
每个测试用例在第一行输出LIS的长度l，第二行以l个整数输出第k个LIS。
示例输入：
86
51643287
84
21436587
82
56781234
示例输出：
148
1368
5678
5、津巴布韦
由于计划经济失败，津巴布韦称为世界上通胀率最高的国家。
这里的物价即使在一天中也会持续上涨，所以必须实时更新物品价格。
1个鸡蛋的价格为35亿津巴布韦元，所以超市做了每位数字的活动标价牌。
钟旭在穆加贝超市打工，有一天遇到了一位比较麻烦的客人。
这位客人要退回刚才买走的鸡蛋，但是他不仅丢失了发票，而且连购买鸡蛋的数量也记不清了。
鸡蛋价格已经在此期间上涨了1次，所以广告牌上已经写上新的价格。
辛亏钟旭还记得如下两件事情。
1）最近一次价格上涨的时候，钟旭只是交换了塑料板的顺序。
也就是说，没有添加其他塑料板，也没有去掉过广告牌中的塑料板。
2）看到最近一次上涨的价格时，钟旭心里曾经想过，“哇，这些钱刚好能购买m个糖果”。
所以，最后的鸡蛋价格是m的倍数。
（因为糖果的价格已经上涨，所以不能计算出鸡蛋的价格了）。
之后的C行里面每行输入两个自然数e和m（1<
=e<
=1014，2<
=m<
=20）。
当前鸡蛋的价格不能以0开始，但是之前的价格可以以0开始。
每个测试用例在1行内输出可能的价格个数除以1000000007的余数。
3213
1233
4222
127381739127
示例输出值
11033
示例输入输出值的说明
第一个示例输入值：
以前鸡蛋的价格可能是123元、132元、213元、231元、312元。
第二个示例输入值：
无论怎样重新排列123元的数字，结果都会比123元大，故无解。
第三个示例输入值：
224元和242元是可能的价格。
第四个示例输入值：
鸡蛋简直太贵了。
6、完全覆盖
有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。
但他感觉把棋盘完全覆盖有点简单，他想能不能把完全覆盖的种数求出来？
由于游戏难度增加他自己已经没法解决了，于是他希望大家能用程序来帮他把问题解决了。
有多组数据。
每组数据占一行，有两个正整数n（0<
n<
12）,m（0<
m<
12）。
当n，m等于0时输入结束
每组数据输出占一行，输出完全覆盖的种数。
22
23
24
211
411
00
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），村子的号码由0到N-1的数字组成。
之后N行里各输入N个整数，形成一个序列A。
第i行j列的数值A[i][j]如果等于1，就表示从第i号村子到第j号村子有山路可走；
如果是0，则表示无路可通。
接下来的一行输入要计算概率的村子的个数T（0≤T<
N），最后一行以整数型输入要计算概率的村子的号码Q（0≤Q<
N）。
如果一个村子与另一个村子相连，那么相反的路径也必定存在。
可假设一个村子连接到自身的路径不存在。
每个测试用例以T个实数输出汉尼拔博士可能藏匿的概率。
存在小于10-7的绝对/相对误差的答案将被视为正确答案。
示例输入值
520
01110
10001
10000
01000
024
823
01110000
10010000
11101100
00010011
00010001
00001000
00001100
3126
0.833333330.000000000.16666667
0.433333330.066666670.066666670.06666667
8、回转寿司
algospot内部举行的解题投注比赛中，积累的罚金实在太多，于是运营团队决定举行一次会餐，地点选择在回转寿司店。
来到回转寿司店的运营团队并没有急于品尝寿司，而是开了一个“策略”会议。
寿司店里共有n种菜品，团队对各个菜品标上了如下等级。
寿司种类
鸡蛋
三文鱼
鳗鱼
金枪鱼
牛排
炸鸡
价格
2500
3000
4000
5000
10000
15000
等级
9
12
20
运营团队要在不超过预算的情况下吃到等级总和最大的菜品。
假设可供购买的寿司不限量，那么能吃到的最大等级之和是多少呢？
第一行输入测试用例的个数C（1<
=C<
=5）。
各测试用例的第一行输入寿司的种类n（1<
=20）和团队的总预算m（1<
=109）。
之后的n行中，每行输入一种寿司的价格和等级。
价格是2000以下的整数，但必须是100的倍数。
等级是20以下的自然数。
每个测试用例在1行内输出可能的最大等级之和。
610000
25007
30009
400010
500012
1000020
150001
6543975612
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个字符的字符串。
请编写程序实现这种功能。
各测试用例的第一行分别输入3个整数，即龙曲线的世代n（0<
=50）、p以及l（1<
=p<
=1000000000、1<
=l<
第n代龙曲线字符串的长度可假设成总是大于等于p+l的数值。
每个测试用例在1行内输出第n代龙曲线字符串的第p个字符开始，输出l个字符。
示例输入
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。
下面给定通配符范式和文件名集合，编写程序找出对应于通配符范式的文件名。
=10）。
各测试用例的第一行输入通配符范式W，第二行输入文件名数量n（1<
接下来的n行中，每行输入1个文件名。
通配符范式由大小写英文字母、数字、*、？
组成，文件名由大小写英文字母和数字组成。
所有字符串的长度都大于等于1小于等于100，且不包含空格。
每个测试用例将按照字母顺序每行显示1个对应于通配符范式的文件名。
he?
p
help
heap
helpp
*p*
papa
hello
*bb*
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
strpattern）
2.{
3.
int
nStr
=
strlen（str）;
4.
nPatt
strlen（strpattern）;
5.
int**
pTable
new
int*
[nStr+1];
6.
for（int
k
0;
<
nStr;
k++）
{
7.
pTable[k]
[nPatt+1];
8.
memset（pTable[k],0,（nPatt+1）*sizeof（int））;
9.
}
10.
11.
if（strpattern[0]
==
）
12.
13.
i
nPatt;
++i）
14.
15.
pTable[0][i]
1;
16.
17.
18.
pTable[0][0]=1;
19.
20.
for
（int
j
++j）
21.
22.
23.
24.
if（（strpattern[j-1]
str[i-1]
!
||
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]
||pTable[i-1][j-1]==1）
28.
29.
30.
31.
32.
33.
bool
ret
（pTable[nStr][nPatt]
true
:
false）;
34.
35.
delete
[]
pTable[k];
36.
pTable;
37.
38.
return
ret;
39.}
测试代码如下：
[html]
1.int
main（int
argc,
char**
argv）
if（match_string（argv[1],argv[2]））
cout
argv[1]
"
and
argv[2]
matched!
endl;
are
not
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
ye
a
a
e
ye
实际上，能够匹配到上面6种情况，按照我们的如果从左到右的匹配每个片段返回的是第一种情况。
这里主要分析这种情况的处理，对于所有情况的输出后面再简单说明一下。
首先处理str2，根据'
分成若干个部分，然后依次在str1中进行匹配，使用kmp算法即可。
这样判断能否匹配或者只找第一个匹配的子串的负责度是O（m+n）
3.代码实现
其中利用了kmp算法，为了使用方便，稍微改了下kmp算法的输入参数，即pat字符串的长度不用'
确定，用指定参数确定。
#include
iostream>
deque>
using
namespace
std;
//
KMP算法，pat长度由len_pat指定
void
get_next（const
char
pat[],
next[],
pat_len）
{
len
strlen（pat）;
pat_len;
i,j;
next[0]
-1;
for（i=1;
i<
len;
i++）
for（j=next[i-1];
j>
=0
pat[i-1]!
=pat[j];
j=next[j]）
;
if（j<
0
=pat[j]）
next[i]
j+1;
if
（pat[i]==pat[next[i]]）
next[i]=next[next[i]];
}
i=0;
if（pat[i]
pat[next[i]]）
next[next[i]];
KMP算法，str长度由'
判断，pat长度由len_pat指定
kmp_next（const
text[],
t_length
strlen（
升级会员 