传说中的约瑟夫环问题,刚开始想到的就是模拟,输入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.*;
2
import java.util.*;
3
class 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
}
44
posted on 2013-03-21 14:34
小鼠标 阅读(199)
评论(0) 编辑 收藏 引用 所属分类:
Java基础练习