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

此为练手简单习题，觉得挺有意思，并且第一次处理之时想的过于简单或者处理有误，故贴出来作为提醒，并分享处理方案，仅供参考！

习题 2-5：分数化小数

输入正整数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

该题以普通想法来说，是直接进行输出，但是存在着两个问题：

  1. 输出的小数位数为c，不好直接进行输出
  2. c ≤ 100 ，由于C语言小数位数的限定，就算 double 类型，其小数位数也不可能达到100位，具体位数可自己进行试验，所以直接进行输出时会有严重的精度损失

由以上，我们可以针对C语言整数除法的特点，间接计算小数的值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void Decimal(int a, int b, int c){
    int i = 1;
    printf("%d.", a/b); // 输出非小数位
    a = a % b;
    while (i++ < c){	// 小数点后前 c-1 位
        a *= 10;
        printf("%d", a/b);
        a = a % b;
    }
    a *= 10;
    /* 小数点后第 c 位进行四舍五入 */
    printf("%d\n", ((a%b)*10)/b >= 5 ? (a/b+1):(a/b));
}

以上代码，直接采用函数方式进行分数转小数原理的实现，将多次输入省略

注：上述代码实现原理参考Artprog的CSDN博客C语言 分数化小数

习题2-6：排列

用1,2,3，……9组成3个三位数 abc , def 和 ghi，每个数字恰好使用一次，要求 abc:def:ghi=1:2:3。按照 “abc def ghi” 格式输出所有接。

样例输入

无

样例输出

abc def ghi

此题我基本想法确立之后：循环判断 abc 2abc 3abc 三个数各位 1~9 每个数字是否恰好使用一次，在判断是否使用之时，却遇到了一些困难，参考博客之后，有了如下解法：

采用一个布尔类型数组，下标表示数字，储存的值表示数字是否被用到(false or true)，如果数组下标1~9全部为储存的值全部为 true，就进行输出。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Permutation(){
    int i, j, k;
    bool isAppear[10];  // 定义判别数组
    for (i = 123; i < 330; i++){
        memset(isAppear, false, sizeof(isAppear));
        j = 2*i;    k = 3*i;
        // 处理数组
        isAppear[i/100] = isAppear[(i/10)%10] = isAppear[i%10] = true;
        isAppear[j/100] = isAppear[(j/10)%10] = isAppear[j%10] = true;
        isAppear[k/100] = isAppear[(k/10)%10] = isAppear[k%10] = true;
        // 判断 1-9 九个数是否都用到
        for (int l = 1; l < 10; l++) {
            if (isAppear[l] == false)
                break;
            if (l == 9)
                printf("%5d%5d%5d\n", i, j, k);
        }
    }
}

注：上述代码参考Lecholin的博客《算法竞赛入门经典》习题2-6 三位数排列