前言
牛客網(wǎng)PAT乙級訓(xùn)練1020
題目描述
NowCoder每天要給很多人發(fā)郵件坎拐。有一天他發(fā)現(xiàn)發(fā)錯了郵件烦磁，把發(fā)給A的郵件發(fā)給了B，把發(fā)給B的郵件發(fā)給了A哼勇。于是他就思考都伪，要給n個人發(fā)郵件，在每個人僅收到1封郵件的情況下积担，有多少種情況是所有人都收到了錯誤的郵件陨晶？
即沒有人收到屬于自己的郵件。
輸入描述
輸入包含多組數(shù)據(jù)帝璧，每組數(shù)據(jù)包含一個正整數(shù)n（2≤n≤20）珍逸。
輸出描述
對應(yīng)每一組數(shù)據(jù)，輸出一個正整數(shù)聋溜，表示無人收到自己郵件的種數(shù)谆膳。
輸入例子
2
3
輸出例子
1
2
解析
這道題是一道典型的錯排問題，核心在于遞歸思想的運用撮躁。
用A漱病、B、C把曼、D.........表示寫著n位友人名字的信封杨帽，a、b嗤军、c注盈、d.........表示n份相應(yīng)的信，把n份信裝錯的總數(shù)記為D(n)叙赚，那么n-1份信封裝錯的總數(shù)就是D(n-1)老客。
現(xiàn)在，假設(shè)這樣一種情況震叮，把a錯裝進B中胧砰，那么對于信b有以下兩種分法：
- b裝入A中，這樣剩下的（n-2）份信和信封A苇瓣、B尉间，和信a、b就沒有任何關(guān)系了，所以這時候裝錯的可能性總共有D(n-2)哲嘲。
- b不一定裝入A中贪薪，那么就有可能裝入A、C眠副、D等其余除B之外的信封了古掏，這時總共就是(n-1)種裝錯的可能性了。
所以對于信b來說侦啸，總共有D(n-2)+D(n-1)種裝錯的可能性槽唾。所以最后除a之外還有（n-1）封信，所以最終的關(guān)系式如下：
D(n)＝(n－1)*[D(n－1)＋D(n－2)]
解決方案
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
long a[] = new long[n + 1];
a[1] = 0;
a[2] = 1;
if (n==2){
System.out.println(1);
}else {
for (int i = 3; i < n + 1; i++) {
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
}
System.out.println(a[n]);
}
}
}
}
