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

int main() {

char s[SIZE], m1, m2; int i; gets(s); m1 = ' '; m2 = ' ';

for (i = 0; i < strlen(s); i++) if (s[i] > m1) { m2 = m1; m1 = s[i]; }

else if (s[i] > m2) m2 = s[i]; printf(\ return 0; }

输入：Expo 2010 Shanghai China 输出：_________ 提示：

字符 ASCII码 4．

#include #define NUM 5 int r(int n) {

int i; if (n <= NUM) return n;

for (i = 1; i <= NUM; i++) if (r(n - i) < 0) return i; return -1; }

空格 32 '0' 48 'A' 65 'a' 97 - 5 -

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 -