題目描述

? ? ? ? 某人寫了n封信和n個信封，如果所有的信都裝錯了信封，共有多少種不同情況？

?

輸入輸出格式

輸入格式

? ? ? ? 一行，一個整數n（n≤10）。

?

輸出格式

? ? ? ? 一行，為所有的情況數。

?

輸入輸出樣例

輸入樣例

4

?

輸出樣例

9

?

題解

? ? ? ? 現在假設有$i$封信需要處理。

? ? ? ? 當第$i$封信放在$[1,i)$中的第$j$個信封時，如果第$j$封信放到了第$i$個信封中，我們其實可以把當前情況下的情況數看做只有$(i-2)$封信的情況數。

? ? ? ? 但如果第$j$封信放在了$[1,i)$中的第$k$個信封時，其實我們可以把第$i$個信封看做第$j$個信封，忽略實際已放了第$i$封信的第$j$個信封，這樣我們就可以把當前的情況數看做只有$(i-1)$封信的情況數。

? ? ? ? 這樣就可以得到遞推式：$a[i]=(i-1)\times(a[i-1]+a[i-2])$。

#include <iostream>using namespace std;int n; int a[11] = {0,1,1,2};int main() {cin >> n;for(int i = 4; i <= n; i++){a[i] = (i - 1) * (a[i - 1] + a[i - 2]); }cout << a[n];return 0; } 參考程序

?

轉載于:https://www.cnblogs.com/kcn999/p/10661679.html

總結

以上是生活随笔為你收集整理的【题解】错排问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。