《算法竞赛入门经典》

题目 题目描述 有n盏灯，编号为1～n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？输入n和k，输出开着的灯的编号。k≤n≤1000。 样例输入： 7 3 样例输出： 1 5 6 7 解答 #include<iostream> using namespace std; int main() { /* 1:开 0:关 */ int n = 0, k = 0; cin >> n >> k; const int MAX = n; int a[MAX]; for (int z = 0; z <= n - 1; z++) { //生成一个全是1的列表 a[z] = 1; } for (int j = 0; j < n; j++) { for (int i = 1; i <= k; i++) { if (j % i == 0) { if (a[j] == 0) { a[j] = 1; } if (a[j] == 1) { a[j] = 0; } } } if (a[j] == 1) { cout << j << " "; } } return 0; } 这个程序当然不能运行，它存在以下问题： 数组 a[MAX] 未正确初始化，可以改用vector。 a 数组下标从 0 开始，但灯的编号从 1 开始，需要修正数组访问方式。 状态翻转逻辑错误，在翻转灯的状态时，不需要额外判断 a[j] == 0 或 a[j] == 1，直接 a[j] = !a[j]; 即可。 ...

习题 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） ...

题目 输入正整数 n≤20，输出一个 n 层的倒三角形。 例如，n＝5 时输出如下： ######### ####### ##### ### # 解答 我们来分析一下： 行号 空格数 符号数 输出内容 0 0 9 ######### 1 1 7 ####### 2 2 5 ##### 3 3 3 ### 4 4 1 # 初版（有 bug） #include<iostream> using namespace std; int triangle(int a) { //a:层数 a = a * 2 - 1; for (int i = 0; i <= a; i = i + 2) { //i:每行个数 int b = 0; //添加空格 int j = 1; while(j <= i) { cout << " "; j++; } while(b <= i) { //b:每行输出次数 cout << "#"; b++; } cout <<endl; } return 0; } int main() { int n; cin >> n; triangle(n); } 输入： ...

题目 阶乘之和：输入 n，计算 S＝1！＋2！＋3！＋…＋n！的末 6 位（不含前导 0）。n≤106 ，n！表示前 n 个正整数之积。 样例输入： 10 样例输出： 37913 解答 这里应该用双层 for 循环，对于每个 i，乘每一个 j（如程序）。 初版（有 bug） #include <iostream> using namespace std; int main() { int n; int sum = 0; cin >> n; for (int i; i <= n; i++) { int a = 1; for (int j; j <= i; j++) { a = i * j; sum = sum + a; } } sum = sum % 1000000; cout << sum; return 0; } 欸？输出是 0？ 经过 debug 发现，未初始化循环变量，我在使用循环变量 i 和 j 时没有初始化。 改正版（有 bug） #include <iostream> using namespace std; int main() { int n; int sum = 0; cin >> n; for (int i = 1; i <= n; i++) { int a = 1; for (int j = 1; j <= i; j++) { a = i * j; sum = sum + a; } } sum = sum % 1000000; cout << sum; return 0; } 令人费解的是，程序仍然有 bug。 ...

题目 猜想：对于任意大于1的自然数n，若n为奇数，则将n变为3n＋1，否则变为n的一半。 经过若干次这样的变换，一定会使n变为1。例如，3→10→5→16→8→4→2→1。 解答 很简单的重复性程序，没什么技术含量。 #include <iostream> using namespace std; int main() { int n; cin >> n; int j = 0; while (n > 1) { if (n % 2 == 1) { j++; n = 3 * n + 1; continue; } else { j++; n = n / 2; continue; } } cout << j; return 0; } 但是，为了防止数据溢出，我们可以把变量改为 long。 #include <iostream> using namespace std; int main() { long n; cin >> n; int j = 0; while (n > 1) { if (n % 2 == 1) { j++; n = 3 * n + 1; continue; } else { j++; n = n / 2; continue; } } cout << j; return 0; } 祝各位读者早日成为神牛牪犇！

题目 输出所有形如 aabb 的 4 位完全平方数（即前两位数字相等，后两位数字也相等）。 解答 这个题目乍一看，有两种思路： 列举所有完全平方数，再找其中形如 aabb 的。 列举所有形如 aabb 的数，再找其中的完全平方数。 经过我的抉择，我选择了第一种思路 （绝对不是因为我不会判断一个数是否为完全平方数） 解答 #include<iostream> using namespace std; int main() { for (int i = 1; ; i++) { int allnum = i * i; if (allnum > 9999) { break; } int a1 = allnum / 1000; int a2 = allnum / 100 - a1 * 10; int b1 = allnum / 10 - a1 * 100 - a2 * 10; int b2 = allnum / 1 - a1 * 1000 - a2 * 100 - b1 * 10; if (a1 == a2 && b1 == b2) { cout << allnum << endl; } } return 0; } 程序没有问题，但是判断是否为 aabb 的数的过程未免太不优雅了！ 所以，我给出了版本 2： #include<iostream> using namespace std; int main() { for (int i = 1; ; i++) { int allnum = i * i; if (allnum > 9999) { break; } int a1 = allnum / 1000; int a2 = (allnum / 100) % 10; int b1 = (allnum / 10) % 10; int b2 = allnum % 10; if (a1 == a2 && b1 == b2) { cout << allnum << endl; } } return 0; } 这样感觉也挺好。 ...

习题 1-1 平均数（average） 题目描述 输入3个整数，输出它们的平均值，保留3位小数。 解答 #include <iostream> using namespace std; float average(float a,float b,float c) { float sum,aver; sum = a + b + c; aver = sum / 3; return aver; } int main() { float a,b,c,ans; cin >> a >> b >> c; ans = average(a,b,c); cout << ans; return 0; } 太过于基础，不过多描述。 习题1-2 温度（temperature） 题目描述 输入华氏温度f，输出对应的摄氏温度c，保留3位小数。提示：c＝5（f－32）/9。 解答 #include <iostream> using namespace std; int main() { int f,c; cin >> f; float c = 5.0 * (f - 32) / 9; cout << c; return 0; } 也是相当简单的。 习题1-3 连续和（sum） 题目描述 输入正整数n，输出1＋2＋…＋n的值。提示：目标是解决问题，而不是练习编程。 解答 终于是上难度了。 #include <iostream> using namespace std; int sum(int EndNumber) { int sum = 0; for (int i = 0;i <= EndNumber;i++) { sum = sum + i; } return sum; } int main() { int EndNumber,ans; cin >> EndNumber; ans = sum(EndNumber); cout << ans; } 这个题也可以用 等差数列求和公式 来解决。 ...

算法是思想的体操，竞赛是智慧的碰撞。 题目 输入两个整数 a 和 b，交换二者的值，然后输出。 解答 这一个例题甚至比上一个简单，解法直接使用经典的“三变量法”就行了。 解答 #include <iostream> using namespace std; int main() { int a,n,m; cin >> n >> m; a = n; n = m; m = a; cout << n << " " << m; } 过！ 祝各位读者早日成为神牛牪犇！

题目 鸡和兔总数量为 n，总腿数为 m。输入 n 和 m，依次输出鸡的数目和兔的数目。若无解，那么输出 No answer。 解答 这里开始上难度，但是鸡兔同笼是小学学的。。。 定义变量 j、t，分别表示鸡的数量、兔子的数量。 先来写出两个关系式： j + t = n 2j + 4t = m 代入消元 t = (m-2n)/2 所以 j = n – t 并且，我们也要考虑，输入的 m、n 必须为正整数。 那么，我们可以写出以下代码： #include <iostream> using namespace std; int main() { /* n:总数量 m:总腿数 j:鸡数量 t:兔数量 */ int m,n,j,t; cin >> n >> m; t = (m - 2 * n) / 2; j = n - t; if (m % 2 != 0 || m < 2 * n || m > 4 * n) { cout << "No answer"; } else { cout << j << " " << t; } return 0; } 整体难度也不高。 ...

好的，从今天开始，我将学习刘汝佳老师的《算法竞赛入门经典》，以便冲刺今年九月份的 CSP-J。 题目 输入底面半径 r 和高 h，输出圆柱体的表面积，保留3位小数。 样例输入： 3.5 9 样例输出： Area = 274.889 解答 由于题目过于简单，上过小学的人都会逻辑，所以没有分析。 初版解答 #include <iostream> using namespace std; float area(r,h) { int s; s = 2 * pi * r ** 2 + 2 * pi * r * h; return s; } int main() { int r,h,a; cin >> r >> h; a = area(r,h); cout << "Area = " << a; return 0; } 大意了，这个程序存在以下问题： 参数类型缺失 float area(r,h) 未声明参数类型。 未定义常量 π C++ 标准库中没有预定义的 pi。 错误的幂运算符 C++ 不支持 ** 运算符。 变量类型不匹配 公式优化 这个故事告诉我们： 不要以为语言入门之后就能轻易地写出算法程序。 ——《算法竞赛入门经典》前言 这也是我以前存在的问题。 修改解答 #include <iostream> using namespace std; float area(float r,float h) { float s,pi; pi = 3.1415926; s = 2 * pi * r * r + 2 * pi * r * h; return s; } int main() { float r,h,a; cin >> r >> h; a = area(r,h); cout << "Area = " << a; return 0; } 完美通过 ...

题目 输入一个三位数，分离出它的百位、十位和个位，反转后输出。 解答 其实题目也很简单，难点在于如何分离出它百位、十位和个位。 百位 = n/100 十位 = n/10%10 个位 = n%10 解答 #include <iostream> using namespace std; int exchange(int n) { int hundred,ten,one,a; hundred = n / 100; ten = n / 10 % 10; one = n % 10; a = one * 100 + ten * 10 + hundred; return a; } int main() { int n,ans; cin >> n; ans = exchange(n); cout << ans; return 0; } 这一次也是认真多了，一遍过。 祝各位读者早日成为神牛牪犇！