1
2

50.00%

1、n 個人 n 張票，就有 n! 種排列情況。我們需要做的就是從這 n! 種情況中，找出 n 個人所有的錯排情況。

2、假設有 n 個人，錯排情況數是 f ( n ) ，把他們分成 1 個人和 n - 1 個人兩部分。有如下 3、4 兩種情況：

3、假設 1 個人拿的是自己的票， n - 1 拿的都不是自己的票，那麼這 1 個人只需要和這 n - 1 個人中任何一個人交換一下票，就可滿足 n 個人錯排。所以有 ( n - 1 ) * f ( n - 1 ) 。

4、假設 n - 1 個人其中有一個人拿的是自己的票，1 個人拿的不管是不是自己的票，只要和 n - 1 個人當中那個拿自己票的人交換一下，就可滿足 n 個人錯排。而且，n - 1 個人當中除掉拿自己票的人，n - 2 個人肯定滿足錯排。所以又有 ( n - 1 ) * f ( n - 2 ) 。

綜上所述：f ( n ) = ( n - 1) * [ f ( n - 1 ) + f ( n - 2 ) ]

寫程序時，可以利用一個二維數組cases [ 21 ] [ 2 ] ，數組第 0 列存儲 n 個人的所有排列情況 n! ，數組第 1 列存儲 n 個人的錯排情況 f ( n ) = ( n - 1) * [ f ( n - 1 ) + f ( n - 2 ) ]

import java.util.Scanner;

public class Main {

	static long[][] cases = new long[21][2];

	static {
		cases[1][0] = 1;
		cases[1][1] = 0;
		cases[2][0] = 2;
		cases[2][1] = 1;

		for (int i = 3; i < 21; i++) {
			cases[i][0] = i * cases[i - 1][0];
			cases[i][1] = (i - 1) * (cases[i - 1][1] + cases[i - 2][1]);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		while (n-- != 0) {
			int count = scanner.nextInt();

			System.out.printf("%.2f", 100.0 * cases[count][1] / cases[count][0]);
			System.out.println("%");
		}
	}
}