习题 2-1 水仙花数（daffodil）
题目描述
输出 100～999 中的所有水仙花数。若 3 位数 ABC 满足
[ ABC = A^3 + B^3 + C^3 ]
则称其为水仙花数。例如 153= (1^3+5^3+3^3) ，所以 153 是水仙花数。
解答
#include<iostream>
using namespace std;
int main()
{
int a, b, c = 0;
for (int num = 100; num <= 999; num++)
{
a = num / 100;
b = (num / 10) % 10;
c = num % 10;
if (num == (a * a * a) + (b * b * b) + (c * c * c))
{
cout << num << endl;
}
}
}
没什么可说的。
习题 2-2 韩信点兵（hanxin）
题目描述
相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。
输入包含多组数据，每组数据包含 3 个非负整数 a, b, c，表示每种队形排尾的人数（a < 3, b < 5, c < 7），输出总人数的最小值（或报告无解）。已知总人数不小于 10，不超过 100。输入到文件结束为止。
样例输入
2 1 6
2 1 3
样例输出
Case 1: 41
Case 2: No answer
解答
初版（有 bug）
#include<iostream>
using namespace std;
int main()
{
int a, b, c = 0;
cin >> a >> b >> c;
for (int num = 10; num <= 100; num++)
{
if ((num % 3 == a) && (num % 5 == b) && (num % 7 == c))
{
cout << num;
break;
}
else
{
cout << "No answer";
continue;
}
}
}
错误输出
No answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answerNo answer41
这样肯定不对。 动了一下聪明的大脑，想出以下解决方法：
修正版本
#include<iostream>
using namespace std;
int main()
{
int a = 0, b = 0, c = 0;
bool found = false;
cin >> a >> b >> c;
for (int num = 10; num <= 100; num++)
{
if ((num % 3 == a) && (num % 5 == b) && (num % 7 == c))
{
cout << num;
found = true;
break;
}
}
if (!found)
{
cout << "No answer";
}
}
这就对了。 在此基础上，还需要添加多组数据处理，这里以后会出文章讲解，所以这里不再说明。
习题 2-3 倒三角形（triangle）
习题 2-4 子序列的和（subsequence）
题目描述
输入两个正整数 n < m < 10^6，输出
[ \frac{1}{n^2} + \frac{1}{(n+1)^2} + … + \frac{1}{m^2} ]
保留 5 位小数。输入包含多组数据，结束标记为 n = m = 0。
样例输入
2 4
65536 655360
0 0
样例输出
Case 1: 0.42361
Case 2: 0.00001
解答
#include<iostream>
#include <iomanip>
using namespace std;
int main()
{
long long n = 0;
long long m = 0;
double sum;
cin >> n >> m;
for (; n <= m; n++)
{
sum += 1.0 / (static_cast<double>(n) * n);
}
cout << fixed << setprecision(5) << sum << endl;
}
题目中的陷阱可能指：
- 大数溢出；
- 分数的值使用浮点数。
所以，我们可以这样解决：
- 将 n 和 m 声明为 long long 类型，确保大数计算不溢出。
- 在计算 n*n 时，通过 static_cast(n) 转换为浮点数运算，避免整数溢出。
- 使用 double 类型累加和，保留足够精度。
- fixed « setprecision(5) 控制输出保留五位小数。
和之前一样，在此基础上，还需要添加多组数据处理，这里以后会出文章讲解，所以这里不再说明。
习题 2-5 分数化小数（decimal）
题目描述
输入正整数 a, b, c，输出 a/b 的小数形式，精确到小数点后 c 位。a, b ≤ 10^6，c ≤ 100。输入包含多组数据，结束标记为 a = b = c = 0。
样例输入
1 6 4
0 0 0
样例输出
Case 1: 0.1667
解答
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
double a = 0.0, b = 0.0;
int c = 0;
cin >> a >> b >> c;
double ans = a / b;
cout << fixed << setprecision(c) << ans << endl;
}
和之前一样，在此基础上，还需要添加多组数据处理，这里以后会出文章讲解，所以这里不再说明。
习题 2-6 排列（permutation）
题目描述
用 1,2,3,…,9 组成 3 个三位数 abc, def, ghi，每个数字恰好使用一次，要求 abc:def:ghi=1:2:3。
按照 “abc def ghi” 的格式输出所有解，每行一个解。
解答
#include<iostream>
using namespace std;
int main()
{
int a, b, c, d, e, f, g, h, i;
for(a = 1; a <= 9; a++)
{
for(b = 1; b <= 9; b++)
{
for(c = 1; c <= 9; c++)
{
for(d = 1; d <= 9; d++)
{
for(e = 1; e <= 9; e++)
{
for(f = 1; f <= 9; f++)
{
for(g = 1; g <= 9; g++)
{
for(h = 1; h <= 9; h++)
{
for(i = 1; i <= 9; i++)
{
if(2 * (a * 100 + b * 10 + c) == (d * 100 + e * 10 + f) &&
3 * (a * 100 + b * 10 + c) == (g * 100 + h * 10 + i) &&
a != b && a != c && a != d && a != e && a != f &&
a != g && a != h && a != i && b != c && b != d &&
b != e && b != f && b != g && b != h && b != i &&
c != d && c != e && c != f && c != g && c != h &&
c != i && d != e && d != f && d != g && d != h &&
d != i && e != f && e != g && e != h && e != i &&
f != g && f != h && f != i && g != h && g != i &&
h != i)
{
cout << a * 100 + b * 10 + c << " "
<< d * 100 + e * 10 + f << " "
<< g * 100 + h * 10 + i << endl;
}
}
}
}
}
}
}
}
}
}
return 0;
}
emm… 没什么好说的，暴力求解法……
总结
至此，我们已经完成了 《算法竞赛入门经典》第二章 的学习。
愿你在不断调试代码与思维的过程中，感受到算法之美与编程之乐！
下一章，我们不见不散！