三國佚事——巴蜀之危

7-7 三國佚事——巴蜀之危 (20 分)

話說天下大勢，分久必合，合久必分。。。卻道那魏蜀吳三國鼎力之時，多少英雄豪傑以熱血譜寫那千古之絕唱。古人誠不我欺，确是應了那句“一将功成萬骨枯”。

是夜，明月高懸。諸葛丞相輕搖羽扇，一臉愁苦。原來是日前蜀國戰事吃緊，丞相徹夜未眠，奮筆急書，于每個烽火台寫下安排書信。可想，這戰事多變，丞相運籌 帷幄，給諸多烽火台定下不同計策，卻也實屬不易。

誰成想這送信小厮竟投靠曹操，給諸葛丞相暗中使壞。這小厮将每封書信都投錯了烽火台，居然沒有一封是對的。不多時小厮便被抓住，前後之事卻也明朗。這可急壞了諸葛丞相，這書信傳錯，勢必會讓蜀軍自亂陣腳，不攻自破啊!

諸葛丞相現在想知道被這小厮一亂，這書信傳錯共有多少種情況。

輸入格式:

輸入一個正數n，代表丞相共寫了n（1 <= n <= 20）封書信。

輸出格式:

輸出書信傳錯的情況數。

輸入樣例:

3

輸出樣例:

2

這裡普及一下錯排的知識，就是每個都找錯的情景，假設n本書錯排數量是：錯排（n）

假設有1~n個書包，每個書包裡有着屬于自己的書本，如果要将n個書本全部放錯，有兩種情況，先假設第k本書錯放在第m個書包裡，這有n-1種情況（比較好了解，就是從不是m的餘下幾本書裡任意找一本）

1、此時如果我們将第m本書放在第k個書包裡，就在此時，我們要在此錯排餘下的n-2個書包，這是不影響這n-2個錯排的，因為第k本書占了第m個書包，第m本書占了第k個書包，是以這種情況是（n-1)*錯排（n-2）

2、此時如果我們将第m本書不放在第k個書包裡，很意外的是就在此時，我們找到了一個條件就是我們不允許第m本書放在第k個書包裡，此時，我們已經踢出一個書包和一本書，就和n-1個錯排的情況是一樣的，即使第m本書和k個書包無關，但在我們讨論的條件下，是不允許這種情況發生，是以，非常類似于n-1個錯排，是以這種情況是（n-1)*錯排（n-1）

#include<stdio.h>
int main()
{
    int n,i;
    long long int a[60];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        if(i==1)
            a[i]=0;
        else if(i==2)
            a[i]=1;
        else
        a[i]=(i-1)*(a[i-1]+a[i-2]);
    }                                
    printf("%lld",a[n]);
}
           

這裡對自己的講解還是感覺非常有味道的，是以直接上代碼