不会飞的章鱼

任务

如果给你一个文本串和模式串，让你查找文本串中是否包含模式串，你用程序怎么完成？

字符串匹配问题

在一个大的字符串里面，查找是否包含另外一个较小的字符串。

任务

请你实现一个程序，输出 2 的 1000 次方的结果是多少。

思考

• C 语言中给我们提供的 int 类型，肯定是无法完成这个任务的，因为它表示不了这么大的数字。
• 用 long long 类型来进行解决，但long long 是 64 位整型，也就是占 64 个 2 进制位，它顶多能表示 2 的 64 次方减 1 的结果，相对于 2 的 1000 次方来说，小太多了。
• 用double类型进行解决，但存在一个严重的问题，就是 double 是有精度损失的。
  （double 的表示精度，一般来说是有效数字 15 位，就是一个数字，由左向右，从第一个不为零的数字起，向后 15 位都是准确的。因此 double 类型实际上也没有办法，准确表示 2 的 1000 次方的计算结果。）

那该怎么办呢？

任务

求出 10000 以内所有数字的因数和。

可能已经想好的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
int sum[10005] = {0};

void init_sum() {
    // 循环遍历 1 到 10000 的所有数字
    for (int i = 1; i <= 10000; i++) {
        // 用 j 循环枚举数字 i 可能的因数
        for (int j = 1; j <= i; j++) {
            // 当 i%j 不等于 0 时，说明 j 不是 i 的因数
            if (i % j) continue;
            sum[i] += j;
        }
    }
    return ;
}

int main() {
    init_sum();
    printf("hello world\n");
    return 0;
}

效率较低，所以弃了。

题目

find-the-duplicate-number

解法一

• 建立一个key为int，value为int的map；
• 第一遍for range循环遍历nums数组，将nums数组里的元素出现的次数记录进map中；
• 第二遍for range循环遍历map，将value不为1的num取出返回，即为重复数。

这个解法需要用两次for循环，效率不高，下面我考虑用第二种解法。

任务

求 1 万以内所有素数的和。

编码

素数筛算法介绍

所谓素数筛，是将其产出的信息存储在一个标记数组中，数组的第 i 位，标记的是 i 这个数字是否是合数的信息。如果 i 这个数字是合数，数组下标为 i 的位置就被标记成为 1，如果 i 不是合数，则数组下标为 i 的位置就是 0。素数筛就是通过一套算法流程，产生一个这样的数组。

任务

求出 1000 以内所有 3 或 5 倍数的数字的和。

编码

一份合格的程序实现

1
2
3
4
5
6
7
8
9

#include <stdio.h>
int main() {
    int sum = 0;
    for (int i = 1; i < 1000; i++) {  //循环遍历 1000 以内的所有整数
        sum += i * (i % 3 == 0 || i % 5 == 0);  //把 3 或 5 的倍数累加到变量 sum 中
    }
    printf("%d\n", sum);  //最后输出 sum 变量的值，就是 1000 以内，所有 3 或 5 的倍数和。
    return 0;
}

任务

实现一个可变循环层数的程序。

编码

我们可以一开始假设，有一个函数，是实现 5 层循环打印的程序，那么它会循环 n 次，每次调用一个实现 4 层循环打印的程序。

1
2
3
4
5
6
7
8
9
10
11

//代码框架
int print_loop(int k, int n) {
    //代表 k 层循环的程序，然后循环 n 次，每次调用一个 k - 1 层循环的程序。
    if (k == 0) {
        // 打印一行
    }
    for (int i = 1; i <= n; i++) {
        print_loop(k - 1, n);
    }
    return;
}

任务

请你实现一个打印“漂亮日志格式”的方法。

首先我们先说“日志”的作用，程序中的“日志”，通常是指在程序运行过程中，输出的一些与程序当前状态或者数据相关的一些信息。这些信息，可以帮助程序开发人员做调试，帮助运营人员做数据分析，帮助管理人员分析日活等等。总而言之，一份合理的日志信息，是非常有价值的数据。而我们今天呢，接触一种最简单的日志形式，就是程序运行过程中的调试信息。

请你实现一个参数形式和 printf 函数一样的 log 方法，用法如代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>

void func(int a) {
    log("a = %d\n", a);
}

int main() {
    int a = 123;
    printf("a = %d\n", a);
    log("a = %d\n", a);
    func(a);
    return 0;
}

任务

仿照 scanf 函数，实现一个低配版的 my_scanf 函数。这个函数的功能，简单来说就是将一个字符串信息转换成整型数字，能够完成这个任务，你会更深刻的理解 scanf 函数，更深刻的理解参数设计。

例如：

1
2
3
4
5
6
7
8
9

//第一个基础功能
int n = 98;
my_scanf("12345", &n);
printf("%d", n); // 输出 12345，而不是 98

//第二个基础功能
int n = 98, m = 0;
my_scanf("123 45", &n, &m);
printf("n = %d m = %d", n, m); // 输出 n = 123 m = 45

实现

任务

假设有如下结构体数组，请看如下代码：

1
2
3

struct Data {
    int x, y;
} a[2];

请用尽可能多的形式，替换下面代码中 &a[1].x 的部分，使得代码效果不变：

1
2

struct Data *p = a;
printf("%p", &a[1].x);