算法竞赛入门经典（第二版）第2章习题

编程技术  /  houtizong 发布于 3年前   169

2.4.1 输出技巧
#include <stdio.h>

int
main()
{
int i, n;

scanf("%d", &n);
for (i = 1; i <= n; i++)
printf("%d\n", i);
return 0;
}

习题2-2 水仙花数(daffodil)

输出100~999中的所有水仙花数。若3位数ABC满足ABC=A^3+B^3+C^3，则称其为水仙花数。
#include <stdio.h>

int
main()
{
int i;
int a, b, c;
for (i = 100; i != 1000; i++) {
a = i/100;
b = i/10%10;
c = i%10;
if (a*a*a + b*b*b + c*c*c == i)
printf("%d\n", i);
}
return 0;
}


习题2-3 韩信点兵(hanxin)

相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负数a, b, c，表示每种队形排尾的人数(a<3, b<5, c<7)，输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100。

样例输入：2 1 6

样例输出：41

样例输出：2 1 3

样例输出：No answer
#include <stdio.h>

int
main()
{
int a, b, c;
int i;

scanf("%d%d%d", &a, &b, &c);
for (i = 10; i != 100; i++) {
if (i%3 == a && i%5 == b && i%7 == c) {
printf("%d\n", i);
break;
}
}
if (i == 100)
printf("No answer\n");
return 0;
}

习题2-8 子序列的和(subsequence)

输入两个正整数n<m<10^6，输出 1/n^2 + 1/(n+1)^2 + ... + 1/m^2，保留5位小数。例如n=2, m=4时答案是0.42361; n = 65536, m = 655360时答案是0.00001。注意：本题有陷阱。

#include <stdio.h>

int
main(void)
{
int a, b, c;

scanf("%d%d%d", &a, &b, &c);
printf("%.*f\n", c, (double)a/b);
return 0;
}


习题2-10 排列(permutation)

用1,2,3,...,9组成3个三位数abc, def和ghi，每个数字恰好使用一次，要求abc:def:ghi = 1:2:3。输出所有解。提示：不必太动脑筋。

#include <stdio.h>

int
main(void)
{
int i, j, k;
int i1, i2, i3;
int j1, j2, j3;
int k1, k2, k3;
int c, count;

for (i = 123; i <= 329; i++) {
j = i*2;
k = i*3;
i1 = i/100, i2 = i/10%10; i3 = i%10;
j1 = j/100, j2 = j/10%10; j3 = j%10;
k1 = k/100, k2 = k/10%10; k3 = k%10;
for (c = 1; c != 10; c++) {
count = 0;
if (c == i1)
count++;
if (c == i2)
count++;
if (c == i3)
count++;
if (c == j1)
count++;
if (c == j2)
count++;
if (c == j3)
count++;
if (c == k1)
count++;
if (c == k2)
count++;
if (c == k3)
count++;
if (count > 1)
break;
}
if (c == 10 && i2 != 0 && i3 != 0 && j2 != 0 && j3 != 0 && k2 != 0 && k3 != 0)
printf("%d %d %d\n", i, j, k);
}
return 0;
}
思路：暴力枚举