發郵件

nowcoder每天要給很多人發郵件。有一天他發現發錯了郵件，把發給a的郵件發給了b，把發給b的郵件發給了a。于是他就思考，要給n個人發郵件，在每個人僅收到1封郵件的情況下，有多少種情況是所有人都收到了錯誤的郵件？ 即沒有人收到屬于自己的郵件。

輸入描述:

輸入包含多組資料，每組資料包含一個正整數n（2≤n≤20）。

輸出描述:

對應每一組資料，輸出一個正整數，表示無人收到自己郵件的種數。

示例1

輸入

2 3

輸出

1

思路了解以及代碼實作：

錯排問題

當n個編号元素放在n個編号位置，元素編号與位置編号各不對應的方法數用d（n）表示，那麼d(n-1)就表示n-1個編号元素放在n-1個編号位置，各不對應的方法數，其它類推.

第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；

第二步，放編号為k的元素，這時有兩種情況：

⑴把它放到位置n，那麼，對于剩下的n-1個元素，由于第k個元素放到了位置n，剩下n-2個元素就有d(n-2)種方法；

⑵第k個元素不把它放到位置n，這時，對于這n-1個元素，有d(n-1)種方法；

綜上得到

d(n) = (n-1) [d(n-2) + d(n-1)]

特殊地，d(1) = 0, d(2) = 1.