[Share Experiences] deepin论坛打卡赛解题思路分享
Tofloor
poster avatar
Free_Aaron.Li
deepin
2024-06-28 20:21
Author

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

题一

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

五次手机密码分别是:

6087 5173 1358 3825 2531

解题思路:

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

首先构建密码图形:

6 0 8 7
5 1 7 3
1 3 5 8
3 8 2 5
2 5 3 1

统计数字出现次数:

数字 次数
0 1
1 3
2 2
3 4
4 0
5 4
6 1
7 2
8 3
9 0

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

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

6 0 8 7
1 7
1 8
8 2
2 1

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

8 1

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

8 7 1 2

题二

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

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

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

\begin{aligned} N=C \\ C=2^{12} \\ \end{aligned}

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

\begin{aligned} \frac{C}{2}&=2^{n} \\ \frac{2^{12}}{2}&=2^{n} \\ n&=11 \end{aligned}

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

题三

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

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

\begin{aligned} P &= \frac{\begin{pmatrix} 5 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 5 \\ 2 \end{pmatrix}}{\begin{pmatrix} 10 \\ 5 \end{pmatrix}} + \frac{\begin{pmatrix} 5 \\ 4 \end{pmatrix} \cdot \begin{pmatrix} 5 \\ 1 \end{pmatrix}}{\begin{pmatrix} 10 \\ 5 \end{pmatrix}} + \frac{\begin{pmatrix} 5 \\ 5 \end{pmatrix} \cdot \begin{pmatrix} 5 \\ 0 \end{pmatrix}}{\begin{pmatrix} 10 \\ 5 \end{pmatrix}} \\ &= \frac{100}{252} + \frac{25}{252} + \frac{1}{252} \\ &= \frac{1}{2} \end{aligned}

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

题四

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

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

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

1 2 3 4 5 6 7 8 9 10
2 1 4 3 6 5 8 7 10 9

那么仅需 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;
}

Reply Favorite View the author
All Replies
阿尼樱奈奈
Moderator
2024-06-28 20:39
#1
Reply View the author
hanzn-zzx
deepin
2024-06-28 22:05
#2

like代码收下了,我要好好学一学啦

Reply View the author
吴标
deepin
2024-06-30 08:42
#3

厉害了,对第四题就觉得不好,答案太多了,最好是唯一的答案,另外第一次的4题我感觉最少肯定是一次,每个人交换一次才能算一次

Reply View the author
Free_Aaron.Li
deepin
2024-06-30 22:07
#4
吴标

厉害了,对第四题就觉得不好,答案太多了,最好是唯一的答案,另外第一次的4题我感觉最少肯定是一次,每个人交换一次才能算一次

您的这思路确实是我没想到的,一次是一次轮转的意思。

Reply View the author