注册 登录
编程论坛 C++教室

[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战

野比 发布于 2007-06-16 11:57, 48944 次点击

偶然从朋友那里搞到的, 名字是<<C++入门题>>
题目都相当的经典. 还有不少是NOI的考试题.
1 - 20题作为热身(见2楼), 越往后越难, 完整版(76道)请到1楼楼底下载.

请解决问题后, 不要吝惜你的才华, 把解题方法跟贴, 大家共同学习提高.

统计时间: 2007-10-10 19:29[/quote]

目前已完成题目(按发帖时间先后排序)

题号 完成人 楼层
---------------------------------------------
2 百年不亮 3
5 HCL 4
20 aipb2007 5,6
17 游乐园/aipb2007 18/20
6 HCL 26,27
16 jiaju111 33 讨论完成, 未编程
11 aipb2007 46
75 HJin 48 不符题干, 参考
49 HJin 49
48 HJin 61
10 HJin 62 * 218楼(blueboy82006),236楼(远去的列车)修改
13 HJin 63
17 HJin 65
1 HJin 67
3 tianma8778 69 有缺陷, 供参考
24 HJin 71
1 kai 77 另一种解法
2 kai 79 数字电路分析法
4 HJin 80
3 kai 81 # With analysis
19 HJin 83
3 laigaoat2005 69
37 HJin 103 162楼补充说明(smartwind)
67 HJin 104
74 HJin 105
4 wfpb 107 * + (kai指出, 见117楼)
3 smartwind 108 *
9 smartwind 109 *
8 wfpb 110 *
3 zkkpkk 111 *
12 wfpb 112 *
75 smartwind 113 *
37 weishj 114 *
41 zkkpkk 115 * 166楼改进(smartwind)
6 zkkpkk 118 * 130楼补充蛇形填数
65 weishj 124 *
14 huozoo 126 @ 正确
7 zkkpkk 137 *
76 HJin 138 *
4 天空の城 140 *
58 HJin 141 *
9 zkkpkk 142 *
13 zkkpkk 144 *
57 HJin 147 *
53 HJin 148 *
22 HJin 149 *
43 zkkpkk 150 *
21 HJin 152 *
31 smartwind 160 * 164楼补充(HJin) 165楼补充(smartwind)
34 smartwind 161 # 分析
45 smartwind 172 *
2 zhchchqihu 194,193 * 2种方法
3 freshman42 196 *
? blueboy82006 208 *
2 卧龙孔明 209,210 * 2种方法
1 hkice 211 *
5 hkice 212 *
3 miaomiao0403 214 *
10 ml232528 215 * 指出62楼10题错误
55 远去的列车 220 *
48 远去的列车 222 *
14 huozoo 223 * 解答者本人不确定
2,3 xjlsgcjdtc 228,229 *
3 qq598369 230 *
3 远去的列车 232 *
3 曦木 233 *
6 远去的列车 234 *
7 海子星竹 239 *
3 且行且珍惜 240 *


注:
* 未测试 (Not tested)
@ 已测试 (Tested)
+ Bug
# 无源代码 (No code)

完整版(76道)下载[attach]22592[/attach]


[此贴子已经被作者于2007-10-10 19:29:50编辑过]

288 回复
#252
poppylx2007-10-31 01:01

关于第一题 说说自己的算法
首先(E+G+G)%10 = E 这样可以推出 G 为 0 与 5 中的一个。
(D+F+F+个位进位)% 10 = D 可以得出 G = 0, F = 5。
再看看A与X,A+ 千位进位 =X,这里的千位进位必定为1, 得出A+1=X,A与X是两个连续的数。
同时可以看出 B+ 百位进位 >10
再看看C+2D, 由于B与Y的关系所以C+2D必定有进位,如果进位为1,则B=9,Y=0,与前面的的推导冲突。
所以进位肯定为2(不可能为3),则B=9,Y=1。
这样10个数中还剩下2 3 4 6 7 8 六个数。
再看百位上 2D+C +1(十位进位),必须进位2,所以2D+C +1 >= 20,又因为 Z!=0 && Z!=1,所以 2D+C +1 >=22.
=> D与C的平均数必须大于等于7
根据前面的A与X连续, 所以Z必定为2或4. 那么2D+C等于21或者23, 所以C必定为一素数, 所以C = 7.
则2D+7=21 或2D+7=23 => 2D=14 或 2D=16. 所以D=8.
只有最后一个E与6了,所以E=6.
证毕.

这个题似乎没必要写程序.

#253
jonc2007-10-31 17:32

做了最简单的
程序不雅观
大家见笑了

代码:
#include <iostream>
#include<iomanip>
using namespace std;
int main()
{
const int num=19;//选择N
int i,j;
char array[num][num];

for(i=0;i<num;i++)//初始化数组
for(j=0;j<num;j++)
{

if((i==0)||(i==num-1)||(j==0)||(j==num-1))
array[i][j]='T';
else
if((i==1)||(i==num-2)||(j==1)||(j==num-2))
array[i][j]='J';
else
if((i==2)||(i==num-3)||(j==2)||(j==num-3))
array[i][j]='1';
else
if((i==3)||(i==num-4)||(j==3)||(j==num-4))
array[i][j]='2';
else
if((i==4)||(i==num-5)||(j==4)||(j==num-5))
array[i][j]='3';
else
if((i==5)||(i==num-6)||(j==5)||(j==num-6))
array[i][j]='4';
else
if((i==6)||(i==num-7)||(j==6)||(j==num-7))
array[i][j]='5';
else
if((i==7)||(i==num-8)||(j==7)||(j==num-8))
array[i][j]='6';
else
if((i==8)||(i==num-9)||(j==8)||(j==num-9))
array[i][j]='7';
else
if((i==9)||(i==num-10)||(j==9)||(j==num-10))
array[i][j]='8';
else
if((i==10)||(i==num-11)||(j==10)||(j==num-11))
array[i][j]='9';//最多打印到9


}
for(i=0;i<num;i++)//打印
{
for(j=0;j<num;j++)
cout<<setw(1.5)<<array[i][j]<<" ";
cout<<""<<endl;
}


return 0;
}

#254
jonc2007-10-31 22:02

第四题
在N行N列的数阵中, 数K(1〈=K〈=N)在每行和每列中出现且仅
出现一次,这样的数阵叫N阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
编一程序,从键盘输入N值后,打印出所有不同的N阶拉丁方阵,并统计个数。

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

#include<iostream>
#include<iomanip>
using namespace std;
void linta(int );
int main()
{
int num;
cout<<"input the num(min is 1):"
<<endl;
cin>>num;//input the number
linta(num);//call the function
return 0;
}
void linta(int num)
{
int i,j,inta=0;
for(i=1;i<=num;i++)//print the lation data
for(j=1;j<=num;j++)
{
if((inta+j)%num==0)
cout<<setw(3)<<num;
else
cout<<setw(3)<<(inta+j)%num;
if(j==num)
{
inta++;
cout<<endl;
}

}

}

#255
poppylx2007-11-01 01:49

/*
2. A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些
人参加了竞赛:

(1)A参加时,B也参加;

(2)B和C只有一个人参加;

(3)C和D或者都参加,或者都不参加;

(4)D和E中至少有一个人参加;

(5)如果E参加,那么A和D也都参加。

*/

/*
分析: 关于条件4与条件5很有意思.
如果D不参加,则E肯定参加.
但如果E参加了,则D肯定参加.
所以可以得出D时肯定参加的.
再根据条件2,3, 可以得到B与C是否参加.
这样只有A与E是不确定的.
使用穷举法, 只要满足条件1与5,便可得到结果.

昨天做了第一题,完全用笔算,今天做第二题时才感觉到昨天误解了出题者的意思.
*/



#include <iostream>
using namespace std;

const int A = 0;
const int B = 1;
const int C = 2;
const int D = 3;
const int E = 4;
const int COUNT = 5;

void PrintResult( bool bArray[], int iCount ); //输出结果


int main()
{
bool bStudent[ COUNT ];

bStudent[D] = true; //条件4与5
bStudent[C] = bStudent[D] ; //条件3
bStudent[b] = !bStudent[C]; //条件2
for( int i = 0; i < 2 ; ++i )
{
bStudent[A] = i;
for( int j = 0; j < 2; ++j )
{
bStudent[E] = j;
if( (bStudent[A] == false || (bStudent[A] == true && bStudent[b] == true)) //条件1
&& ( bStudent[E] == false || (bStudent[E] == true && bStudent[A] == true)) ) //条件5
{
PrintResult( bStudent, COUNT );
}
}
}

cin.get();
return 0;
}

//输出结果
void PrintResult( bool bArray[], int iCount )
{

for( int i = 0; i < iCount; ++i)
{
if( bArray[i] == true )
{
cout << (char)(i+'A') << ": Attend" << endl;
}
else
{
cout << (char)(i+'A') << ": Not attend" << endl;
}
}
}

#256
jonc2007-11-01 08:46

5. 输入一个十进数,将其转换成 N 进制数(0<N<=16)。

#include<iostream>
#include<iomanip>
using namespace std;
void convert(int ,int,int[],int);
int main()
{
int num,make_num,sign=1;
int array[32]={0};//,array[32]={0}
cout<<"input the num and the make_num:";
cin>>num
>>make_num;//input the number
convert(num,make_num,array,32);//call the functnio
cout<<"the "
<<num
<<" convert into "
<<make_num
<<" is : "<<endl;
for(int i=31;i>=0;i--)
{
if(!(array[i]==0&&sign==1))
{
if(array[i]==65)
cout<<"A";
else if(array[i]==66)
cout<<"B";
else if(array[i]==67)
cout<<"C";
else if(array[i]==68)
cout<<"D";
else if(array[i]==69)
cout<<"E";
else if(array[i]==70)
cout<<"F";
else
cout<<array[i];
}
}
return 0;
}
void convert(int num,int make_num,int array[],int size)
{
int Remainder=num,i=0,mold;
while(Remainder!=0)
{
mold=Remainder%make_num;

if(mold==10)
array[i++]='A';
else if(mold==11)
array[i++]='B';
else if(mold==12)
array[i++]='C';
else if(mold==13)
array[i++]='D';
else if(mold==14)
array[i++]='E';
else if(mold==15)
array[i++]='F';
else
array[i++]=mold;


Remainder/=make_num;

}
}

#257
jonc2007-11-01 11:46

9. 四人玩火柴棍游戏,每一次都是三个人赢,一个人输。输的人要按赢者手中的火柴
数进行赔偿,即赢者手中有多少根火柴棍,输者就赔偿多少根。现知道玩过四次后,
每人恰好输过一次, 而且每人手中都正好有16根火柴。问此四人做游戏前手中各有
多少根火柴? 编程解决此问题。
#include<iostream>
#include<iomanip>
using namespace std;
void game(int[],int);
int main()
{
int array[4]={16,16,16,16};//初始化
static int count=0;
cout<<setw(40)
<<"采用递归调用的方法进行解析\n"
<<setw(35)
<<"设定他们输的顺序为:\n"
<<"----------------------------------------------\n"
<<setw(4)
<<" |i"
<<setw(10)
<<"array[0]"
<<setw(10)
<<"array[1]"
<<setw(10)
<<"array[2]"
<<setw(10)
<<"array[3]"
<<endl;
for(int i=4;i>=0;i--)
{

cout<<setw(3)
<<"|"
<<i;

for(int j=0;j<4;j++)
{
cout<<setw(10)
<<array[j];
}
if(count++!=4)
game(array,4);
cout<<endl;
}
cout<<"the result is the last line\n"
<<"----------------------------------------------\n"
<<endl;
return 0;
}
void game(int arr[],int num)
{
static i=1;
int j,array[3]={0};

switch (i)
{
case 1:
{
for(j=0;j<num;j++)
if(j!=3)
{
arr[j]/=2;
array[j]=arr[j];
}
else
arr[j]=(arr[j]+array[0]+array[1]+array[2]);
break;
}
case 2:
{
for(j=0;j<num;j++)
arr[j]/=2;
arr[2]=64-arr[0]-arr[1]-arr[3];
break;
}
case 3:
{
for(j=0;j<num;j++)
arr[j]/=2;
arr[1]=64-arr[0]-arr[2]-arr[3];
break;
}
case 4:
{
for(j=0;j<num;j++)
arr[j]/=2;
arr[0]=64-arr[1]-arr[2]-arr[3];
break;

break;
}
default:
cout<<"you can't get here"<<endl;
break;
}
i++;

}

#258
jonc2007-11-01 15:03

8.
/* 输入两个正整数num_x,num_y,将num_x,num_y化为二进制数,然后将这两个二进制数作二进
制加法运算,再将结果化为十进制数输出。

*/
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
void convert(int ,int[],int);
void array_add(int[],int[],int[],int);
int convert2(int[],int);
int main()
{
int num_x,num_y,sign=1;
const int max=20;
int array_x[max]={0},array_y[max]={0},array_sum[max]={0};//,array_x[32]={0}

cout<<"input the num_x & num_y:\n\r";//input the num_x and num_y
cin>>num_x
>>num_y; //input the number

convert(num_x,array_x,max);//call the function

cout<<"the <"<<num_x<<"> convert into "<<"2"<<" is : ";//print the num_x convert into 2
for(int i=max-1;i>=0;i--)
{
if(!(array_x[i]==0&&sign==1))
{
cout<<array_x[i];
sign=0;
}
}
cout<<endl;

convert(num_y,array_y,max);//call the function
sign=1;
cout<<"the <"<<num_y<<"> convert into "<<"2"<<" is : ";//print the num_x convert into 2
for(int j=max-1;j>=0;j--)
{
if(!(array_y[j]==0&&sign==1))
{
cout<<array_y[j];
sign=0;
}
}
cout<<endl;
sign=1;
array_add(array_x,array_y,array_sum,max);
cout<<"the sum is: ";//print the num_x convert into 2
for(int p=max-1;p>=0;p--)
{
if(!(array_sum[p]==0&&sign==1))
{
cout<<array_sum[p];
sign=0;
}
}

cout<<endl;
cout<<"the sum in the way of 10 is:"<<convert2(array_sum,max)<<endl;
return 0;
}
void convert(int num_x,int array_x[],int size)//change into 2
{
int Remainder1=num_x,i=0;
while(Remainder1!=0)
{
array_x[i++]=Remainder1%2;
Remainder1/=2;
}
}
void array_add(int arr1[],int arr2[],int arr3[],int max)//the sum function
{
int i,j;
for(i=0,j=0;i<max;)
{
arr3[i]=arr1[i]+arr2[i]+arr3[i];
if(arr3[i]==2)
{
arr3[i]=0;
i++;
arr3[i]=1;
}else if(arr3[i]==3)
{
arr3[i]=1;
i++;
arr3[i]=1;
}
else i++;


}
}
int convert2(int arr[],int max)
{
int data=0,i;

for(i=0;i<max;i++)
{
data+=arr[i]*pow(2,i);
}
return data;
}

#259
六道2007-11-01 23:13

第6题:

倒排数组
#include<iostream.h>
#include<math.h>
#include<iomanip.h>
void main()
{
int a[100],b[10][10];
int i,j,k,n;
cout<<"please input a number:";
cin>>n;
for(i=0;i<n*n;i++)
a[i]=i+1;
k=n*n-1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++,k--)
b[i][j]=a[k];
}

cout<<"倒排数组:\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<b[i][j];
cout<<endl;
}
}

回转数组

#include<iostream.h>
#include<iomanip.h>
void main()
{
int s[100],a[10][10];
int i,j,n;
static k;
cout<<"please input a number:";
cin>>n;
for(i=0;i<n*n;i++)
s[i]=i+1;

for(i=0;i<=n/2;i++)
{
for(j=i;j<n-i;j++)
{
a[j][i]=s[k];
k++;
}
for(j=i+1;j<n-i;j++)
{
a[n-i-1][j]=s[k];
k++;
}
for(j=n-2-i;j>=i;j--)
{
a[j][n-1-i]=s[k];
k++;
}
for(j=n-2-i;j>=i+1;j--)
{
a[i][j]=s[k];
k++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<a[i][j];
cout<<endl;
}
}

#260
六道2007-11-01 23:25

第5题:
#include<stdio.h>
main()

{
int i=0,base,n,j,num[20];
printf("enter data that will be converted\n");
scanf("%d",&n);
printf("enter base\n");
scanf("%d",&base);
j=n;
do
{
i++;
num[i]=n%base;
n=n/base;
} while(n!=0);
printf("the data %d has been converted into the %d--base data:\n",j,base);
for(;i>=0;i--)
printf("%d",num[i]);
printf("\n");
}

#261
yoapple2007-11-01 23:28
菜鸟啊
#262
zjl1382007-11-20 16:49

呵呵,努力中!!!

#263
liujianlin2007-11-20 18:49

能做出来都是牛人,我们是超菜鸟级别的,看来要努力了,题目都看不懂,小学文花,能学编程吗???

#264
中学者2007-11-21 17:50
准备下学期再努力攻克算法~
#265
qlc002007-12-01 11:04
原帖由 [bold][underline]jiaju111[/underline][/bold] 于 2007-6-17 17:10 发表 [url=http://bbs.bc-cn.net/redirect.php?goto=findpost&pid=870399&ptid=147967][/url]
以下是引用野比在2007-6-17 16:17:55的发言:
好像有些不对劲.. 这里"若不平衡(如果仍然是左边重)则是b,或c偏重 / (如果是左边轻)则是d偏轻", 没有考虑到"e或f偏轻"的情况...因为不能保证一定会把偏轻的那一个当成d拿到 ...

  我觉得左右各放四个,第一步先判断那边重或轻,可以取出4个(其中有个假的)
第二步就是在这四个中各取两个进行比较,又可以排除两个
第三步就是在剩下的两个中比较,然后就出结果了!
也只用了三次啊
#266
HACKER20082007-12-03 09:20
76道题怎么下载呢?
楼主,这76道题是不是不能下载呀?
#267
xijunhua2007-12-03 19:44
题目在哪下啊,下下来慢慢研究下.
要不楼主发我一份   
邮箱: [email]xijunhua4321@[/email] 或 [email]313156507@[/email]
#268
HACKER20082007-12-03 21:02
踢,我的题
麻烦楼主把题上传上无,上面的那个无法下载!
#269
china25qd2007-12-04 16:06
34题谁会?
#270
_woodpecker2008-05-25 17:27
谢谢楼主,这些题目太好了!
#271
cl3784050852008-07-08 20:32
tttttttt
tttttttttttttttttttttttttttt
#272
mooshin2008-07-13 07:53
lz怎么下载不了啊
#273
xlin1033xl2008-09-06 10:54
先顶
#274
wojiaozifan2008-09-06 12:23
为什么不能下载,能说明一下吗
#275
守鹤2008-09-06 22:02
我来参与下
第二题从算法的效率上看,还有跟简捷地方法,采用二进制地方法
即:
string  s[]={"参加比赛",“不参加比赛”};
 for(int i=0;i<32;i++)
{  
    A=(i&16)>>4;
    B=(i&8)>>3;
    C=(i&4)>>2;
    D=(i&2)>>1;
    E=i&1;
c1=A||(!B);
c2=B/\C;
c3=!(C/\D);
c4=D||E;
if(E==1)
  c5=A&&D;
else
  c5=1;
cout<<"A"<<s[A];
.....

}
}
#276
stvdent2008-10-05 09:14
新手路过...来学习..可惜下载不了那写题目...
有无人可以发给我..
304329337@
#277
blueboy820062008-10-05 17:54
始终觉得这样的好贴,应该多搞一些...
现在看了,还能想到当初的许多许多...
#278
stvdent2008-10-06 13:34
蛮好的..
对我们新手来说还可以参考参考
#279
rcbblgy2008-10-06 18:53
附件失效了????
#280
wyxpop1632008-10-08 14:02
这贴可以长期么??现在水平不够,等水平够了再做
#281
philip2008-10-12 16:41
回复 25# aipb2007 的帖子
16题,最少的比较次数应该是3次。
首先将8枚硬币,每边4枚放在天平上,将(重)轻的那一边取出,再分成每边两枚放在天平上。将(重)轻的那一边取出,再分成每边1枚放在天平上。(重)轻的那一枚就是了。
#282
hustini2008-10-18 16:56
到哪里下载呀?
#283
cppzh2010-09-06 14:26
14.递归算法,哪位大侠改下数组声明,试试能否编译
Void main()
{Int n=0;
char *a=null;
cin>>n;
A=new char[n*2];
Void print(char a[],int n)
Void init(char a[],int n)
Void reverse(char a[],int n)
Init(a,n);
Reverse(a,n,n);
}
Void init(a,n)
{Char a[n*2];
For(i=0;i<n;i++) a[i]=’O’;
For(i=-n;i<0;i++) a[i]=’*’;}

Void print(a,n)
{Char a[n*2];
For(i=-n;i<n;i++) cout<<a[i];}

Void reverse(a,n,m)
{Char a[n*2],b[n*2];int i,n,n2
If(n<0) return;
elseif(n=1) print(a,m);
else
reverse(a,n--);
for(i=-n;i<n;)
{char t=a[i];a[i]=a[++i];a[i++]=t;
Print(a,m);}
}

#284
cppzh2010-09-06 14:33
哪位有题发一下吧。zhhhychen@
#285
amwjgigql2010-09-09 00:33
第16题,最少三次,最多四次,
我有二种想法:8枚硬币分为四组,ab,cd,ef,jh.
第一次,左ab跟右cd,有三种情况,平衡,左重,左轻。
       如果平衡 第二次,左ab,右ef,同样有三种情况。
       如果平衡 第三次,左ab,左 jh.这时只有二种情况了,左重或左轻
       第四次,如果第三次是左重,说明假币较真币轻,左放j,右放上h.轻的那个是假币。
       第四次,如果第三次是左轻,说明假币较真币重,左放j,右放h,重的那个是假币。
如果第一次是平衡
     第二次,左放ab,右放ef,会有三种情况同上如果平衡上面已经讲了,。
    如果左重,说明ef里有假币且较真币轻。
     第三次,左放e,右放f,轻的为假币。
     第二次如果是左轻,说明ef里有假币且较真币重。
     第三次左放e,右放f,重的为假币。
     
如果第一次是左重(说明efjh是真币)
    说明第一次的二组里有一组里有假币。(且如果假币在ab内,说明假币较重,反之较轻。)
   第二次,左放ef,右放ab,只会有二种情况,平衡,左轻(因为第一次是左重也就是ab重所以ef不可能比ab重)。
    如果平衡,说明假币在cd内且较轻。
  第三次,左放c,右放d,轻的为假币。
  第二次如果左轻,说明假币在ab内
   第三次,左放a,右放b轻的为假币,
如果第一次是左轻(说明efjh是真币)。
   说明第一次的二组内有一组假币。(且如果假币在ab内,说明假币较轻,反之较重。)
   第二次,左放ef,右放ab只会有二种情况,平衡,左重。
   如果平衡,说明 cd内有假币且较重。
   第三次,左放c,右放d重的为假。
   第二次若左重,说明ab内有假币,且较轻
   第三次左放a,右放b,轻的为假。
#286
jerry2782010-11-21 20:59
szdfd
#287
abcdef123ab2013-01-24 19:58
回复 126楼 huozoo
#include "stdafx.h"
#include<iostream>
using namespace std;

int main(){
    const int n=10;
    char t,a[n];

    for( int i = 0; i < n/2; i++ )
        a[i] = '*';
    for( int i = n/2; i < n; i++ )
        a[i] = '0';

    cout << "原始数据:" << endl;
    for( int i = 0; i < n;i++ )
        cout << a[i] << " ";
    cout << endl;

    cout << "变换过程:" << endl;
    for( int i = n/2; i < n-1; i++ ){
        //cout << i << endl;
        for( int j = i; j > 0 && a[j-1] != '0'; j--){
            t = a[j];
            a[j] = a[j+1];
            a[j+1] = t;
            for( int k = 0; k < n; k++ )
                cout << a[k] << " ";
            cout << endl;
        }
    }

    system("pause");
    return 0;
}
#288
jacobwj2013-01-28 21:17
研究研究
123456