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

楼主

问题点数：0 回复次数：288

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

偶然从朋友那里搞到的, 名字是<<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编辑过]

搜索更多相关主题的帖子: 竞赛题　练习题　高难度　 NOI　

第 2 楼

得分:0

No.1 - 20 热身题

1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不
D F G 同字母。编程求出这些数字并且打出这个数字的
+ D F G 算术计算竖式。

───────

X Y Z D E

2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
人参加了竞赛：

（１）Ａ参加时，Ｂ也参加；

（２）Ｂ和Ｃ只有一个人参加；

（３）Ｃ和Ｄ或者都参加，或者都不参加；

（４）Ｄ和Ｅ中至少有一个人参加；

（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。

3. 打印一个 N*N 的方阵，Ｎ为每边Ｎ＝１５打印出下面图形
字符的个数（３＜Ｎ＜２０）, 要求最 TTTTTTTTTTTTTTT
外一层为"T", 第二层为"J", 从第三层 TJJJJJJJJJJJJJT
起每层依次打印数字 1,2,3,... TJ11111111111JT
（右图以Ｎ为１５为例） TJ12222222221JT
TJ12333333321JT
TJ12344444321JT
TJ12345554321JT
TJ12345654321JT
TJ12345554321JT
TJ12344444321JT
TJ12333333321JT
TJ12222222221JT
TJ11111111111JT
TJJJJJJJJJJJJJT
TTTTTTTTTTTTTTT

4. 在Ｎ行Ｎ列的数阵中, 数Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出现且仅
出现一次，这样的数阵叫Ｎ阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
编一程序，从键盘输入Ｎ值后，打印出所有不同的Ｎ阶拉丁方阵，并统计个数。

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

5. 输入一个十进数，将其转换成 N 进制数（0<N<=16)。
6. 矩阵中填数. 当给出 N*N 的矩阵，要求用程序填入下列形式的数：

① 倒填，例如N=5 ② 蛇形填数 ③ 回转填数

┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│25│24│23│22│21│ │ 1│ 3│ 4│10│11│ │ 1│16│15│14│13│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│20│19│18│17│16│ │ 2│ 5│ 9│12│19│ │ 2│17│24│23│12│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│15│14│13│12│11│ │ 6│ 8│13│18│20│ │ 3│18│25│22│11│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│10│ 9│ 8│ 7│ 6│ │ 7│14│17│21│24│ │ 4│19│20│21│10│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ 5│ 4│ 3│ 2│ 1│ │15│16│22│23│25│ │ 5│ 6│ 7│ 8│ 9│
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘

7. 读入一行文本，包含若干个单词（以空格间隔，％结尾）。将其中以 A 开头的
单词与以 N 结尾的单词，用头尾交换的办法予以置换。

8. 输入两个正整数Ｘ，Ｙ，将Ｘ，Ｙ化为二进制数，然后将这两个二进制数作二进
制加法运算，再将结果化为十进制数输出。

9. 四人玩火柴棍游戏，每一次都是三个人赢，一个人输。输的人要按赢者手中的火柴
数进行赔偿，即赢者手中有多少根火柴棍，输者就赔偿多少根。现知道玩过四次后，
每人恰好输过一次，而且每人手中都正好有１６根火柴。问此四人做游戏前手中各有
多少根火柴? 编程解决此问题。

10. 如图１所示，编写程序计算 ┎┰┰┰┰┰┰┰┰┰┒
大大小小正方形共有多少？当最小 ┠╂╂╂╂╂╂╂╂╂┨
正方行边长为１时，它们的总面积 ┠╂╂╂╂╂╂╂╂╂┨
共为多少？ ┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┖┸┸┸┸┸┸┸┸┸┚
11. 巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之
和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。

12. 下图是一个集装箱仓库，阴影部分表示有集装箱存放不能通过，无阴影处为临时通
道。当有人要从入口处到达出口处时，必须寻找可通过路线，请你找出可完成这个过程
的最方便（即用最短路线）到达出口处的路径。

┎┰┰┰入口┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┒
┠╂╂╂──╂╂╂╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂╂┸┸╂╂╂┨
┠╂╂╂──╂┸┸╂──╂┰┰╂┰┰╂──╂╂╂╂──╂╂╂┨
┠╂╂╂──╂┰┰╂┰┰╂╂╂╂╂╂╂──╂┸┸╂──╂╂╂┨
┠╂╂╂──╂╂╂╂╂╂╂╂╂╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂┨
┠╂╂╂──╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂┨
┠╂╂╂──╂┰┰╂┰┰╂┰┰╂──╂┰┰╂──╂┰┰╂╂╂┨
┠╂╂╂──╂╂╂╂╂╂╂╂╂╂──╂╂╂╂──╂╂╂╂╂╂┨
┠╂╂╂──╂╂╂╂┸┸╂┸┸╂──╂╂╂╂──╂┸┸╂╂╂┨
┠╂╂╂──╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂╂┰┰╂──╂╂╂┨
┖┸┸┸──┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸出口┸┸┸┚

13. 有N个硬币（N为偶数）正面朝上排成一排，每次将 N-1 个硬币翻过来放在原位
置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把
翻币的最简过程及翻币次数打印出来（用＊代表正面，O 代表反面）。

14. 有黑白棋子各有Ｎ个（分别用＊和Ｏ代替），按下图方式排列

＊＊＊．．．＊＊＊ＯＯＯ．．．ＯＯＯ

Ｎ个黑棋Ｎ个白棋

允许将相邻两个棋子互换位置，最后使队形成黑白交替排列，试编程实现该操作。

15. 已知６个城市，用ｃ[i,j]表示从ｉ城市到城市ｊ是否有单向的直达汽车

（１=<ｉ〈＝６，１〈＝ｊ〈＝６）, c[i,j]=1 表示城市ｉ到城市ｊ有单向直达汽
车；否则ｃ[i,j]＝0. 试编制程序，对于给出的城市代号ｉ，打印出从该城市出
发乘车（包括转车）可以到达的所有城市。
16. 设有８枚硬币ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，其中有一枚硬币是伪造的。
真伪硬币的区别仅是重量不同，可能重，可能轻。今要求以天平为工具，用最少的
比较次数挑出伪造硬币，并鉴定它是重还是轻。

17. 编写一个程序，当输入不超过６０个字符组成的英文文字时，计算机将这个句子
中的字母按英文字典字母顺序重新排列，排列后的单词的长度要与原始句子中的长度
相同。例如：

输入：

ＴＨＥＰＲＩＣＥＯＦＢＲＥＡＤＩＳ￥１２５ＰＥＲＰＯＵＮＤ

输出：

ＡＢＣＤＤＥＥＥＥＦＨＩＩＮＯＯＰ￥１２５ＰＰＲＲＲＳＴＵ

并且要求只对Ａ到Ｚ的字母重新排列，其它字符保持原来的状态。

18. 在一线性七个格位置的图上有两种不同颜色的棋子Ａ，Ｂ. 排列如下图所示，中间
格的位置为空。

┎─┰─┰─┰─┰─┰─┰─┒
┃Ａ┃Ａ┃Ａ┃ ┃Ｂ┃Ｂ┃Ｂ┃
┖─┸─┸─┸─┸─┸─┸─┚

要求将Ａ，Ｂ的现行位置交换,形成下图中的排列：

┎─┰─┰─┰─┰─┰─┰─┒
┃Ｂ┃Ｂ┃Ｂ┃ ┃Ａ┃Ａ┃Ａ┃
┖─┸─┸─┸─┸─┸─┸─┚

移动棋子的条件：

(1) 每个格中只准放一个棋子。
(2) 任意一个棋子均可移动一格放入空格内。
(3) 一方的棋子均可跳过另一方的一个棋子进入空格。
(4) 任何棋子不得跳跃两个或两个以上棋子（无论颜色同异）
(5) 任何一个颜色棋子只能向前跳，不准向后跳。

编程完成有关的移动，并且完成具有２Ｎ＋１个格子的情形. 其中两种颜色各有
Ｎ个棋子,且中间为空格.

19. (背包问题) 有 N 件物品 d1，......dN，每件物品重量为 W1，..., WN
(Wi > 0)，每件物品价值为 V1，......VN (Vi>0)。用这N件物品的某个子集
填空背包，使得所取物品的总重量<=TOTAL，并设法使得背包中物品的价值尽可
能高。

20. (Ｎ皇后) 在国际象棋的棋盘上放置Ｎ个皇后，使其不能互相攻击，即任意
两个皇后不能处在棋盘的同一行，同一列，同一斜线上，试问共有多少种摆法？
21. 请设计一个程序，由计算机把１..￣.８的八个自然数填入图中，使得横、
竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
为禁止的情形).

┌─┐ ┌─┐ ┌─┐
│ │ │４│ │８│
┌─┼─┼─┐ └─┼─┐ ┌─┼─┘
│ │ │ │ │５│ │７│
├─┼─┼─┤ └─┘ └─┘
│ │ │ │ ┌─┐
└─┼─┼─┘ │６│ ┌─┬─┐
│ │ ├─┤ │１│２│
└─┘ │７│ └─┴─┘
└─┘

[此贴子已经被作者于2007-6-16 16:32:25编辑过]

女侠，约吗？

第 3 楼

得分:0

将百年兄对第2题的解答搬到这里来

2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
人参加了竞赛：

（１）Ａ参加时，Ｂ也参加；

（２）Ｂ和Ｃ只有一个人参加；

（３）Ｃ和Ｄ或者都参加，或者都不参加；

（４）Ｄ和Ｅ中至少有一个人参加；

（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。

___________________________________________________________________

答案:

#include<stdio.h>
int main()
{
char name[]={'A','B','C','D','E'};
int i,value[5];

for(value[0]=0;value[0]<2;value[0]++)
for(value[1]=0;value[1]<2;value[1]++)
for(value[2]=0;value[2]<2;value[2]++)
for(value[3]=0;value[3]<2;value[3]++)
for(value[4]=0;value[4]<2;value[4]++)
{
if((value[1]>=value[0])
&&(value[1]+value[2]==1)
&&value[2]==value[3]
&&(value[3]+value[4])
&&(!value[4]||(value[4]&&value[0]&&value[3])))
for(i=0;i<5;i++)
if(value[i])
printf("%c参加\t",name[i]);
else
printf("%c不参加\t",name[i]);
}
return 0;

}

结果:

A不参加 B不参加 C参加 D参加 E不参加

女侠，约吗？

第 4 楼

得分:0

#include <iostream>
#include <stack>

using namespace std;

int main()
{
char digit[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

cout <<"输入待转换整数: ";
int number;
cin >>number;
cout <<endl;

cout <<"转换成多少进制? ";
int base;
cin >>base;
cout <<endl;

stack<char> stk;
char remain;
while (number!=0)
{
remain = digit[number%base];
stk.push(remain);
number /= base;
}

cout <<"结果: ";
while(!stk.empty())
{
cout <<stk.top();
stk.pop();
}
cout <<endl;
return 0;
}

第五题的,望指点!

第 5 楼

得分:0

辛苦了，我也冒个泡：
N皇后：

版本1：

[CODE]
//file : queens.h
#ifndef QUEENS_H
#define QUEENS_H
const int max_size = 24;
class queens{
public:
//constructor
queens(int size);

//main function
void solution(); //recursive function for backtracking
//times of solutions
static unsigned int times_of_solution;
protected:
//member functions
void print() const; //print the solution
void insert(int col); //add a queen the posn
void remove(int col); //delete a queen at row-1
bool isSolved() const; //return true if all queens at right posn
bool isUnguarded(int col) const; //return true if the posn is guarded by a queen
private:
//data members
int row;
int board_size;
bool chessboard[max_size][max_size];
};
#endif[/CODE]

[CODE]
//file : queens.cpp
#include "queens.h"
#include <iostream>
queens::queens(int size){
board_size = size;
row = 0; //no queen on chess board
for (int i = 0;i < board_size;++i)
for (int j =0;j < board_size;++j)
chessboard[i][j] = false;
}
bool queens::isSolved() const{
return row == board_size;
}
bool queens::isUnguarded(int col) const{
bool isOk = true;
//at current column
for (int i = 0;isOk && i < row;++i)
isOk = !chessboard[i][col];
//at left upper diagonal
for (int i = 1;isOk && row-i >= 0 && col-i >= 0;++i)
isOk = !chessboard[row-i][col-i];
//at right upper diagonal
for (int i = 1;isOk && row-i >= 0 && col+i < board_size;++i)
isOk = !chessboard[row-i][col+i];
return isOk;
}
void queens::insert(int col){
chessboard[row++][col] = true;
}
void queens::remove(int col){
chessboard[--row][col] = false;
}
void queens::print() const{
for (int i = 0;i < board_size;++i){
for (int j = 0;j < board_size;++j)
std::cout << chessboard[i][j] << " ";
std::cout << std::endl;
}
++times_of_solution;
std::cout << "**************************************" << std::endl;
}
void queens::solution(){
if (isSolved())
print();
else
for (int col = 0;col < board_size;++col)
if (isUnguarded(col)){
insert(col);
//for backtracking
solution();
remove(col);
}
}[/CODE]

//file : main.cpp
#include "queens.h"
#include <iostream>
#include <ctime>
using namespace std;

unsigned int queens::times_of_solution = 0;
int main(){
int size;
cin >> size;
while (size < 1 || size > max_size){
cout << "the queen must between 1 ------ " << max_size << endl;
cin >> size;
}
queens puzzle(size);

////////////////////////////////////////////
clock_t start,finish;
start = clock();
////////////////////////////////////////////

puzzle.solution();
cout << "number of solutions ------ " << queens::times_of_solution << endl;

////////////////////////////////////////////
finish = clock();
double time = (double) (finish - start) / CLOCKS_PER_SEC;
cout << "time used ------ " << time << endl;
////////////////////////////////////////////
}

[此贴子已经被作者于2007-6-16 13:12:08编辑过]

Ｆight ｔｏｗin or ｄie...

第 6 楼

得分:0

版本2 ：无迭代改进版本：

[CODE]
//file : queens.h
#pragma once
const int max_board_size = 24;
class queens{
public:
//constructor
queens(int size);

//main function
void solution(); //recursive function for backtracking
//times of solutions
static unsigned int times_of_solution;
protected:
//member functions
void print() const; //print the solution
void insert(int col); //add a queen the posn
void remove(int col); //delete a queen at row-1
bool isSolved() const; //return true if all queens at right posn
bool isUnguarded(int col) const; //return true if the posn is guarded by a queen
private:
//make bool array for the chessboard
bool col_free[max_board_size];
bool upward_free[2*(max_board_size-1)];
bool downward_free[2*(max_board_size-1)];
int queen_in_rows[max_board_size]; //store the column of queens at each row
//data members
int row;
int board_size;
};[/CODE]

[CODE]
//file : queens.cpp
#include "queens.h"
#include <iostream>
queens::queens(int size){
board_size = size;
row = 0;
//set all columns free
for (int i = 0;i < board_size;++i)
col_free[i] = true;
//set all upward diagonals free
for (int i = 0;i < 2*(board_size-1);++i)
upward_free[i] = true;
//set all downward diagonals free
for (int i = 0;i < 2*(board_size-1);++i)
downward_free[i] = true;
}
bool queens::isSolved() const{
return row == board_size;
}
bool queens::isUnguarded(int col) const{
return col_free[col] && upward_free[row+col]
&& downward_free[row-col+board_size-1];
}
void queens::insert(int col){
queen_in_rows[row] = col;
//set the column & diagonal which is guarded by queen to false
col_free[col] = false;
upward_free[row+col] = false;
downward_free[row-col+board_size-1] = false;
++row;
}
void queens::remove(int col){
//remove a queen at previous row
--row; //back to previous row
//set the column & diagonal which is guarded by queen to true
col_free[col] = true;
upward_free[row+col] = true;
downward_free[row-col+board_size-1] = true;
}
void queens::print() const{
for (int i = 0;i < board_size;++i){
for (int j = 0;j < board_size;++j)
std::cout << (j == queen_in_rows[i] ? "1 " : "0 ");
std::cout << std::endl;
}
std::cout << "---------------------------------" << std::endl;
++times_of_solution;
}
void queens::solution(){
if (isSolved())
print();
else
for (int col = 0;col < board_size;++col)
if (isUnguarded(col)){
insert(col);
//the steps for backtracking
solution();
remove(col);
}
}[/CODE]

//file : main.cpp
#include "queens.h"
#include <iostream>
#include <ctime>
using namespace std;

unsigned int queens::times_of_solution = 0;
int main(){
int size;
cin >> size;
while (size < 4 || size > max_board_size){
cout << "the queen must between 4 ------ " << max_board_size << endl;
cin >> size;
}
queens puzzle(size);

////////////////////////////////////////////
clock_t start,finish;
start = clock();
////////////////////////////////////////////

puzzle.solution();
cout << "number of solutions ------ " << queens::times_of_solution << endl;

[此贴子已经被作者于2007-6-16 13:10:49编辑过]

Ｆight ｔｏｗin or ｄie...

第 7 楼

得分:0

仔细研究中

女侠，约吗？

第 8 楼

得分:0

以下是引用HCL在2007-6-16 13:00:49的发言：

#include <iostream>

...第五题的,望指点!

第五题用堆栈的话就有些限制了吧? 遇到堆栈很小的情况.
如果要考虑负数的话就更难了..象2,8,16等进制都是用补码表示的...啊..好难啊...

[此贴子已经被作者于2007-6-16 14:27:53编辑过]

女侠，约吗？

第 9 楼

得分:0

第2题分析：

首先要设置逻辑变量。value[i]==1时表示第i(i=0~4依次表示A，B，C，D，E五人)个人参加，为0则不参加。

然后写出逻辑函数。将下面的逻辑关系写成函数形式：
（１）Ａ参加时，Ｂ也参加；value[1]>=value[0]
（２）Ｂ和Ｃ只有一个人参加；value[1]+value[2]==1
（３）Ｃ和Ｄ或者都参加，或者都不参加；value[2]==value[3]
（４）Ｄ和Ｅ中至少有一个人参加；(value[3]+value[4])
（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。(!value[4]||(value[4]&&value[0]&&value[3]))
表示为Y=(value[1]>=value[0])&&(value[1]+value[2]==1)&&value[2]==value[3]&&(value[3]+value[4])&&(!value[4]||(value[4]&&value[0]&&value[3])))

最后穷举法把所有的组合算出来，将Y==1时的情况输出。

第 10 楼

得分:0

哦, 谢谢百年兄指点!

女侠，约吗？