黑马程序员技术交流社区

标题: 发一个约瑟夫环问题的简单解决方法 [打印本页]

---

作者: 罗中扬    时间: 2014-6-10 17:09
标题: 发一个约瑟夫环问题的简单解决方法

1. public class Test7 {
   
2.         /**
   
3.          * 题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
   
4.          * 约瑟夫环问题；
   
5.          * 通过分析：我们可以的到一个约瑟夫环问题的递推公式
   
6.          * 递推公式   f[1]=0;
   
7.      *        f[i]=(f[i-1]+m)%i;
   
8.      *      （住：这个公式并不是我推出来的）
   
9.          * 通个这个公式就可以很方便的秋出最后一个人，但是无法还原过程
   
10.          */
    
11.         public static void main(String[] args) {
    
12.                 int n = 5;  //总人数
    
13.                 int m  = 3;   //每次要退出的数
    
14.                 int s = 0;
    
15.                
    
16.                 for(int i = 2;i<=n;i++){
    
17.                         s= (s+m)%i;
    
18.                 }
    
19.                 //实际生活中编号总是从1开始，我们输出f[n]+1（也就是s+1）
    
20.                 System.out.println(s+1);
    
21.         }
    
22. }

复制代码

---

作者: 马宁    时间: 2014-6-10 18:51
看看。。。

---

作者: 过犹不及    时间: 2014-6-10 22:19
看到过好几次这样的题目了。不过每次都没搞懂

---

作者: 闪耀.Q    时间: 2014-6-10 22:26
来学习了

---

作者: 唐坚    时间: 2014-6-11 01:04
公式还没搞懂怎么来的

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2