OpenJudge算法设计与分析习题解答.docx
《OpenJudge算法设计与分析习题解答.docx》由会员分享，可在线阅读，更多相关《OpenJudge算法设计与分析习题解答.docx（29页珍藏版）》请在冰点文库上搜索。
OpenJudge算法设计与分析习题解答
CompanyDocumentnumber：
WUUT-WUUY-WBBGB-BWYTT-1982GT
OpenJudge算法设计与分析习题解答
1、硬币面值组合
描述
使用1角、2角、5角硬币组成n角钱。
设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a,b,c组合。
输出顺序为：
先按c的值从小到大，若c相同则按b的值从小到大。
输入
一个整数n（1<=n<=100），代表需要组成的钱的角数。
输出
输出有若干行，每行的形式为：
iabc
第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a,b,c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
样例输入
10
样例输出
0011000
002810
003620
004430
005240
006050
007501
008311
009121
010002
源代码：
#include<>
#include<>
intmain（）{
intt=1;
inti,j,k;
intn;
scanf（"%d",&n）;
intA=n,B=n/2,C=n/5;
for（i=0;i<=C;i++）{
for（j=0;j<=B;j++）{
for（k=0;k<=A;k++）{
if（i*5+j*2+k*1==n）{
printf（"%03d%12d%12d%12d\n",t,k,j,i）;
t++;
}
}
}
}
getchar（）;
return0;
}
2、比赛排名
描述
5名运动员参加100米赛跑，各自对比赛结果进行了预测：
A说：
E是第1名。
B说：
我是第2名。
C说：
A肯定垫底。
D说：
C肯定拿不了第1名。
E说：
D应该是第1名。
比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。
请编程判断5位选手各是第几名。
输入
无
输出
输出要求：
按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，
第3行是C的名次，第4行是D的名次，第5行是E的名次。
样例输入
样例输出
源代码：
#include<>
intmain（）
{
printf（"5\n"）;
printf（"2\n"）;
printf（"1\n"）;
printf（"3\n"）;
printf（"4\n"）;
return0;
}
3、鸡兔同笼
描述
一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。
输入
一行，一个正整数a（a<32768）。
输出
一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。
如果没有满足要求的答案，则输出两个0，中间用一个空格分开。
样例输入
20
样例输出
510
源代码：
#include<>
intmain（）
{
intn;
scanf（"%d",&n）;
if（n%4==0）
printf（"%d%d",n/4,n/2）;
elseif（n%4!
=0&&n%2==0）
printf（"%d%d",n/4+1,n/2）;
else
printf（"00"）;
return0;
}
4、谁是你的潜在朋友
描述
“臭味相投”——这是我们描述朋友时喜欢用的词汇。
两个人是朋友通常意味着他们存在着许多共同的兴趣。
然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。
幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。
首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。
同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。
你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。
输入
第一行两个整数N,M，2<=N，M<=200。
接下来有N行，第i（i=1,2,…,N）行每一行有一个数，表示读者i-1最喜欢的图书的编号P（1<=P<=M）
输出
包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。
如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^^）
样例输入
45
2
3
2
1
样例输出
1
BeiJu
1
BeiJu
源代码：
#include<>
#include<>
intb[222];
inta[222];
intn,m;
intmain（）
{
scanf（"%d%d",&n,&m）;
for（inti=1;i<=n;i++）{
scanf（"%d",&a[i]）;
b[a[i]]++;
}
for（inti=1;i<=n;i++）{
if（b[a[i]]==1）
printf（"BeiJu\n"）;
elseif（b[a[i]]>=2）
printf（"%d\n",b[a[i]]-1）;
}
return0;
}
5、称体重
描述
赵、钱、孙、李四个人中既有大人也有小孩，给他们称体重时发现，他们每个人的体重都不一样，且体重（单位：
公斤）恰好是10的整数倍，且他们的体重都不高于50公斤，已知赵、钱两人的体重之和恰好等于孙、李两人的体重之和；赵、李两人的体重之和大于孙、钱两人的体重之和，并且赵、孙俩人的体重之和还小于钱的体重。
请编写一个程序，按照体重从小到大的顺序，打印出四人的姓氏的首字母和体重数。
输入
无
输出
打印出四人的姓氏的首字母（小写）和体重数（每人一行，姓名首字母和体重数之间用空格隔开）。
样例输入
无
样例输出
z10
q20
s30
l40
（以上输出仅用于说明格式）
#include<>
#include<>
intmain（）{
inta[4],b[4]={1,2,3,4},c[4]={'z','q','s','l'};
inti,j,t;
for（a[0]=1;a[0]<=5;a[0]++）{
for（a[1]=1;a[1]<=5;a[1]++）{
for（a[2]=1;a[2]<=5;a[2]++）{
for（a[3]=1;a[3]<=5;a[3]++）{
if（（a[1]!
=a[0]&&a[2]!
=a[1]&&a[2]!
=a[0]&&a[3]!
=a[2]&&a[3]!
=a[1]&&a[3]!
=a[0]）
&&（a[0]+a[1]==a[2]+a[3]）&&（a[0]+a[3]>a[1]+a[2]）&&（a[0]+a[2]for（i=0;i<4;i++）{
b[i]=a[i];
}
}
}
}
}
}
for（i=0;i<4;i++）{
a[i]=b[i];
}
for（i=0;i<4;i++）{
for（j=i+1;j<4;j++）{
if（b[i]>b[j]）{
t=b[i];
b[i]=b[j];
b[j]=t;
}
}
}
for（j=0;j<4;j++）{
for（i=0;i<4;i++）{
if（a[i]==b[j]）{
printf（"%c%d\n",c[i],b[j]*10）;
}
}
}
getchar（）;
return0;
}
6、比饭量
描述
3个人比饭量，每人说了两句话：
A说：
B比我吃的多，C和我吃的一样多
B说：
A比我吃的多，A也比C吃的多
C说：
我比B吃得多，B比A吃的多。
事实上，饭量和正确断言的个数是反序的关系。
请编程按饭量的大小输出3个人的顺序。
输入
无输入
输出
按照饭量大小输出3人顺序，比如：
ABC
样例输入
无
样例输出
无
#include<>
#include<>
intmain（）{
intA,B,C;
inta,b,c;
for（A=1;A<=3;A++）{
for（B=1;B<=3;B++）{
for（C=1;C<=3;C++）{
a=（（B>A）+（C==A））;
b=（（A>B）+（A>C））;
c=（（C>B）+（B>A））;
if（（（A>B&&ab））
+（（A>C&&ac））
+（（Bc）||（B==C&&b==c）||（B>C&&bif（a>b&&a>c）{
if（b>c）printf（"ABC"）;
elseprintf（"ACB"）;
}
if（b>a&&b>c）{
if（a>c）printf（"BAC"）;
elseprintf（"BCA"）;
}
if（c>a&&c>b）{
if（a>b）printf（"CAB"）;
elseprintf（"CBA"）;
}
}
}
}
}
getchar（）;
return0;
}
7、求排列的逆序数
描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。
考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足jik，那么就称（ij,ik）是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。
例如排列263451含有8个逆序（2,1）,（6,3）,（6,4）,（6,5）,（6,1）,（3,1）,（4,1）,（5,1），因此该排列的逆序数就是8。
显然，由1,2,…,n构成的所有n!
个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n（n-1）/2，对应的排列就是n,（n-1）,…,2,1。
逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。
输入
第一行是一个整数n，表示该排列有n个数（n<=100000）。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入
6
263451
样例输出
8
提示
1.利用二分归并排序算法（分治）；
2.注意结果可能超过int的范围，需要用longlong存储。
#include
usingnamespacestd;
constintMAX_NUM=100000+5;
longlongseq[MAX_NUM];
intN;
longlongans;
voidreSeq（longlong*seq,intlef,intrigh）{,&num[i].y）;
}
intans;
sort（num,num+t,cmp）;
if（t%2==1）
{
ans=0;
intzong=num[t/2].y;
for（i=0;i{
ans+=abs（num[i].y-zong）;
}
}
else
{
intzong=num[t/2].y+num[t/2-1].y;
zong/=2;
ans=0;
for（i=0;i{
ans+=abs（num[i].y-zong）;
}
}
printf（"%d\n",ans）;
return0;
}
12、0/1背包问题
描述
给定n种物品和一个背包，物品i（1≤i≤n）的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：
装入背包或者不装入背包。
如何选择装入背包的物品，使得装入背包中物品的总价值最大
输入
输入包含一组或多组测试例。
每组测试例的第一行是物品的数量n和背包的容量C，之后的n行是每个物品的重量及其价值。
输出
输出第一行是装入背包中物品的总价值，后面n行是各个物品装入背包的情况。
样例输入
510
26
23
65
54
46
样例输出
15
1
1
0
0
1
源代码：
#include<>
#include
usingnamespacestd;
intdp[110][1010];
intn,c,ans[110];
intw[110],v[110];
voidprint（）{
inti,j,k;
k=c;
for（i=n;i>=1;i--）{
if（dp[i][k]!
=dp[i-1][k]）{
ans[i]=1;
k=k-w[i];
}
else{
}
}
return;
}
intmain（）{
inti,j,k;
scanf（"%d%d",&n,&c）;
for（i=1;i<=n;i++）{
scanf（"%d%d",&w[i],&v[i]）;
}
for（i=1;i<=n;i++）{
for（j=1;j<=c;j++）{
dp[i][j]=dp[i-1][j];
if（j>=w[i]）{
dp[i][j]=max（dp[i-1][j-w[i]]+v[i],dp[i][j]）;
}
}
}
printf（"%d\n",dp[n][c]）;
print（）;
for（i=1;i<=n;i++）{
printf（"%d\n",ans[i]）;
}
return0;
}
13、最少硬币问题
描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:
n]中。
现要用这些面值的硬币来找钱。
可以使用的各种面值的硬币个数存于数组Coins[1:
n]中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。
输入
由文件提供输入数据，文件的第一行中只有1个整数给出n的值，第2行起每行2个数，分别是T[j]和Coins[j]。
最后1行是要找的钱数m。
输出
将计算出的最少硬币数输出到文件中。
问题无解时输出-1。
样例输入
3
13
23
53
18
样例输出
5
提示
运用动态规划法进行算法设计并编程实现。
源代码：
#include<>
#include
usingnamespacestd;
intw[110],v[110];
intdp[110][20010];
intn,m;
voidinit（）{
for（inti=0;i<110;i++）{
for（intj=0;j<20010;j++）{
}
}
}
intmain（）{
inti,j,k;
intt,x,cnt=1;
scanf（"%d",&n）;
for（i=1;i<=n;i++）{
scanf（"%d%d",&t,&x）;
for（j=1;j<=x;j++）{
w[cnt]=t;
v[cnt]=1;
cnt++;
}
}
scanf（"%d",&m）;
init（）;
for（i=0;i.,An}，考察这n个矩阵的连乘积A1A2...An。
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。
矩阵连乘积的计算次序与其计算量有密切关系。
例如，考察计算3个矩阵{A1,A2,A3}连乘积的例子。
设这3个矩阵的维数分别为10*100，100*5，和5*50。
若按（A1A2）A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50=7500。
若按A1（A2A3）计算，则总共需要100*5*50+10*100*50=75000次数乘。
现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。
输入
输入数据由多组数据组成。
每组数据格式如下：
第一行是一个整数n（1≤n≤26），表示矩阵的个数。
接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。
如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。
输出
对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。
如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。
样例输入
3
A10100
B1005
C550
A（BC）
样例输出
75000
源代码：
#include<>
#include
#include
#include<>
#include<>
#include
usingnamespacestd;
intn,ans;
stringexp,str;
intx,y;
structnode{
intx,y;
};
nodes[200];
intflage;
stackope;
stackv;
stringchange（stringt）{
intlength=（）;
stringdes="";
for（inti=0;iif（isalpha（t[i]））{
if（t[i+1]=='）'）{
des=des+t[i];
}
else{
des=des+t[i]+'*';
}
}
elseif（t[i]=='（'）{
des=des+t[i];
}
else{
if（t[i+1]=='）'）{
des=des+t[i];
}
else{
des=des+t[i]+'*';
}
}
}
des=des+t[length-1]+'=';
returndes;
}
nodecalc（nodea,nodeb）{
if!
={
flage=1;
}
nodet;
ans=ans+**;
=;=;
returnt;
}
charcompare（chari,charj）{
if（i=='='）{
if（j!
='='）{
return'<';
}
else{
return'=';
}
}
if（i=='（'）{
if（j=='）'）{
return'=';
}
else{
return'<';
}
}
if（i=='*'）{
if（j=='（'）{
return'<';
}
else{
return'>';
}
}
}
intmain（）{
inti,j,k;
stringe;
while（cin>>n）{
for（i=1;i<=n;i++）{
cin>>str>>x>>y;
s[str[0]].x=x;
s[str[0]].y=y;
}
cin>>e;
flage=0;
ans=0;
exp=change（e）;
while（!
（））{
（）;
}
while（!
（））{
（）;
}
（'='）;
intl=（）;
for（k=0;k<=l-1;）{
if（isalpha（exp[k]））{
（s[exp[k]]）;
k++;
}
else{
if（compare（）,exp[k]）=='='）{
（）;
k++;
}
elseif（compare（）,exp[k]）=='<'）{
（exp[k]）;
k++;
}
else{
nodea=（）;
（）;
nodeb=（）;
（）;
（calc（b,a））;
（）;
}
}
}
if（!
flage）
cout<else
cout<<"error"<}
return0;
}
15、多边形游戏
描述
一个多边形，开始有n个顶点。
每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。
所有边依次用整数从1到n编号。
现在来玩一个游戏，该游戏共有n步：
第1步，选择一条边，将其删除
随后n-1步，每一步都按以下方式操作：
（1）选择一条边E以及由E连接着的2个顶点v1和v2；
（2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。
最后，所有边都被删除，只剩一个顶点，游戏结束。
游戏得分就是所剩顶点上的整数值。
那么这个整数值最大为多少
输入
第一行为多边形的顶点数n（n≤20），其后有n行，每行为一个整数和一个字符，整数为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“*”（最后一个字符为最后一个顶点到第一个顶点间连边上
升级会员 