算法题数学推导过程求助

夜雨微澜

题目背景：

圣诞节快到了，公司为每个员工都准备了礼物，每个礼物都有一个精美的盒子。如果所有的礼物都不小心装错了盒子，求所有礼物都装错盒子共有多少种不同情况。

输入描述：

输入一个正整数n表示公司人数，保证n  ≤  20。

输出描述：

输出一个整数，代表有多少种情况。

样例1：

输入：

2

输出：

1
上述题目我的思路是用数学的方法求出都装错盒子的概率，然后使用总的方案数（即n！）乘以概率得出答案。
我的数学推理过程如图所示，但是在测试的时候发现我的推理结果似乎是错的。
例如n=3的时候，3的全排列共有123、132、213、231、312、321，其中全部装错的有231,312，装错的概率为三分之一，与我推理得出的答案不同。
求论坛各位高人指点我推理过程中的错误，谢谢

AntibioticsKss

在推导第二个盒子的地方有问题，后面的以此类推也有问题

我们先考虑第一个盒子装错的概率，显然是 $\dfrac{n-1}{n}$

然后考虑第二个盒子装错的概率，还是分成两种情况，这里应该使用全概率公式

1. 先考虑第一个盒子装了2号物品的情况： $\dfrac{1}{n-1}\times 1$
2. 然后考虑第一个盒子没有装2号物品的情况： $\dfrac{n-2}{n-1}\cdot\dfrac{n-2}{n-1}$

那么此时前两个物品都装错的概率就是 $\dfrac{n-1}{n}\cdot(\dfrac{1}{n-1}\times 1 + \dfrac{n-2}{n-1}\cdot\dfrac{n-2}{n-1})$

代入 $n=2$ 进去算可以得到概率是 $\dfrac{1}{2}$

为了证明这种算法的正确性，我再来推一下3个物体的情况吧

也是分成两种情况用全概率公式

1. 前两个盒子装了3号物品：$\dfrac{2(n-1)}{n(n-1)}\times 1$
2. 前两个盒子没有装3号物品：$\dfrac{(n-1)(n-2)}{n(n-1)}\cdot\dfrac{n-3}{n-2}$

此时前三个物品都装错的概率就是下面这个一长串的式子

$\dfrac{n-1}{n}\cdot\left(\dfrac{1}{n-1}\times 1 + \dfrac{n-2}{n-1}\cdot\dfrac{n-2}{n-1}\right)\left[\dfrac{2(n-1)}{n(n-1)}\times 1+\dfrac{(n-1)(n-2)}{n(n-1)}\cdot\dfrac{n-3}{n-2}\right]$

代入 $n=3$ 可以算到是 $\dfrac{1}{3}$

到这里显然这种办法过于复杂，并没有明显的规律，很难找出通式计算，正解应该是考虑错位重排问题递推求解，网上讲解很多，在此就不加赘述了

你好，再见

错排公式哦乖乖，看看这篇文章我觉得推导非常清晰
https://hanshuliang.blog.csdn.net/article/details/109438773

按照分步分类原则推出这个公式就可以写出代码了
D(n)=(n-1)(D(n-1)+D(n-2))

[C++] 纯文本查看 复制代码

//
// Created by Michael on 24-7-7.
//
#include <iostream>

#define endl '\n'
using namespace std;
using ll = long long;

using namespace std;

long long D(long long n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    return (n - 1) * (D(n - 1) + D(n - 2));
}

void solve() {
    long long n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return;
    }
    cout << D(n) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

十万菠萝拍黄瓜

后面的盒子能不能装错受前面盒子的影响, 每个盒子是不是装错,不是独立的情况, 不能相乘.
这个问题的意思就是n个物品,每个物品都不能在自己的盒子里,有两个特殊情况, n=1:  错不了,所以输出AAA(1)为0; n=2: 互相装错,所以输出AAA(2)为1;
n>2: 第n个物品不能在第n个盒子, 所以可以有n-1种放法, 假设在这n-1种随便放在了一个m盒子里(m 不等于 n), 此时n的位置确定了, 看一下m应该怎么放, 如果m放在n的位置, 那剩下的n-2个物品还会有AAA(n-2)种情况;(m和n一组,剩下的n-2个一组)
如果m没放在n的位置, 此时n物品已经放错,剩下的n-1个物品还会有AAA(n-1)种情况,所以m物品放错的情况一共有AAA(n-2) + AAA(n-1)种, 而m一共有n-1种取法,
所以当一共有n个物品时(n>2), 全错的情况AAA(n) = (n-1)*(AAA(n-2) + AAA(n-1))种.
例: 一共4个物品, 根据公式: AAA(4) = 3*(AAA(2)+ AAA(3)), 其中AAA(2)=1, AAA(3)=2*(AAA(1)+AAA(2))=2, 即AAA(4)=9

gchq2005

以三为例，全排列是 3*2*1=6 ，当要全装错的话，应该是 2*1*1=2  类推四的话，应该是 3*2*1*1=6

夜雨微澜

AntibioticsKss 发表于 2024-7-7 00:18
[md]在推导第二个盒子的地方有问题，后面的以此类推也有问题

我们先考虑第一个盒子装错的概率，显然是 $ ...

请问贝叶斯公式是什么，能不能通俗的解释一下，我只有初中的数学水平

AntibioticsKss

夜雨微澜 发表于 2024-7-8 22:12
请问贝叶斯公式是什么，能不能通俗的解释一下，我只有初中的数学水平

突然发现我写错了，应该是全概率公式

关于全概率公式，你可以先看一下百度百科
https://baike.baidu.com/item/全概率公式/

通俗解释的话，我举个例子吧
比如我有2个箱子，一个箱子里2个红球和3个白球，另一个箱子有3个红球和2个白球
那么现在有一个人从中任选一个箱子，再从箱子里任选一个球，此时拿到红球的概率是多少呢？
就是选第一个箱子的概率乘上在第一个箱子里选到红球的概率，加上选第二个箱子的概率乘上在第二个箱子里选到红球的概率
手机上写公式比较麻烦，这里就偷懒不写了（逃
算出来应该是二分之一