算法竞赛入门经典第二章【小结与习题】

╰半橙微兮° 2022-09-18 04:00 184阅读 0赞

2.4.1 输出技巧

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** i, n;  
7.    
8.      scanf("%d", &n);  
9.      **for** (i = 1; i <= n; i++)  
10.         printf("%d\\n", i);  
11.     **return** 0;  
12. \}

目的：输出2, 4, 6, 8, ..., 2n  
任务1：只修改printf()

**\[cpp\]**  [view plain][] [copy][view plain]

1.  printf("%d\\n", 2\*i);\\

任务2：只修改for循环体

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **for** (i = 2; i <= 2\*n; i += 2)

2.4.2 浮点数陷阱

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **double** i;  
7.        
8.      **for** (i = 0; i != 10.0; i += 0.1)  
9.          printf("%.1f\\n", i);          
10.     **return** 0;  
11. \}

这段代码运行了就停不下来，打印出来保留三位数可以看到有10.000，但是这个数不会跟10.0相等。gdb跟踪可以看到这个10.000其实可以是9.99999999999998046007476659724488854408264160156250。可以用下面的代码运行便知！

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **double** i;  
7.      **int** j;  
8.        
9.      **for** (i = 0, j = 0; i != 10.0 && j != 102; i += 0.1, j++) \{  
10.         printf("%.50f\\n", i);  
11.     \}         
12.     **return** 0;  
13. \}

这里还发现如果把10.0改为0.5是可以正确运行的，代码如下：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **double** i;  
7.        
8.      **for** (i = 0; i != 0.5; i += 0.1) \{  
9.          printf("%.50f\\n", i);  
10.     \}         
11.     **return** 0;  
12. \}

总之不要用浮点数来充当计数器，因为浮点数的表示是可以允许有误差的。

2.4.2 64位整数

像杭电OJ可能是Windows平台上建立的，测试是要用"%I64d"才能编译通过，而有些OJ就用"%lld"(long long int)

2.4.4 C++的输入输出

略

【上机练习】

习题2-1 位数(digit)

输入一个不超过10^9的正整数，输出它的位数。例如12735的位数是5。请不要使用任何数学函数，只能用四则运算和循环语句实现。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** num;//garantee less than 10^9  
7.      **int** i, digit = 0;  
8.    
9.      scanf("%d", &num);  
10.     **for** (i = 1; num/i != 0; i\*=10)  
11.         digit++;  
12.     printf("%d\\n", digit);    
13.     **return** 0;  
14. \}

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

输出100~999中的所有水仙花数。若3位数ABC满足ABC=A^3+B^3+C^3，则称其为水仙花数。例如153=1^3+5^3+3^3，所以153是水仙花数。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** i;  
7.      **int** a, b, c;  
8.      **for** (i = 100; i != 1000; i++) \{   
9.          a = i/100;  
10.         b = i/10%10;  
11.         c = i%10;  
12.         **if** (a\*a\*a + b\*b\*b + c\*c\*c == i)  
13.             printf("%d\\n", i);  
14.     \}  
15.     **return** 0;  
16. \}

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

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

样例输入：2 1 6

样例输出：41

样例输出：2 1 3

样例输出：No answer

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** a, b, c;  
7.      **int** i;  
8.    
9.      scanf("%d%d%d", &a, &b, &c);  
10.     **for** (i = 10; i != 100; i++) \{  
11.         **if** (i%3 == a && i%5 == b && i%7 == c) \{  
12.             printf("%d\\n", i);  
13.             **break**;  
14.         \}             
15.     \}  
16.     **if** (i == 100)  
17.         printf("No answer\\n");  
18.     **return** 0;  
19. \}

枚举量还不到100，而且发现满足条件后直接退出循环，i也不会增加，确保输出0 4 0，输出是99，而不会输出99然后又输出100；i == 100成立等价于没有执行过break;语句，所以就是无解。

习题2-4 倒三角形(triangle)  
输入正整数n<=20，输出一个n层的倒三角形。例如n = 5时输出如下：

(9个\#一行，7个一行，5个一行，3个一行，1个一行，且除第一行外，每行最中间的\#与上一行最中间的\#对齐)

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** n, m;  
7.      **int** i, j;  
8.    
9.      scanf("%d", &n);  
10.     m = 2\*n-1;  
11.     **for** (i = 0; i != n; i++) \{  
12.         **for** (j = 0; j != m; j++)   
13.             printf((j<i || j > m-1-i) ? " " : "\#");   
14.         printf("\\n");  
15.     \}     
16.     **return** 0;  
17. \}

设计思路：首先在for循环里写一行代码printf("\#");即可以输出一个n\*m的矩阵；然后再做调整！我们观察如果要构成倒三角，每一行中空格取代\#处的数目与行号序号成正相关，不难写出在位置(i, j)满足(j < i || j > m-1-j)时用空格来代替\#。如果认为三角形右边的空格是多余的，也可以分三路，符合条件j>m-1-i的位置什么也不做，即执行空语句。

习题2-5 统计(stat)

输入一个正整数n，然后读取n个正整数a1, a2, ..., an，最后再读一个正整数m。统计a1, a2, ..., an中有多少整数的值小于m。提示：如果重定向和fopen都可以使用，哪个比较方便？

暂略。。。

习题2-6 调和级数(harmony)

输入正整数n，输出H(n) = 1+(1/2)+(1/3)+...+(1/n)的值，保留3位小数。例如n=3时答案为1.833。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** n;  
7.      **int** i;  
8.      **double** sum = 0;  
9.    
10.     scanf("%d", &n);  
11.     **for** (i = 1; i != n+1; i++) \{  
12.         sum += 1.0/i;  
13.     \}  
14.     printf("%.3f\\n", sum);  
15.     **return** 0;  
16. \}

习题2-7 近似计算(approximation)

计算(PI/4) = 1 - 1/3 + 1/5 - 1/7 +...，直到最后一项小于10^(-6)。

理解题意：意思就是计算右边的式子，计算到满足下述条件时停止。条件是：最后一项（不带符号）小于0.000001

然后我设置输出右边式子结果的4倍，作为PI的近似值

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#define N 0.000001  
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** sign = 1, i = 2;  
7.      **double** cur = 1.0, sum = 0.0;  
8.    
9.      **for** (; ;) \{  
10.         **if** (cur < N)  
11.             **break**;        
12.         sum += cur\*sign;  
13.         cur = 1.0/(i\*2-1);  
14.         i++;  
15.         sign = -sign;  
16.     \}  
17.     printf("PI ~= %.6f\\n", 4\*sum);  
18.     **return** 0;  
19. \}

结果输出是：PI ~= 3.141591

习题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。注意：本题有陷阱。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **double** n, m;  
7.      **double** i, sum = 0.0;  
8.      scanf("%lf%lf", &n, &m);  
9.      **for** (i = n; i <= m; i++) \{  
10.         sum += 1.0/(i\*i);  
11.     \}  
12.     printf("%.5f\\n", sum);    
13.     **return** 0;  
14. \}

首先分母是正整数求平方，可能会溢出，所以要使用浮点数。

习题2-9 分数化小数(decimal)

输入正整数a, b, c，输出a/b的小数形式，精确到小数点后c位。a, b <= 10^6，c <= 100。例如a=1, b=6, c=4时应输出0.1667。

刚开始想到一个用数组（字符串）实现的方法，如下

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#define N 110  
3.  **char** str\[N\];  
4.    
5.  **int**  
6.  main(**void**)  
7.  \{  
8.      **double** a, b;  
9.      **int** c;  
10.     **char** \*p;  
11.   
12.     scanf("%lf%lf%d", &a, &b, &c);  
13.     sprintf(str, "%.100f", a/b);  
14.             
15.     **for** (p = str; \*(p-1) != '.'; p++)  
16.         printf("%c", \*p);  
17.       
18.     **for** (; \*p != '\\0'; p++) \{  
19.         **if** (c-- == 1)  
20.             **break**;  
21.         printf("%c", \*p);  
22.     \}  
23.       
24.     printf("%c\\n", \*(p+1)-'0' >= 5 ? \*p+1 : \*p);  
25.       
26.     **return** 0;  
27. \}

说明：首先把a/b精确到100位的结果作为字符串存入数组str中，然后输出小数点之前的部分，接着输出c-1位小数，再根据c+1位小数是否大于或等于5输出第c位小数。

**补充：其实这个程序是错的！它有两个严重的BUG.**

第一个是\*(p-1)第一次执行时，数组第一个元素前面一个位置的地址是未定义的（UB），这种代码就是错的！

第二个是当遇到4.425987时候，如果我保留4位呢？结果应当是4.4260。但是上述程序只是简单地仅对最后一位小数作修改或不修改，输出的结果会是4.425:

最后发现，格式化输出还有特殊用法，比如

**\[cpp\]**  [view plain][] [copy][view plain]

1.  printf("%\*.\*lf\\n", 8, 4, (**double**)10/3);

会输出8个字宽保留4位小数的浮点数运算结果

所以这个题目的标准答案应该是：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** a, b, c;  
7.    
8.      scanf("%d%d%d", &a, &b, &c);  
9.      printf("%.\*f\\n", c, (**double**)a/b);  
10.     **return** 0;  
11. \}

习题2-10 排列(permutation)

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

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.    
3.  **int**  
4.  main(**void**)  
5.  \{  
6.      **int** i, j, k;  
7.      **int** i1, i2, i3;  
8.      **int** j1, j2, j3;  
9.      **int** k1, k2, k3;  
10.     **int** c, count;  
11.   
12.     **for** (i = 123; i <= 329; i++) \{  
13.         j = i\*2;  
14.         k = i\*3;  
15.         i1 = i/100, i2 = i/10%10; i3 = i%10;  
16.         j1 = j/100, j2 = j/10%10; j3 = j%10;  
17.         k1 = k/100, k2 = k/10%10; k3 = k%10;          
18.         **for** (c = 1; c != 10; c++) \{  
19.             count = 0;  
20.             **if** (c == i1)  
21.                 count++;  
22.             **if** (c == i2)  
23.                 count++;  
24.             **if** (c == i3)  
25.                 count++;  
26.             **if** (c == j1)  
27.                 count++;  
28.             **if** (c == j2)  
29.                 count++;  
30.             **if** (c == j3)  
31.                 count++;  
32.             **if** (c == k1)  
33.                 count++;  
34.             **if** (c == k2)  
35.                 count++;  
36.             **if** (c == k3)  
37.                 count++;  
38.             **if** (count > 1)  
39.                 **break**;  
40.         \}  
41.         **if** (c == 10 && i2 != 0 && i3 != 0 && j2 != 0 && j3 != 0 && k2 != 0 && k3 != 0)  
42.             printf("%d %d %d\\n", i, j, k);  
43.     \}         
44.     **return** 0;  
45. \}

思路：暴力枚举，不过因为不能用数组，所以写起来比较繁琐，目前只能想到这种方法了。

程序输出了四组：

192 384 576  
219 438 657  
273 546 819  
327 654 981

[view plain]: http://blog.csdn.net/architect19/article/details/8557383#