一个巧妙的约瑟夫环算法

int fun(int n, int m)
{
int i, r = 0;
for (i = 2; i <= n; i++)
r = (r + m) % i;
return r+1;
}
就是一共n个人，查到m的人出圈，求最后圈里的人是几号。好巧妙啊，想了半天也想不明白。r = (r + m) % i; 这一步为什么求模？请路过的大侠看下

思路如下：

当第一个人退出后，此时剩下的n-1人还是一个圈，从第m个人开始重新一轮报数。于是只要把这个人重新定义为编号0，那么就是一个f[n-1]的子问题了。

而此时的n-1个编号转化为：

m --> 0
m+1 --> 1
m+2 --> 2
...
m-2 --> n-2
m-1 --> n-1

归纳以下，就是 原编号 = (现编号+k)%n。

因此我们可以写出递推公式了。

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果是f[n]

递推公式：
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

你这个程序就是计算这个递推公式f[n]的值。

用JAVA写的import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.InputStreamReader;

public class Questiontest { public static void main(String[] args) { int renshu = 0, number = 3, n = 0;// renshu总数，n当前要删除，也是报数的开始 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { renshu = Integer.parseInt(br.readLine());

} catch (Exception e) {

} boolean[] arry = new boolean[renshu]; for (int i = 0; i < arry.length; i++) { arry[i] = true; } int leftCount = arry.length;//一次要数的总人数 int countNum = 0;//数的数是几 int index = 0;//第一个人的下标 while (leftCount > 1) { if (arry[index] == true) { countNum++; //当数到三时，退出，从一在说 if (countNum == 3) { countNum = 0; arry[index] = false; leftCount--;//总人数减1 } } index++;//下标加1 //判断是否是最后一个人与第一个人是否可以联接 if (index == arry.length) { index = 0;//第一个接到最后一个人数 } } for (int i = 0; i < arry.length; i++) { if (arry[i] == true) { System.out.println(i+1); } } }

}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息