传说中的约瑟夫环问题，刚开始想到的就是模拟，输入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
小鼠标 阅读(196)
评论(0) 编辑 收藏 引用 所属分类:
Java基础练习