NOIP2010第十六届普及组初赛（c语言）(2)

int main() {

int n;

scanf(\ printf(\ return 0; } （1） 输入：7

输出：_________（4分） （2） 输入：16

输出：_________（4分）

四、完善程序（前4空，每空2.5分，后6空，每空3分，共计28分）

1．（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。

#include #define SIZE 1000

int main() {

int n, r, p[SIZE], i, j, k, ans, tmp; scanf(\ r = 1; p[1] = 2;

for (i = 3; i <= n; i++) { ① ;

for (j = 1; j <= r; j++) if (i % ② == 0) { tmp = 0; break; }

if (tmp == 1) { r++; ③ ; }

- 6 -

} ans = 0;

for (i = 2; i <= n / 2; i++) { tmp = 0;

for (j = 1; j <= r; j++) for (k = j; k <= r; k++) if (i + i == ④ ) { tmp = 1; break; } if (tmp == 1) ans++; }

printf(\ return 0; }

若输入n为2010，则输出 ⑤ 时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。

2．（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n（2≤n<100）和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4=7。 #include #define SIZE 100 #define INFINITY 10000 #define LEFT 1 #define RIGHT 0 #define LEFT_TO_RIGHT 1 #define RIGHT_TO_LEFT 0 int n, time[SIZE], pos[SIZE];

int max(int a, int b) {

- 7 -

if (a > b) return a; else

return b; }

int go(int stage) {

int i, j, num, tmp, ans;

if (stage == RIGHT_TO_LEFT) {

num = 0; ans = 0;

for (i = 1; i <= n; i++) if (pos[i] == RIGHT) { num++;

if (time[i] > ans) ans = time[i]; }

if ( ① ) return ans; ans = INFINITY;

for (i = 1; i <= n - 1; i++) if (pos[i] == RIGHT)

for (j = i + 1; j <= n; j++) if (pos[j] == RIGHT) { pos[i] = LEFT; pos[j] = LEFT;

tmp = max(time[i], time[j]) + ② ; if (tmp < ans) ans = tmp; pos[i] = RIGHT; pos[j] = RIGHT; } return ans;

}

- 8 -

if (stage == LEFT_TO_RIGHT) {

ans = INFINITY;

for (i = 1; i <= n; i++) if ( ③ ) { pos[i] = RIGHT; tmp = ④ ; if (tmp < ans) ans = tmp; ⑤ ; } return ans; } return 0; }

int main() {

int i;

scanf(\

for (i = 1; i <=n; i++) { scanf(\ pos[i] = RIGHT; }

printf(\ return 0; }

CCF NOIP2010普及组（C语言）参考答案与评分标准

一、单项选择题（共20题，每题1.5分，共计30分） D A A D A D B D C B D B B B B A A D C D

- 9 -

二、问题求解（共2题，每题5分，共计10分）

1．2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或22123113431213536） 2．49

三、阅读程序写结果（共4题，每题8分，其中第4题（1）、（2）各4分，共计32分）1．2 20 77 91 2．99 101 111 3．120 112 4．（1）1 （2）4

四、完善程序（前4空，每空2.5分，后6空，每空3分，共计28分）

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1．① tmp = 1 ② p[j] ③ p[r] = i

④ p[j] + p[k]（或p[k] + p[j]） ⑤ 1004

2．① num <= 2（或num < 3 或num == 2） ② go(LEFT_TO_RIGHT)

③ pos[i] == LEFT（或LEFT == pos[i]）

④ time[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + time[i]） ⑤ pos[i] = LEFT

本小题中，LEFT可用1代替，LEFT_TO_RIGHT可用1代替，RIGHT_TO_LEFT可用0代替。

- 10 -