遞歸入門——錯排及其應用

一、常見遞歸

​ 簡單題：母牛的故事、骨牌鋪方格、一隻小蜜蜂...。

​ 中等題：不容易系列之(3)—— LELE的RPG難題、阿牛的EOF牛肉串。

​ 較難題：神、上帝以及老天爺、不容易系列之(4)——考新郎。

​ 變态題：折線分割平面。

​ 簡單題，顯而易見的規律；中等題，略加思考推出來的規律；較難題，深度思考（其實是我高中數學弱，不會錯排???）；變态題，我想不出來，看題解也沒看懂的題。

二、遞推公式：斐波那契型

\[ F(n) = F(n-1) + F(n-2) \]

​ 上述題目除了折線分割平面之外，都是這個公式的變形。

較難題需要用到錯排，今天細講錯排。

三、錯排公式的推導和應用

錯排的定義：一段序列中一共有n個元素，那麼可知這些元素一共有n!種排列方法。假如在進行排列時，原來所有的元素都不在原來的位置，那麼稱這個排列為錯排。而錯排數所指的就是在一段有n個元素的序列中，有多少種排列方式是錯排。

\[ 遞歸關系：D(n)=(n-1)(D(n-1)+D(n-2)) 特别地有D(1)=0,D(2)=1； \\錯排公式：D(n)=(n!)[(-1)^0/0!+(-1)^1/(1!)+(-1)^2/(2!) +(-1)^3/(3!)+......+(-1)^n/(n!)]； \\其中n!=n*(n-1)*(n-2)*......3*2*1 特别地有0!=1\quad 1!=1 \]

遞推思想：

​ 一共分為兩步

第一步：

​ 錯排（不能選擇自己本來就在的位置）第一個元素，在n個位置中任選一個位置，有 n-1 種選法。

第二步：

​ 錯排其餘n-1個元素，也是需要分情況和種類的。因為這需要看第一步的結果，如果第一個元素落在第k個位置上，第二步就需要把k号元素進行錯排，k号元素錯排位置的不同将導緻不同的情況會發生：

①.假設k号元素正好落在了第一個元素的位置，那麼就可以将第一個元素和第k個元素完全剔除出去，因為相當于隻是他們兩者互換了位置，其他元素暫時還沒有發生變動。留下來的n-2元素進行錯排的話，那麼我們就可以得到了D(n-2)種 的錯排方式。

②.若k号元素不排到第一個元素的位置，我們可以暫時将現在排在k号位置的第一個元素剔除出去，生下來的就隻包含k号元素和原來n-2個的元素了。這時，我們可以将原來的第一個元素的位置看做是現在k号元素的原本位置，因為k号元素不能夠放在原來的位置上，是以就相當于是原來的n-2個元素和k共計n-1個元素進行完全的錯排。那麼一共就有D(n-1)種方法。

綜上所述:第二步得到D(n-1)+D(n-2)種方法，第一步是n-1種，由于是分步進行，是以結果為(n-1)*[D(n-1)+D(n-2)]種方法。

四、實戰

①神、上帝以及老天爺

​ 典型的錯排題目神、上帝以及老天爺，這道題的題意就是求所有的組合情況中錯排所占的比例，題目要求的就是這個。

\[ \frac{（n-1)*[D(n-1)+D(n-2)]}{N!} \]

下面就是AC代碼了：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    int s;
    double a[20+5] = {0,0,1};   //錯排的數組
    double b[20+5] = {2,2,2};   //全排的數組
    int i = 3;

    cin >> t;
    while(t--)
    {
        cin >> s;
        for( ; i <= s; i++)
        {
            a[i] = (i-1)*(a[i-1]+a[i-2]);   //錯排
            b[i] = b[i-1]*i;                //全排
        }
        cout << fixed << setprecision(2) << a[s]/b[s]*100 << "%" << endl;
    }
}                

②不容易系列之(4)——考新郎

​ 這道題的題意為在n對新人裡面挑出m對新人來錯排，那麼實際讓我們求得就是挑出m對新人的方法乘以m對新人的錯排方法。就是下面這個公式。

\[ C_n ^m*(n-1)*[D(n-1)+D(n-2)] \]

下面是AC代碼：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

ll factorial(int n, int m)  //求組合數
{
    ll ans = 1;
    if(m < n-m)
        m = n-m;
    for(int i = m+1; i <= n; i++)
        ans *= i;
    for(int j = 1; j <= n - m; j++)
        ans /= j;
    return ans;
}

int main()
{
    int t;
    int n, m;
    ll a[20+5] = {0,0,1};
    int i = 3;
    int temp;

    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        if( n < m)
        {
            temp = n;
            n = m;
            m = temp;
        }
        for( ; i <= m; i++)     //錯排
            a[i] = (i-1)*(a[i-1]+a[i-2]);
        cout << factorial(n,m)*a[m] << endl;//輸出錯排*組合數
    }
}
                

求組合數代碼（用階乘不到20就超出long long的範圍了）：

typedef long long ll;
ll factorial(int n, int m)  //求組合數
{
    ll ans = 1;
    if(m < n-m)
        m = n-m;
    for(int i = m+1; i <= n; i++)
        ans *= i;
    for(int j = 1; j <= n - m; j++)
        ans /= j;
    return ans;
}
                

轉載于:https://www.cnblogs.com/trirabbits/p/10108373.html