傳說中的約瑟夫環問題，剛開始想到的就是模擬，輸入10的時候就運行了數小時！網上搜索之后才知道是DP。這里有兩個重要的遞推公式：
1.
f[i] = (f[i - 1] + m) % i, f[1] = 0. f[i]表示
人數為i時最后活下來那個人的下標（從0開始），m為基數，即每數到m就讓該人出局
2.
f[i] = (f[i - 1] + m - 1) % (n - i + 1), f[0] = 0，f[i] 表示
第i輪出局的人的下標， n為一開始的總人數
解題用到的是第二個公式。
不過直接用遞推公式還是會超時，于是乎，我只好打表了。
代碼
1
import java.io.*;
2import java.util.*;
3class Main
4
{
5
6 public static void main(String[] args)throws Exception
7
{
8 Scanner sc = new Scanner(System.in);
9 int key[] = {0, 2, 7, 5,
10 30, 169, 441, 1872,
11 7632, 1740, 93313, 459901,
12
1358657, 2504881, 13482720};
13 int k = sc.nextInt();
14 while(k != 0)
15 {
16 /**//*for(int m = k + 1; ; m++)
17 {
18 if(isOK(k, m))
19 {
20 System.out.println(m);
21 break;
22 }
23 }*/
24 System.out.println(key[k]);
25 k = sc.nextInt();
26 }
27
28 }
29 public static boolean isOK(int k, int m)
30 {
31 int f = 0;
32 for(int i = 1; i <= k; i++)
33 {
34 f = (f + m - 1) % (2 * k - i + 1);
35 if(f < k)
36 {
37 return false;
38 }
39 }
40 return true;
41
42 }
43
}
44posted on 2013-03-21 14:34
小鼠標 閱讀(212)
評論(0) 編輯 收藏 引用 所屬分類:
Java基礎練習