下面鄙人分享解答“deepin论坛打卡赛“的一些思路，其中不免存在些许问题，望见谅。

题一

小明五次输入四位数的手机密码均错误,但是每次输入的密码中有两位数字正确，位置都不对。现求小明正确的四位数手机密码?

五次手机密码分别是:

6087 5173 1358 3825 2531

解题思路：

根据密码中数字出现的次数进行初步判断：出现 4 次该数字必然不属于密码数字，出现 3 次可以确定该数字的准确位置。

首先构建密码图形：

统计数字出现次数：

由题设可知：由于位置都不对，所以每个数字出现的次数小于 4。排除 3 和 5 这两个数字。通过最后四行可知，必然有：1、8、2 、7这四个数字。由此我们得到密码准确数字，现在考虑密码的顺序。

有题设知，密码的位置都不正确，所以可以利用反证法确定某些数字位置。

可以看到 8 和 1 的次数均出现 3 次，那么可以精确确定其位置：

同时也可以确定 7 的位置，因为 8 已经占据首位，所以 7 必定位于第二位，由此得到最终答案：

题二

往一个篮子里放鸡蛋，假定篮子里的鸡蛋数目每分钟增加1倍，这样，12分钟后，篮子满了。那么请问在什么时候是半篮子鸡蛋?

由于每分钟增加 1 倍，可以简单的构建该模型函数 ​N=2^{n}\quad n\in(1,2,3,...,12) ,

由于 12 分钟后篮子满了，那么可以得到：

现在找出半篮子鸡蛋的时间，即 ​C/2 个鸡蛋的时间，

所以，在第 11 分钟时为半篮子鸡蛋。

题三

一个袋子里有5个红球，3个蓝球，2个绿球。随机抽取5个球，求至少有3个红球的概率。

至少有 3 个红球的概率可以通过反证法考虑：恰好有 3 个红球、恰好有 4 个红球、恰好有 5 个红球的概率和。设 ​P 为至少有 3 个红球的概率，那么可得

所以至少有 3 个红球的概率为 ​\frac{1}{2} 。

题四

有10个人围成一圈，分别为编号1-10，每个人手中有一个随机的不同的数字卡片，也是从1到10。如果每个人依次交换卡片，且只能与他相邻的两个人交换卡片，最少需要多少次交换，才能让每个人最终都拿到与自己编号相同的卡片？

事实上，本题可以看作是一个排列问题。

由题设可知每人拿到的是随机不同的数字卡片，那么我们假设相邻二者两两交换，即

那么仅需 5 次即可让每个人拿到与自己编号相同的卡片。现在尝试去寻找交换次数小于 5 次的卡片排列方式。

但是这显然是不可能的，每人仅能和左右相邻交换卡片，所以必然需要花费 5 次及以上。

题四（改）

在一个古老的城堡里，有一个神秘的房间，里面藏有宝藏。房间的门上有一个密码锁，密码是一个四位数。城堡的守护者留下了一个线索，这个线索是一个数学表达式，表达式的结果是这个四位数密码。数学表达式如下：

其中A、B、C和D是1到9之间的整数，且每个数字只能使用一次。城堡的守护者还留下了另一个线索：A、B、C和D的和是16。

密码=1000×(A−1)+100×(B−2)+10×(C−3)+(D−4)

请问，正确的四位数密码 ABCD分别是什么呢？

由题设可以使用一个简单的程序得到结果。

下面我给出具体 C++代码：

#include 

bool isValidPassword(int password) {
    return 1000 <= password && password <= 9999;
}

int main() {
    for (int A = 1; A <= 9; ++A) {
        for (int B = 1; B <= 9; ++B) {
            for (int C = 1; C <= 9; ++C) {
                int D = 16 - A - B - C; // 计算D的值
                if (D >= 1 && D <= 9 && A != B && A != C && A != D && B != C && B != D && C != D) {
                    // 计算密码
                    int password = 1000 * (A - 1) + 100 * (B - 2) + 10 * (C - 3) + (D - 4);
                    // 如果密码是四位数，则输出
                    if (isValidPassword(password)) {
                        std::cout << "数字组合: (" << A << ", " << B << ", " << C << ", " << D << "), 密码: " << password << std::endl;
                    }
                }
            }
        }
    }

    return 0;
}

具体结果为：

数字组合: (2, 3, 4, 7), 密码: 1113
.
.
.

简化输出方式为得到的全部结果为：

[ 2347, 2356, 2365, 2374, 2419, 2437, 2473, 2491, 2518, 2536, 2563, 2581, 2617, 2635, 2653, 2671, 2716, 2734, 2743, 2761, 2815, 2851, 2914, 2941, 3148, 3157, 3175, 3184, 3247, 3256, 3265, 3274, 3418, 3427, 3472, 3481, 3517, 3526, 3562, 3571, 3625, 3652, 3715, 3724, 3742, 3751, 3814, 3841, 4129, 4138, 4156, 4165, 4183, 4192, 4219, 4237, 4273, 4291, 4318, 4327, 4372, 4381, 4516, 4561, 4615, 4651, 4723, 4732, 4813, 4831, 4912, 4921, 5128, 5137, 5146, 5164, 5173, 5182, 5218, 5236, 5263, 5281, 5317, 5326, 5362, 5371, 5416, 5461, 5614, 5623, 5632, 5641, 5713, 5731, 5812, 5821, 6127, 6145, 6154, 6172, 6217, 6235, 6253, 6271, 6325, 6352, 6415, 6451, 6514, 6523, 6532, 6541, 6712, 6721, 7126, 7135, 7153, 7162, 7216, 7234, 7243, 7261, 7315, 7324, 7342, 7351, 7423, 7432, 7513, 7531, 7612, 7621, 8125, 8134, 8143, 8152, 8215, 8251, 8314, 8341, 8413, 8431, 8512, 8521, 9124, 9142, 9214, 9241, 9412, 9421, ]

对该题目，鄙人存在以下疑惑：

• 题目的规则是否稍许宽泛？以至于存在相当多的结果，对于缺乏编程经验的朋友并不友好。
• 抛开使用遍历的方式寻找答案，以数学思想建立模型方式求解并不复杂，是否有些简单？
• 在题意上是否有些不严谨？每个数字仅使用一次，是单个密码中不存在重复数字，还是整个密码集合不存在重复数字？

题五

数列1, 1, 2, 3, 5, 8, 13, ... 被称为斐波那契数列，其中每个数字是前两个数字的和。求第20项的值。

答案为 6765，使用动态规划而非递归求解。

原因在于：斐波那契数列的增长速度非常快，第 20 项就已经超过 int 类型范围，同时由于递归调用的深度和计算量都非常大，频繁调用较大数字（哪怕仅有 20 项），使用动态规划或者矩阵连乘等算法都更为优秀。

下面是使用动态规划的 C++代码：

#include 
#include 

unsigned long long fibonacci(int n) {
    if (n <= 1)
        return n;

    std::vector fib(n + 1, 0);
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n = 20;
    std::cout << "斐波那契数列的第 " << n << " 项是: " << fibonacci(n) << std::endl;
    return 0;
}