不会飞的章鱼

任务

众所周知，在不计算小于 1 元钱的面额的前提下，我国的纸币系统中，曾经拥有如下面值：1 元、2 元、5 元、10 元、20 元、50 元 和 100 元。假设，每一种面值的纸币，我们都有无限张，现在想用这些钱凑出 1000 元，请问你有多少种不同的方案？

这里说的不同方案，是不关注钱币之间的顺序的，例如要凑 7 元钱，可以是 1 元、5 元、1 元，也可以是 1 元、1 元、5 元，这两种方案我们视为同一种。

编码实现

容斥原理

任务

假设有一面木板墙，每块木板的宽度都是 1，你现在想在木板墙上，沿着平行于地面的方向，切割出一块矩形区域。问题来了，如果给出了每一块木板的高度，那么如何切出面积最大的矩形区域？矩形木板墙如下图所示：

思考

图中有 7 块木板，每块木板的高度分别为：2、1、4、5、1、3、3。经过尝试，我们发现最大矩形就是红色阴影部分所示，也就是切割了高度为 4 和 5 两块木板，形成了一个高度为 4，宽度为 2 的矩形区域，这个最大面积为 8。

今天看了天气，不是很热，和女朋友计划去龙潭水乡玩一玩。

坐车大概花了一个半小时，因为是快速公交，时间上节约了大概半小时。

到达指定地点后，哇，人很少，很有江南水乡的气息，和小学语文课本上见到的一样呢。

到处都是桥，路面凹凸不平，水面上的荷花很好看，景区内也有穿着汉服拍照的小哥哥小姐姐。

我和她选择了一些人比较少的地方取景，摆姿势，不得不说，自己私底下看了看讲拍摄的文章，还是很有用，女朋友夸我拍照技术也进步了，哈哈。(可想而知以前在拍照上打击的有多惨～～～)

任务

滑动区间最大值，就是指在固定区间长度的前提下，在一个序列上，从前到后滑动这个区间窗口，每次窗口内部的最大值，就组成了滑动区间最大值。

例如，给你如下包含 8 个数字的序列，区间长度设置为 3：

1
2
3
4
5
6

[6 4 2] 10 3 8 5 9 -> 6
6 [4 2 10] 3 8 5 9 -> 10
6 4 [2 10 3] 8 5 9 -> 10
6 4 2 [10 3 8] 5 9 -> 10
6 4 2 10 [3 8 5] 9 -> 8
6 4 2 10 3 [8 5 9] -> 9

滑动区间从数字 6 开始出发，每次向右移动一个数字，同时把左边的一个数字丢出去，保持区间长度为 3，最后移动到数字 9 停止。可以看到，这个序列共包含 8 个数字，所以最后形成的滑动区间最大值共有 6 个，依次是 6、10、10、10、8、9。

百度网盘上的视频无法变速，我将分享一种我自认为最快解决的办法。

步骤一：添加快捷指令

打开iPad上的快捷指令；
选中共享表单快捷指令；
点击更改视频速度；
拉到最下面点击添加快捷指令。

步骤二：Safari浏览器

打开Safari浏览器，登录百度网盘，选中一个视频播放；
点击右上角有一个向上箭头的图标；
拉到下面有一个更改视频速度的选项；
选择可以接受的视频播放速度，完成。

任务

首先，我们定义一种数字名称，叫做“快乐数”。所谓快乐数就是经过有限次变换以后，等于 1 的数字。这个变换规则，给出一个非 1 的数字 a ，把它的位数拎出来，求各个位数的平方和，得到一个数字 b，如果数字 b 不是 1，那就对数字 b 的每一位数再做平方和，得到数字 c……经过不停的变换，确定最后能否得到 1。

例如，一开始的数字是 19，经过变换规则 12+92=82，得到数字 82；因为不是 1 ，所以接着做变换，就是 82+22=68，再做一次变换 62+82=100，最后一次做变换 12+02+02=1，得到了 1 以后，停止。

注：此题LeetCode链接

实现

任务

假设你手上有 n 段长度不等的绳子，你现在想将这些绳子进行裁剪，裁剪出 k 条长度相等的绳子，注意，只能剪断绳子，不能拼接绳子。问题就是，你能得到的这 k 段绳子的最长长度是多长？

如图所示，如果你手中有 3 条绳子，分别是 4 米、6 米 和 5 米，想要切出等长的 4 段，你会发现，每段最长就是 3 米。

思考

任务

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

字符串匹配问题

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

任务

请你实现一个程序，输出 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;
}

效率较低，所以弃了。