黑马程序员技术交流社区

标题: 发一个约瑟夫环问题的简单解决方法；大家指导指导 [打印本页]
作者: 罗中扬    时间: 2014-6-10 17:11
标题: 发一个约瑟夫环问题的简单解决方法；大家指导指导
  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. }
复制代码






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