算法竞赛入门经典-第二章习题

发表于 分类于 ，

习题2-1 水仙花数-daffodil


谭浩强习题5-8，难度不大，直接复制过来吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main() {
    int i, bai, shi, ge;
    for (i = 100; i < 1000; i++) {
        ge = i % 10;
        shi = i / 10 % 10;
        bai = i / 100 % 10;
        if ((ge * ge * ge + shi * shi * shi + bai * bai * bai) == i) {
            printf("这是一个水仙花数: %d。\n", i);
        } else {
            // printf("这不是一个水仙花数\n");
        }
    }
    return 0;
}

习题2-4 韩信点兵-hanxin

方法1 穷举

可怜可怜，只会用穷举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#define MIN 10
#define MAX 100
int hanxin(int a, int b, int c) {
    int i;
    for (i = MIN; i < MAX; i++) {
        if ((i % 3 == a) && (i % 5 == b) && (i % 7 == c)) {
            return i;
        }
    }
    return 0;
}
int main() {
    int sum, a, b, c, kase = 0;
    while ((scanf("%d", &a)) && (scanf("%d", &b)) && (scanf("%d", &c))) {
        printf("Case %d:", ++kase);
        if ((sum = hanxin(a, b, c)) != 0) {
            printf("%d", sum);
        } else {
            printf("No answer");
        }
        printf("\n");
    }
    return 0;
}

习题2-3 倒三角型-triangle


和我们课程测试题目差不多，甚至更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
void space(int x) {
    while (x--) {
        printf(" ");
    }
}
void jin(int x) {
    while (x--) {
        printf("#");
    }
}
int main() {
    int n;
    int i = 0;
    scanf("%d", &n);
    if (n <= 20 && n > 0) {
        while (n) {
            space(i++);
            jin(2 * (n--) - 1);
            printf("\n");
        }
    }
    return 0;
}

习题2-4 子序列的和-subsequence


题目说：本题有陷阱。但可惜我不知道陷阱是啥。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
double cal(long n, long m) {
    double sum = 0;
    for (n = n - 1; n < m; n++) {
        sum += 1 / (double)((n + 1) * (n + 1));
    }
    return sum;
}
int main() {
    int kase = 0;
    long n, m;
    while ((scanf("%ld%ld", &n, &m)) && ((n != 0) && (m != 0))) {
        if (kase) printf("\n");
        printf("Case %d:%.5f", ++kase, cal(n, m));
    }
    return 0;
}

习题2-5 分数化小数-decimal


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 坑！
// strlen 是数组长度，数组长度 0 1 2 3 4，有 5 项，倒数第二项是 3，所以要减 2。
// 这个长度是计算到非 0 的数字的，也就是说 num[10] = {1,0,0,0,0},只有一项！
#include <math.h>
#include <stdio.h>
// 这是用来输出小数点后半段的
void chu(int a, int b, int c) {
    // 用来存放小数点的数组
    char num[101];
    // 计算的余数？不知道叫啥。
    int tmp = a;
    // 计数器，两次的用途不一样
    int i;
    // 位数
    int ws = 0;
    // 自己实现除法
    for (i = 0; i <= c; i++) {
        // 请看本文章旁边的图理解
        num[i] = (tmp * 10) / b;
        // printf("num[%d]=%d\n", i, num[i]);
        tmp = (tmp * 10) % b;
        ws++;
    }

    for (i = 0; i < (ws - 1); i++) {
        // 四舍五入
        if (i == (ws - 2)) {
            if (num[i + 1] > 4) {
                num[i] = num[i] + 1;
            }
        }
        printf("%d", num[i]);
    }
}
int main() {
    int a, b, c, kase = 0;
    while ((scanf("%d", &a)) && (scanf("%d", &b)) && (scanf("%d", &c)) &&
           !((a == 0) && (b == 0) && (c == 0))) {
        if (++kase) printf("\n");
        // 输出前半段
        printf("Case %d: 0.", kase);
        chu(a, b, c);
    }
    return 0;
}

习题2-6 排序-permutation


我日，真难啊！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
int main() {
    int a, b, c, kase = 0;
    // 百位
    for (int ai = 0; ai < 3; ai++) {
        char arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        a = arr[ai];
        arr[ai] = 0;
        // 十位
        for (int bi = 0; bi < 9; bi++) {
            if (!arr[bi]) continue;
            b = arr[bi];
            arr[bi] = 0;
            // 个位
            for (int ci = 0; ci < 9; ci++) {
                if (!arr[ci]) continue;
                c = arr[ci];
                arr[ci] = 0;
                int num1, num2, num3;
                // 生成 num1, 它是   a b c
                num1 = 100 * a + 10 * b + c;
                // 生成 num 2,分解为 d e f
                num2 = 2 * num1;
                int d = num2 / 100 % 10, e = num2 / 10 % 10, f = num2 % 10;
                // 分解 num 3,分解为 h i j
                num3 = 3 * num1;
                int h = num3 / 100 % 10, i = num3 / 10 % 10, j = num3 % 10;
                if ((e != 0) && (f != 0) && (i != 0) && (j != 0)) {
                    // printf("\n%d %d %d\n", num1, num2, num3);
                    // 放到数组中
                    char tmp[9] = {a, b, c, d, e, f, h, i, j};
                    // 找不一样
                    int flag = 0;
                    for (int fi = 0; fi < 9; fi++) {
                        for (int fn = 0; fn < fi; fn++) {
                            // printf("%d %d\n", tmp[fi], tmp[fn]);
                            if (fn != fi && tmp[fi] == tmp[fn]) {
                                // 如果它有相等，证明他不是一个互不相同的数字
                                // printf("Fuck1");
                                flag = 1;
                            }
                        }
                    }
                    // 如果flag是0，他是一个互不相同的数字
                    if (!(flag))
                        printf("找到你了！ %d %d %d\n", num1, num2, num3);
                }
                // 恢复数字
                // arr[ai] = a;
                arr[bi] = b;
                arr[ci] = c;
            }
        }
    }
    return 0;
}