OpenJudge算法设计与分析习题解答.docx
《OpenJudge算法设计与分析习题解答.docx》由会员分享，可在线阅读，更多相关《OpenJudge算法设计与分析习题解答.docx（43页珍藏版）》请在冰点文库上搜索。
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）{//用longlong存储，避免结果超过int的范围
if（lef>=righ）{
return;
}
intmid=lef+（righ-lef）/2;
reSeq（seq,lef,mid）;
reSeq（seq,mid+1,righ）;
inttotalSize=righ-lef+1;
longlongtmp[totalSize];
intn=lef;
intm=mid+1;
inti=0;
while（n<=mid||m<=righ）{
if（m>righ||（n<=mid&&seq[n]<=seq[m]））{
tmp[i++]=seq[n++];
}else{
tmp[i++]=seq[m++];
ans+=mid-n+1;
}
}
i=lef;
for（intj=0;jseq[i++]=tmp[j];
}
}
voidreSeqNum（longlong*seq,intn）{
reSeq（seq,0,n-1）;
}
intmain（）{
scanf（"%d",&N）;
for（inti=0;iscanf（"%ld",&seq[i]）;
}
ans=0;
reSeqNum（seq,N）;
printf（"%ld\n",ans）;
return0;
}
8、Grey码
描述
Grey码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。
例如长度为23的格雷码为（000,001,011,010,110,111,101,100）。
设计分治算法对任意的n值构造相应的Grey码。
输入
每个元素的长度值n。
输出
将所有相应的Grey码分行输出，即每一行输出一个二进制位串。
样例输入
3
样例输出
000
001
011
010
110
111
101
100
源代码：
#include
#include
intpower（intbase,intn）
{
inti,p=1;
for（i=1;i<=n;++i）
p=p*base;
returnp;
}
voidGrey（inta,intb,int**arr,intk）{
if（b==1）{
*（（int*）arr+k*0+0）=0;
//arr[0][0]=0;
*（（int*）arr+k*1+0）=1;
//arr[1][0]=1;
return;
}else{
for（inti=0;i*（（int*）arr+k*i+b-1）=0;
//arr[i][b-1]=0;
*（（int*）arr+k*（a-i-1）+b-1）=1;
//arr[a-i-1][b-1]=1;
}
Grey（a/2,b-1,（int**）arr,k）;
for（inti=a/2;ifor（intj=0;j*（（int*）arr+k*i+j）=*（（int*）arr+k*（a-i-1）+j）;
//arr[i][j]=arr[a-i-1][j];
}
}
}
}
intmain（）{
intn;
scanf（"%d",&n）;
intm=（int）power（2,n）;
intarr[m][n];
Grey（m,n,（int**）arr,n）;
for（inti=0;ifor（intj=n-1;j>=0;j--）{
printf（"%d",arr[i][j]）;
}
printf（"\n"）;
}
getchar（）;
return0;
}
9、循环比赛
描述
设有N个选手的循环比赛。
其中N=2^M（2的M次方），要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
输入
M
输出
表格形式的比赛安排表
样例输入
3
样例输出
12345678
21436587
34127856
43218765
56781234
65872143
78563412
87654321
提示
M的大小不会超过8
源代码：
#include
#include
voidarrange（intk,int**a,intn）{
intt=1,temp=1;
*（（int*）a+k*0+0）=1;
//a[0][0]=1;
while（t<=n）{
for（inti=0;ifor（intj=0;j*（（int*）a+k*i+j+temp）=*（（int*）a+k*i+j）+temp;
//a[i][j+temp]=a[i][j]+temp;
}
}
for（inti=0;ifor（intj=0;j*（（int*）a+k*（i+temp）+j）=*（（int*）a+k*i+j+temp）;
//a[i+temp][j]=a[i][j+temp];
*（（int*）a+k*（i+temp）+j+temp）=*（（int*）a+k*i+j）;
//a[i+temp][j+temp]=a[i][j];
}
}
temp*=2;
t++;
}
}
intmain（）{
intn;
scanf（"%d",&n）;
intk=1;
for（inti=0;ik=2*k;
}
inta[k][k];
arrange（k,（int**）a,n）;
for（inti=0;ifor（intj=0;jprintf（"%d",a[i][j]）;
}
printf（"\n"）;
}
getchar（）;
return0;
}
10、棋盘覆盖问题
描述
在一个2k×2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘。
显然，特殊方格在棋盘中出现的位置有4k种情形，因而有4k种不同的棋盘，如图1所示是k=2时16种棋盘中的一个。
在棋盘覆盖问题中，要求用图2所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。
输入
对每一个测试例有2行，第一行是k（1<=k<=10），第二行是特殊方格所在的位置坐标x,y（0<=x，y<1024）。
输出
边长为2的k次方的方阵，特殊方格的编号为0，所有L型骨牌从1开始编号，数据之间的间隔是空格。
样例输入
2
01
样例输出
2033
2213
4115
4455
提示
按分治策略进行算法设计。
#include
#include
intt=0;
intboard[100][100];
voidChessBoard（inttr,inttc,intdr,intdc,intsize）{
ints,t1;
if（size==1）return;
t1=++t;
s=size/2;
if（drChessBoard（tr,tc,dr,dc,s）;
}else{
board[tr+s-1][tc+s-1]=t1;
ChessBoard（tr,tc,tr+s-1,tc+s-1,s）;
}
if（dr=tc+s）{
ChessBoard（tr,tc+s,dr,dc,s）;
}else{
board[tr+s-1][tc+s]=t1;
ChessBoard（tr,tc+s,tr+s-1,tc+s,s）;
}
if（dr>=tr+s&&dcChessBoard（tr+s,tc,dr,dc,s）;
}else{
board[tr+s][tc+s-1]=t1;
ChessBoard（tr+s,tc,tr+s,tc+s-1,s）;
}
if（dr>=tr+s&&dc>=tc+s）{
ChessBoard（tr+s,tc+s,dr,dc,s）;
}else{
board[tr+s][tc+s]=t1;
ChessBoard（tr+s,tc+s,tr+s,tc+s,s）;
}
}
intmain（）{
intn,size=1;
scanf（"%d",&n）;
for（inti=0;isize=size*2;
}
intdr,dc;
scanf（"%d%d",&dr,&dc）;
ChessBoard（0,0,dr,dc,size）;
for（inti=0;ifor（intj=0;jprintf（"%d",board[i][j]）;
}
printf（"\n"）;
}
getchar（）;
return0;
}
11、输油管道问题
描述
某石油公司计划建造一条由东向西的主输油管道。
该管道要穿过一个有n口油井的油田。
从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。
如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?
证明可在线性时间内确定主管道的最优位置。
要求给定n口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。
输入
由文件提供输入数据，文件第一行是油井数n，1<=n<=10000。
接下来n行是油井的位置，每行两个整数x和y，-10000<=x,y<=10000。
输出
将结果输出到文件中，文件第一行中的数是油井到主管道之间的输油管道最小长度总和。
样例输入
5
12
22
升级会员 