- public class Test7 {
- /**
- * 题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
- * 约瑟夫环问题;
- * 通过分析:我们可以的到一个约瑟夫环问题的递推公式
- * 递推公式 f[1]=0;
- * f[i]=(f[i-1]+m)%i;
- * (住:这个公式并不是我推出来的)
- * 通个这个公式就可以很方便的秋出最后一个人,但是无法还原过程
- */
- public static void main(String[] args) {
- int n = 5; //总人数
- int m = 3; //每次要退出的数
- int s = 0;
-
- for(int i = 2;i<=n;i++){
- s= (s+m)%i;
- }
- //实际生活中编号总是从1开始,我们输出f[n]+1(也就是s+1)
- System.out.println(s+1);
- }
- }
复制代码 |
|