黑马程序员技术交流社区

标题: 数学问题：约瑟夫环问题 [打印本页]

---

作者: doevents    时间: 2013-9-11 20:33
标题: 数学问题：约瑟夫环问题
什么是约瑟夫环？
约瑟夫环是一个数学问题：五百个学生手拉手站成一圈，从第一个孩子开始数数，数到三的学生退出，然后从下一个，开始数，再到三，是第三个的再退出。直到最后有一个学生为止,下面的代码就是实现此项功能的。

Josephus.java
public class Josephus {
public static void main(String[] args) {
  Jose();
}
//定义约瑟夫环方法体
private static void Jose() {
  boolean[] arr=new boolean[500]; //定义500个学生
  for(int i=0;i<arr.length;i++) {
   arr=true;
  }
  int leftcount=arr.length;
  int countNum=0; //定义数到3
  int index=0; //定义索引
  while(leftcount>1) { //但人数大于1才可以开始数数。
   if(arr[index]==true) {
    countNum++;
    if(countNum==3) { //当数到3的时候，数到3的人退出，累加器归零，重新数数
     countNum=0;
     arr[index]=false; //将数值变为false
     leftcount--; //总人数减1
    }
   }
   index++; //位置递增
   
   if(index==arr.length) { //如果index等于总人数，索引值清空。
    index=0;
   }
  }
  for(int i=0;i<arr.length;i++) {
   if(arr==true) {  //打印出最后一个为真的人
    System.out.println(i);
   }
  }
}
}

Count3Quit.java

public class Count3Quit{
public static void main(String []args){
   //定义一个数组用来当做500个人.并且初始化为true表示都在圈内
   boolean[]  arr =new boolean[500];
   for(int i=0; i<arr.length; i++){
    arr=true;
   }
   //定义一个总人数
   int count=arr.length;
   //定义一个索引位置,表示当前在那个位置
   int index=0;
   //计数器,数到3退出
   int countNum=0;
   //如果只剩下最后一个人就退出循环
   while(count>1){
  
    if(arr[index]==true){ //如果当前的这个人在圈内就开始数数
     
     countNum++;
   
     if(countNum==3){
     
      countNum=0; // 如果数到3了就要把计数器归0
     
      arr[index]=false; //表示这个人已经退出
     
      count--; //总人数减去一个，表示这个人已经退出  
     
     }
    }
   
    index++;
   
    if(index==arr.length){
     index=0;
    }     
   }
   //找到最后一个在圈子内的人的下标位置
   for(int i=0 ;i<arr.length; i++){
    if(arr==true){
     System.out.println("最后剩下的一个人在第"+(i+1)+"个位置");
    }
   }
}
}
代码写了好久，不知道还有什么欠缺，请大家提出来，我好修改，谢谢。{:soso_e100:}

---

作者: Yuan先生    时间: 2013-9-11 20:52


约瑟夫环问题：由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.         
public void xunHuanShanChu(){   
        //提示输入总人数
    System.out.println("请输入做这个游戏的总人数：");
    Scanner sca=new Scanner(System.in);
    int m=sca.nextInt();
    System.out.println("请输入要出圈的数值："); //提示输入要出圈的数值
    int n=sca.nextInt();
    System.out.println("按出圈的次序输出序号：");        
　　　int[] a=new int[m];//创建有m个值的数组        
    int len=m;//初始长度，以后出圈一个，长度就减一
    for(int i=0;i<a.length;i++){//给数组赋值
        a=i+1;
　　　}        
    int i=0;//i为元素下标
    int j=1;//j代表当前要报的数
    while(len>0){
        if(a[i%m]>0){
           if(j%n==0){//找到要出圈的人，并把圈中人数减一
//             if(len == 1){   // 输出最后一个人的序号
                   System.out.print(a[i%m]+"  ");
                   System.out.print("     "+"i = " + i);
                   System.out.println("     "+"i % "+ m+" =" + i%m);
//               }
                    a[i%m]=-1;
                    j=1;
                    i++;
                    len--;
                }else{
                    i++;
                    j++;
                }
            }else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
                i++;
            }
        }
}

---

作者: 无所谓啦    时间: 2014-8-23 08:42
赞！！！！！！

---

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

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