本文的问题分析过程参考了http://blog.csdn.net/lyy289065406/article/details/6648444
大致题意：
有k个坏人k个好人坐成一圈，前k个为好人（编号1~k），后k个为坏人(编号k+1~2k)
现在有一个报数m，从编号为1的人开始报数，报到m的人就要自动死去。
问当m为什么值时，可以使得在出现好人死亡之前，k个坏人先全部死掉？
PS:当前一轮第m个人死去后，下一轮的编号为1的人 为 前一轮编号为m+1的人
前一轮恰好是最后一个人死掉，则下一轮循环回到开头那个人报“1”
解题思路:
经典的约瑟夫水题
由于k值比较少（1~13），暴力枚举m就可以了
递推公式为：
ans[i]; //第i轮杀掉 对应当前轮的编号为ans[i]的人
ans[0]=0;
ans[i]=(ans[i-1]+m-1)%(n-i+1); (i>1 , 总人数n=2k 则n-i为第i轮剩余的人数)
有耐心的同学可以自己推导一下公式。。。
推导时要注意2点:
第一：每轮都是以前一轮死掉的人的后一个人作为“1”开始顺序编号的
如：k=2 (n=4) m=7
|
1 |
|
4 |
|
3 |
|
2 |
那么最初的编号如下
第一轮报数后，3号被杀掉，那么以3号后面的一个人“4”作为下一轮的“1”重新编号
第二：
f[i]=(f[i-1]+m)%(n-i); (i>1)
这是网上一些地方给出的递推公式，对于本题而言是不正确的。因为这种递推公式针对的是从0开始报数的Joseph，本题是从1开始报数的，必须要变形
最后就是由于本题k值有限，只有13个值，那么POJ的数据测试就极有可能重复测试每个k值的结果，为了节省总体时间，我们的程序只在第一次得到k值的时候计算m值，然后保存下来，当k值再次出现时，就直接把保存的结果输出，不再计算m。这是在服务器打表的处理。
另外有了递推的程序后，我们就知道了每个k值对应的m值。
此时追求0ms AC的同学可以利用递推程序的结果，再写一个程序，直接在程序里面打表
int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
package com.njupt.acm;
import java.util.Scanner;
public class TestPOJ1012 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//以下store[]数组中存储的是报表的相应结果，可以在我的。打表程序已经在另一篇博客中单独给出
int[] store={2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
int k = 0;
while(true){
k = scanner.nextInt();
if(k==0){
break;
}else{
System.out.println(store[k-1]);
}
}
}
}