主题：[原创][讨论][交流]编程高手的超级训练题解析
vcacm
[专家分：1500] 发布于 2007-04-11 17:29:00
[code]
[[color=FF0000]注意： 这儿绝大部分的题目来源于信息学竞赛！
这些题目都是非常好的！如果大家能把这些题目做出来，那么可以说你
的编程能力达到了一定的水平！
关于这些题目的答案在GOOGLE/BAIDU上都能搜出来，但我：希望大家积极参 与讨论， 如果你把当中的题目做出来了可以贴出来，不过最好是要讲清自己的解题思路！
我也会把自己做出来了的题目以及解题思路发上来和大家一起交流！
如果你想学好编程，那么实践是很重要的！
我也是一个编程爱好者！[/color]
[color=FF00FF] My dream is to
develop a better than Linux, Windows more popular than the OS! [/color]
有啥问题，可以联系本人： 见我的签名档！
]
第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组 竞赛用时：3小时）
[color=FF00FF] 编号为： gcc_1[/color]
[/code]
[quote]
1．比赛安排（20分）
设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n ? 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n ? 1天内每个队都与不同的对手比赛。
例如n=2时的比赛安排：
队 1 2 3 4
比赛 1==2 3==4 一天
1==3 2==4 二天
1==4 2==3 三天
2．数制转换（20分）
设有一个字符串A$的结构为： A$=’m<n>p’
其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。
程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。
例如：A$=’48<10>8’
其意义为：将10进制数48，转换成8进制数输出。
输出结果为：48<10>=60<8>
3．挖地雷（30分）
在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。
V1 V 2 V3 V4 V5
例如：
[题目要求]
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
输入格式： N： （表示地窖的个数）
Ｗ1，W2，W3，……WN （表示每个地窖中埋藏的地雷数量）
A12…………… . A1N
A23…………..A2N
……..
AN-1 N
输出格式：
K1--K2--……….KV （挖地雷的顺序）
MAX （挖地雷的数量）
例如：
⑩--------⑧ ④-----⑦-------⑥
其输入格式为： 输出：
5 1 ?3 -4 -5
10，8，4，7，6 max=27
1 1 1 0
0 0 0
1 1
1
4．砝码称重（30分）
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：Total=N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
如输入：1_1_0_0_0_0 （注：下划线表示空格）
输出：TOTAL=3 表示可以称出1g，2g，3g三种不同的重量。
[/quote]
最后更新于：2007-04-17 06:46:00
回复列表 （共83个回复）
31 楼
vcacm [专家分：1500] 发布于 2007-04-13 10:33:00
[code]
====================gcc-4-3 ===========================
/* * * name : gcc-4-3.c * * *
* * * string_edit * * */
#include <stdio.h>
#include <string.h>
#define MAX_NUM 101
void output ( char *st , int len )
{
int j;
for(j= 1 ; j<= len ; j++)
printf("%c",st[j]) ;
printf("\n");
}
int Insert( int len, char *st,char x , char y)
{
int i,j,k ;
k = -1 ;
for(i=1 ;i<len ; i++)
if(st[i] == x)
{
k = i ;
}
if(k== -1 )
{
printf("wrong ! x is not in the string!\n");
return len ;
}
else
{
for(j=len ; j>=k ; j--)
st[j+1] = st[j] ;
st[k] = y ;
return len+1 ;
}
}
int Delete (int len, char *st , char x)
{
int i, j,k;
int flag = -1 ;
for(i= 1 ; i<len ; i++)
if(st[i] == x)
{
flag = i ;
break ;
}
if( flag == - 1)
{
printf("wrong ! the x is not in the string!\n");
return len ;
}
else
{
for(i= flag+1 ; i<=len ;i++)
st[i-1] = st[i] ;
return len-1 ;
}
}
void Instead (int len , char *st , char x, char y)
{
int i,j,k ;
int leap = -1 ;
for(i = 1 ;i<len ; i++)
if( st[i] == x)
{
leap = i ;
st[i] = y ;
}
if( leap == -1)
printf("\nsorry! the x is not in the string!\nPlease try again\n") ;
}
[/code]
32 楼
vcacm [专家分：1500] 发布于 2007-04-13 10:34:00
[code]
int main (int argc, char *argv[])
{
char d,x,y;
int i,j,k ;
char st[MAX_NUM];
char ch,c1,c2 ;
int len=0 ;
while((ch=getchar()) != '.')
{
st[++len] = ch ;
}
st[++len] = ch ;
getchar() ;
printf("\nPlease Input the message which you want to do!\n");
printf("\n=======(I , x , y) is to insert y before x!======\n");
printf("\n=======(D , x ) is to delete x in string!=====\n");
printf("\n=======(R, x , y) is let y instead of x in string!====\n");
while( (scanf("%c",&d )) != EOF && d !='#')
{
if( d == 'I')
{
while((scanf("%c",&c1))!=EOF && c1 ==' ')
;
x = c1 ;
while((scanf("%c",&c2))!=EOF && c2 ==' ')
;
y = c2 ;
printf("\n=======The before string !======\n");
output(st,len);
len = Insert (len,st,x,y) ;
printf("\n=======The end string !======\n");
output (st,len) ;
getchar () ;
}
else if( d == 'D' )
{
while( (scanf("%c",&c1)) != EOF && c1 == ' ')
;
x= c1 ;
printf("\n======The before string !======\n");
output(st,len);
len = Delete(len,st,x);
printf("\n=====The end string !========\n");
output (st,len) ;
getchar() ;
}
else if( d == 'R' )
{
while( (scanf("%c", &c1))!= EOF && c1 == ' ' )
;
while( (scanf("%c", &c2))!= EOF && c2 == ' ' )
;
x = c1 ;
y = c2 ;
printf("\n=====The before string !=======\n");
output(st, len );
Instead (len, st,x, y) ;
printf("\n=====The end string !=========\n");
output(st, len);
getchar() ;
}
else
printf("Your input message is wrong!") ;
printf("\nPlease input the message again, or enter the # to over!\n\n");
}
return 0 ;
}
[/code]
[/code]
33 楼
shena995800 [专家分：170] 发布于 2007-04-13 13:26:00
第一题答案~~我慢慢的一步一步的推过去,基本上明白了是整个复制过程了.
但是这两句我不知道怎么写出来,看的明白,自己不会写...
怎么确定的这些变量之间的关系呢?
rem 将表的右上角复制到左下角
a(i, j + (t - 1) * 2 * m - m) = a(i - m, j + (t - 1) * 2 * m)
rem 将表的左上角复制到右下角
a(i, j + (t - 1) * 2 * m) = a(i - m, j + (t - 1) * 2 * m - m)
CLS
DIM a(64, 64) AS INTEGER
INPUT "k="; k
n = 1
rem 产生球队数n
FOR i = 1 TO k
n = n * 2
NEXT i
rem 产生比赛安排表的第一行（球队的编号）
FOR i = 1 TO n
a(1, i) = i
NEXT i
c = n: m = 1
rem 整个合并过程分成k个阶段
FOR s = 1 TO k
c = c / 2
rem 这一阶段需要进行c次合并操作
FOR t = 1 TO c
FOR i = m + 1 TO 2 * m
FOR j = m + 1 TO 2 * m
rem 将表的右上角复制到左下角
a(i, j + (t - 1) * 2 * m - m) = a(i - m, j + (t - 1) * 2 * m)
rem 将表的左上角复制到右下角
a(i, j + (t - 1) * 2 * m) = a(i - m, j + (t - 1) * 2 * m - m)
NEXT j
NEXT i
NEXT t
m = m * 2
NEXT s
rem 输出比赛安排表（以题目要求的格式输出）
FOR i = 2 TO n
FOR j = 1 TO n
IF j < a(i, j) THEN PRINT j; "-"; a(i, j);
NEXT j
PRINT
NEXT i
END
34 楼
shena995800 [专家分：170] 发布于 2007-04-13 13:28:00
我初中高中的时候都没听说过这个的比赛,好奇怪哦~~难道是学校的原因?
35 楼
vcacm [专家分：1500] 发布于 2007-04-13 14:01:00
[quote]我初中高中的时候都没听说过这个的比赛,好奇怪哦~~难道是学校的原因?[/quote]
也许吧!
36 楼
vcacm [专家分：1500] 发布于 2007-04-13 14:04:00
[quote]第一题答案~~我慢慢的一步一步的推过去,基本上明白了是整个复制过程了.
但是这两句我不知道怎么写出来,看的明白,自己不会写...
怎么确定的这些变量之间的关系呢?
rem 将表的右上角复制到左下角
a(i, j + (t - 1) * 2 * m - m) = a(i - m, j + (t - 1) * 2 * m)
rem 将表的左上角复制到右下角
a(i, j + (t - 1) * 2 * m) = a(i - m, j + (t - 1) * 2 * m - m)
CLS
DIM a(64, 64) AS INTEGER
INPUT "k="; k
n = 1
rem 产生球队数n
FOR i = 1 TO k
n = n * 2
NEXT i
rem 产生比赛安排表的第一行（球队的编号）
FOR i = 1 TO n
a(1, i) = i
NEXT i
c = n: m = 1
rem 整个合并过程分成k个阶段
FOR s = 1 TO k
c = c / 2
rem 这一阶段需要进行c次合并操作
FOR t = 1 TO c
FOR i = m + 1 TO 2 * m
FOR j = m + 1 TO 2 * m
rem 将表的右上角复制到左下角
a(i, j + (t - 1) * 2 * m - m) = a(i - m, j + (t - 1) * 2 * m)
rem 将表的左上角复制到右下角
a(i, j + (t - 1) * 2 * m) = a(i - m, j + (t - 1) * 2 * m - m)
NEXT j
NEXT i
NEXT t
m = m * 2
NEXT s
rem 输出比赛安排表（以题目要求的格式输出）
FOR i = 2 TO n
FOR j = 1 TO n
IF j < a(i, j) THEN PRINT j; "-"; a(i, j);
NEXT j
PRINT
NEXT i
END
[/quote]
分治法呀!
我等下把解法贴出来,我现在也还没做好!
37 楼
vcacm [专家分：1500] 发布于 2007-04-13 17:15:00
[color=FFOOFF]GCC-1-1 /GCC-4-4 的参考答案:
方法: 分治法/递归
[/color]
[code]
/* * * name : gcc-1-1 /gcc-4-4 * * *
* * * * * *
循环赛日程安排问题
* * *==========================================* * */
#include <stdio.h>
#include <time.h>
#define MAX 101
int m[MAX][MAX] ;
int is_can (int data, int len)
{
int k ;
for(k= 1 ; k<=len ; k++)
if(data == m[k][1])
return 0 ;
return 1 ;
}
int main(int argc, char *argv[])
{
int i, j, k, h ,t;
clock_t end , begin;
//int m[MAX][MAX] ;
int n ,total = 1,go=0 ;
scanf("%d",&n );
begin = clock() ;
for( i =1 ; i<= n ; i++)
total *= 2 ;
go = n ;
n = total ; /* total ---> n */
for(i = 1 ; i<= n ; i++)
m[1] [i] = i ;
h = 1 ;
for( i = 1 ; i<=go ; i++)
{
n = n / 2 ;
for(j = 1 ; j<=n ; j++)
for(k= h+1 ; k<= 2*h ; k++)
for(t= h+1 ; t<= 2*h ; t++)
{
m[k][t+(j -1 )* h *2] = m[k-h][t+(j-1)*h*2-h ] ;
m[k][t+(j-1)*h*2 -h ] = m[k-h][t+(j-1)*h*2 ] ;
}
h *= 2 ;
}
/*for(i=1 ; i<= total ; i++)
{
for(j=1 ; j<= total ; j++)
printf("%d ",m[i][j]) ;
printf("\n");
}*/
for(i=2 ; i<= total; i++)
{
printf("\n\n======The %d day !======\n",i-1);
for(j=1 ; j<=total ; j++)
if(m[j][i] && is_can(m[j][i],j))
{
printf("%d == %d ",m[j][1], m[j][i]);
}
printf("\n\n");
}
end = clock() ;
printf("\n===The program has run %f seconds !==\n",(double)(end-begin)/1000);
return 0 ;
}
[/code]
38 楼
Rick0ne [专家分：1490] 发布于 2007-04-13 18:44:00
那个FVWM是做什么的?
39 楼
CLO [专家分：2000] 发布于 2007-04-13 20:34:00
[quote]那个FVWM是做什么的?[/quote]
LINUX和BSD……下一个很出名的 窗口管理器
40 楼
Rick0ne [专家分：1490] 发布于 2007-04-13 22:25:00
[quote][quote]那个FVWM是做什么的?[/quote]
LINUX和BSD……下一个很出名的 窗口管理器[/quote]
Windows上不能用咯?
我来回复
您所在位置：