《算法竞赛入门经典（第二版）》习题解答——第二章

---

文章目录

• 
  

  一、习题2-1 水仙花数（daffodil）

• 
  

  二、习题2-2 韩信点兵（hanxin）

• 
  

  三、习题2-3 倒三角形（triangle）

• 
  

  四、习题2-4 子序列的和（subsequence）

• 
  

  五、习题2-5 分数化小数（decimal）

• 
  

  六、习题2-6 排列（permutation）

• 总结

---

一、习题2-1 水仙花数（daffodil）

输出100～999中的所有水仙花数。

若3位数ABC满足ABC＝A3＋B3＋C3，则称其为水仙花数。

例如153＝13＋53＋33，所以153是水仙花数。

#define _CRT_SECURE_NO_WARNING
#pragma warning(disable : 4996)
#include
int main()
{
    int a, b, c;
    for (int i = 100; i <= 999; i++) {
    a = i / 100;
    b = i / 10 % 10;
    c = i % 10;
    if (i == a * a * a + b * b * b + c * c * c)
        printf("%d是水仙数\n", i);
    }    
    return 0;
}

二、习题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

题解1

#include
int main()
{
    int a,b,c,n,i = 1;
    scanf("%d%d%d",&a,&b,&c);
    for(n = 10;n < 101;n++){
        if(n % 3 == a && n % 5 == b && n % 7==c){
            i = 0;
            break;
        }
    }
    if(i){
        printf("No answer\n");
    }else{
        printf("总人数 = %d\n",n);
    }
    return 0 ;
}

解析

用i标志来解决输出问题

题解2

#include
int main()
{   int a,b,c,i,n=0;
    freopen("2-2 datain.txt","r",stdin);//需要提前在cpp文件同一目录下建立txt文件作为scanf的读取路径
    freopen("2-2 dataout.txt","w",stdout);
    while(scanf("%d%d%d",&a,&b,&c)==3)
	{   
		++n;
		for(i=10;i<=100;i++)
	   {
			if(i%3==a && i%5==b && i%7==c)
			{
				printf("Case %d: %d\n",n,i);
				break;
			}
						
	   }
	   if(i>100) printf("No answer\n");	   		
	}
	
	return 0;
}

解析

此代码运用文件读写方式。

关于文件结束，在参考不同的答案时有人根据其标志为EOF，所以while的条件为while (scanf ("%d%d%d",&a,&b,&c) != EOF)，但此题中我用了重定向的方法，故循环条件为while(scanf("%d%d%d",&a,&b,&c)==3)。

三、习题2-3 倒三角形（triangle）

输入正整数n≤20，输出一个n层的倒三角形。

例如，n＝5时输出如下：

#include
int main()
{
    int n;
    scanf("%d",& n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2*n-1; j++) {
         if(j<i) printf(" ");
          if(j>=i&&j<2*n-i-1) printf("#");
        }
      printf("\n");     
    }
        
    return 0;
}

四、习题2-4 子序列的和（subsequence）

输入两个正整数n＜m＜106，输出 1 n 2 + 1 ( n + 1 ) 2 + ⋯ + 1 m 2 \frac{1}{n^2}+\frac{1}{(n+1)^2}+\cdots +\frac{1}{m^2} n21​+(n+1)21​+⋯+m21​ ，保留5位小数。

输入包含多组数据， 结束标记为n＝m＝0。

提示：本题有陷阱。

样例输入：
2 4
65536 655360
0 0
样例输出：
Case 1: 0.42361
Case 2: 0.00001

---

#include
int main()
{
    int n,m,temp;
    double s=0;
    scanf("%d%d",& n,&m);
    if (n > m) {
        temp = n;
        n = m;
        m = temp;
    }
    for (int i = n; i <= m; i++) {
        s += 1.0 / i/i;  //1.0/(i*i)精度会溢出    
    }  
    printf("%.5lf",s);      
    return 0;
}

防止精度溢出也可以将n,m,i的类型直接定义为long long型

五、习题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
int main()
{
    int a,b,c;
    double s=0;
    scanf("%d%d%d",& a,&b,&c);
    s = a * 1.0 / b;
    printf("%.*lf\n",c,s);      
    return 0;
}

printf的特殊用法printf("%*.*lf\n",a,b,s);前面的**定义的是总的宽度，后边的是定义保留的小数位数

六、习题2-6 排列（permutation）

用1，2，3，…，9组成3个三位数abc，def和ghi，每个数字恰好使用一次，要 求abc：def：ghi＝1：2：3。

按照“abc def ghi”的格式输出所有解，每行一个解。

提示：不必太动脑筋。

#include
int main()
{
    int n,m,t;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (i == j)continue;
            for (int k = 1; k <= 9; k++) {
                if (i == j || i == k || j == k)continue;
                    n = i * 100 + j * 10 + k;
                    m = 2 * n;
                    t = 3 * n;
                int d = m / 100;
                int e = m / 10 % 10;
                int f = m % 10;
                int g = t / 100;
                int h = t / 10 % 10;
                int i = t % 10;
                if(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&&m<1000&&t<1000)
                printf("%d %d %d\n", n, m, t);      
            }
        }
    }    
    return 0;

总结

文件输入题是硬伤！！
代码逻辑没有太大问题，但由于能力有限，部分代码不够简洁，会继续努力哒