黑马程序员技术交流社区

标题: 约瑟夫环 [打印本页]
作者: 何堂红    时间: 2014-6-7 20:13
标题: 约瑟夫环
本帖最后由 何堂红 于 2014-6-10 00:19 编辑
  1. 我这个代码得不得正确的结果，请帮我检查并给出正确的代码，谢谢！
复制代码
  1. public class Test01 {

  3.         /**
  4.          * 约瑟夫环:
  5.          *                 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列
  6.          * ；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
  7.          *         
  8.          * 需求：定义一个集合，从第一个元素开始，将第三个元素移除，直到剩下最后一个元素。
  9.          *
  10.          * @param args
  11.          */
  12.         public static void main(String[] args) {
  13.                 // 自定义数据类型
  14.                 // method1();
  15.                 // Integer数据类型
  16.                 // 创建有索引的集合，并添加元素
  17.                 List<Integer> list = new ArrayList<>();
  18.                 list.add(11);
  19.                 list.add(22);
  20.                 list.add(33);
  21.                 list.add(44);
  22.                 list.add(55);

  24.                 // 遍历集合
  25.                 for (int i = 0; i < list.size(); i++) {
  26.                         // 当数到第三个元素时，将其移除
  27.                         if (i % 3 == 2) {
  28.                                 list.remove(i);
  29.                                 i--;
  30.                         }
  31.                         // 当遍历到最后一个元素时，将其重新赋值为0，再次进行遍历
  32.                         if (i == list.size()) {
  33.                                 i = 0;
  34.                         }
  35.                 }
  36.                 System.out.println(list);
  37.         }
复制代码


作者: Conning    时间: 2014-6-7 22:36
  1. import java.util.Scanner;
  2. /**
  3. *使用数组实现约瑟夫环问题
  4. *由m个人围成一个首尾相连的圈报数。
  5. *从第一个人开始，从1开始报数，报到n的人出圈，
  6. *剩下的人继续从1开始报数，直到所有的人都出圈为止。
  7. *对于给定的m和n，求出所有人的出圈顺序.
  8. */
  9. public class RingTest{
  10.     public static void main(String[] args){
  11.         System.out.println("程序说明如下：");
  12.         System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
  13.         
  14.         //提示输入总人数
  15.         System.out.println("请输入做这个游戏的总人数：");
  16.         Scanner sca=new Scanner(System.in);
  17.         int m=sca.nextInt();
  18.         //提示输入要出圈的数值
  19.         System.out.println("请输入要出圈的数值：");        
  20.         int n=sca.nextInt();
  21.         System.out.println("按出圈的次序输出序号：");        
  22.         //创建有m个值的数组
  23.         int[] a=new int[m];
  24.         //初始长度，以后出圈一个，长度就减一
  25.         int len=m;
  26.         //给数组赋值
  27.         for(int i=0;i<a.length;i++)
  28.             a[i]=i+1;
  29.         //i为元素下表，j代表当前要报的数
  30.         int i=0;
  31.         int j=1;
  32.         while(len>0){
  33.             if(a[i%m]>0){
  34.                 if(j%n==0){//找到要出圈的人，并把圈中人数减一
  35.                     System.out.print(a[i%m]+"  ");
  36.                     a[i%m]=-1;
  37.                     j=1;
  38.                     i++;
  39.                     len--;
  40.                 }else{
  41.                     i++;
  42.                     j++;
  43.                 }
  44.             }else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
  45.                 i++;
  46.             }
  47.         }
  48.     }
  49. }
复制代码



出圈数值输入3即可
作者: yogaa    时间: 2014-6-7 22:46
本帖最后由 yogaa 于 2014-6-7 22:48 编辑

你写的那个约瑟夫环我是没太看懂，但是从你的需求来看，我是这样理解的，一步一步将集合中一直处于第三个的元素移除，最后再移除剩下的元素，只留下第一个元素。
首先说明一下，你第17行那个List的泛型没写全乎，前面有Integer,后面就没了，会报错的
其次是你32行的那个代码，是直到程序结束都不会被执行的代码，因为你的判断条件写的有问题呢，前面for循环已经说了i<list.size()了，在for循环里i就永远不会有等于list,size()的时候的，也就是说这条if语句肯定不会被执行的，没啥意义。我改了改代码试了一下，你看看这样符合你的需求不？
        public static void main(String[] args) {
                // 自定义数据类型
                // method1();
                // Integer数据类型
                // 创建有索引的集合，并添加元素
                List<Integer> list = new ArrayList<Integer>();
                list.add(11);
                list.add(22);
                list.add(33);
                list.add(44);
                list.add(55);
                list.add(66);

                // 遍历集合
                for (int i = 0; i < list.size(); i++) {
                        // 当数到第三个元素时，将其移除
                        if (i % 3 == 2) {
                                list.remove(i);
                                i--;
                        }
                }
                //当只剩下两个元素时移除第二个元素
                if (list.size()==2) {
                    list.remove(1);
                }
                System.out.println(list);
        }
}
输出结果就只剩下个[11]了，不过真心没看出来这么干有啥意义，可能是我没看懂前面那个约瑟夫圆环吧~
作者: 何堂红    时间: 2014-6-8 00:02
yogaa 发表于 2014-6-7 22:46
你写的那个约瑟夫环我是没太看懂，但是从你的需求来看，我是这样理解的，一步一步将集合中一直处于第三个的 ...

谢谢解答，楼主确实对约瑟夫环比较陌生，而我也没解释清楚，你可以百度一下，它解释的很详细。
另外，第17行的泛型不会报错，因为jdk1.7之后就可以省略了，它默认跟前面的一样的泛型。
32行那里，确实是执行不到，但问题不在这里，我修改后，一样没能得到正确的结果。
不过还是谢谢你的解答，你还是很细心的，以后肯定是个优秀的程序员！O(∩_∩)O嘿嘿~
作者: 何堂红    时间: 2014-6-8 00:04
Conning 发表于 2014-6-7 22:36
出圈数值输入3即可

感觉你这段代码跟我的相同点就是都是约瑟夫环的代码，不过方式完全不一样啊
作者: tc4892998    时间: 2014-6-8 10:59
留来吧!正好也是我的老师给我留的作业....分享一下吧.
附上我的代码  这个程序都是从第一个人开始数起的,,,不像楼主说的从第K个位置数M...

  

import java.util.ArrayList;
import java.util.Scanner;
/*
*         约瑟夫环
*/
public class YueSeFuHuan {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                System.out.println("输入一共有多少个囚犯");
                ArrayList<Integer> al = new ArrayList<>();
                int x = sc.nextInt();
                for (int i = 1; i <= x; i++) {
                        al.add(i);
                }
                //以count为计数器,开始遍历集合前先自加1,如果计数器为3的倍数,则将其对应的元素移除
                //如果遍历的脚标为最后一个脚标,则将脚标置为-1,因为for循环内还要执行自加运算
                //当集合的size为1是,break结束遍历,并且打印输出集合.
                int count = 0;
                System.out.println("囚犯的编号为:"+al);
                for (int j = 0; j < al.size(); j++) {
                        count++;
                        if (count % 3 == 0) {
                                al.remove(j--);
                        }
                        if (j == al.size()-1 ) {
                                j=-1;
                        }
                        if (al.size()==1) {
                                break;
                        }
                }
                System.out.println("最后的存活者为" + al);
                sc.close();
        }
}



作者: tc4892998    时间: 2014-6-8 11:00
不过如果要改成你所说的K开始,数M的话也不难,
可以将第二个for循环中的int j = 0改成inte j = k-1;
可以将count%3改成count%m
作者: yuZhe_toString    时间: 2014-6-8 15:56
自定义循环队列比用集合要方便些。



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