黑马程序员技术交流社区

标题: 经典数据结构问题之约瑟夫环 [打印本页]
作者: sin    时间: 2014-12-5 17:07
标题: 经典数据结构问题之约瑟夫环
前两天做的一道考试题，是一道挺经典的算法题
  1. package com.itheima;
  2. /**
  3. * 10、 有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，
  4. * 从1报数，到14退出。问：最后剩下的是100人中的第几个人？
  5. *
  6. * @author Administrator
  7. * */
  8. public class Test10 {

  10.         public static void main(String[] args) {

  12.                 // 定义总数
  13.                 int total = 100;
  14.                 // 报到即被退出的数字
  15.                 int div = 14;
  16.                 // 最后能被留下的人数
  17.                 int left = 1;

  19.                 // 定义一个数组，长度即总人数
  20.                 int[] it = new int[total];
  21.                 // 遍历数组并为其每一个元素赋值1
  22.                 for (int i = 0; i < total; i++) {
  23.                         it[i] = 1;
  24.                 }

  26.                 // 定义一个计数器
  27.                 int count = total;
  28.                 // 定义一个指针，代表当前被报到的数字
  29.                 int pointer = 0;

  31.                 // 循环直到数组中留下left个元素
  32.                 while (count > left) {

  34.                         // 在数组中的每一轮循环
  35.                         for (int j = 0; j < it.length; j++) {

  37.                                 // 如果数组的值为0，代表其为退出，不为零则指针加一
  38.                                 if (it[j] != 0) {
  39.                                         it[j] = ++pointer;
  40.                                 } else {
  41.                                         continue;
  42.                                 }

  44.                                 // 如果其能被div整除，代表退出
  45.                                 if (pointer % div == 0) {
  46.                                         it[j] = 0;

  48.                                         pointer = 0;
  49.                                         count--;
  50.                                         if (count == left) {
  51.                                                 break;
  52.                                         }
  53.                                 }
  54.                         }
  55.                 }
  56.                 // 判断数组中不为零的元素的位置
  57.                 for (int i = 0; i < total; i++) {
  58.                         if (it[i] != 0) {
  59.                                 System.out.println("最后剩下的是其中的第" + (i + 1) + "个人");
  60.                         }
  61.                 }
  62.         }
  63. }
复制代码


作者: cczheng    时间: 2014-12-6 08:12
确实很经典，我也做到了，开始也没想出来
作者: 聪明叉    时间: 2014-12-6 08:27
本帖最后由 聪明叉 于 2014-12-6 08:34 编辑

我觉得用List集合来做更简单，把1~100封装成Integer对象，放进集合
在ListIterator中设置计数器，用remove方法移除第14个数
。。。。不对，我这样会剩13个，我再想想
作者: 聪明叉    时间: 2014-12-6 09:31
第一次报到14的人退出了，重新开始是指从第15个人继续报数吗
作者: as604049322    时间: 2014-12-6 10:50
我发现我是脑残~
作者: Rain2692    时间: 2014-12-6 17:37
你觉得你的代码高效并且简单 吗？时间复杂度O(n2),猴子选大王的问题做过没，这个题目，用C语言就可以直接秒过！！
作者: sin    时间: 2014-12-6 21:00
聪明叉 发表于 2014-12-6 09:31
第一次报到14的人退出了，重新开始是指从第15个人继续报数吗

对从一开始报，不过接着报也没问题，只要是14的倍数就行
作者: Rain2692    时间: 2014-12-6 21:02
sin 发表于 2014-12-6 21:00
对从一开始报，不过接着报也没问题，只要是14的倍数就行

come on!!baby
作者: sin    时间: 2014-12-6 21:02
Rain2692 发表于 2014-12-6 17:37
你觉得你的代码高效并且简单 吗？时间复杂度O(n2),猴子选大王的问题做过没，这个题目，用C语言就可以直接秒 ...

看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论
作者: Rain2692    时间: 2014-12-6 21:13
sin 发表于 2014-12-6 21:02
看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论 ...

加我好友，我就给你！！
作者: 聪明叉    时间: 2014-12-7 09:07
sin 发表于 2014-12-6 21:02
看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论 ...
  1. import java.util.ArrayList;  
  2. import java.util.List;  
  3. import java.util.Scanner;  
  4.   
  5. class Count {  
  6.     public static void main(String[] args) {  
  7.         Scanner scanner = new Scanner(System.in);  
  8.         System.out.print("请输入总人数：");  
  9.         int totalNum = scanner.nextInt();  
  10.         System.out.print("请输入报数的大小：");  
  11.         int cycleNum = scanner.nextInt();  
  12.         yuesefu(totalNum, cycleNum);  
  13.     }  
  14.   
  15.    public static void yuesefu(int totalNum, int countNum) {  
  16.         // 初始化人数  
  17.         List<Integer> start = new ArrayList<Integer>();  
  18.         for (int i = 1; i <= totalNum; i++) {  
  19.             start.add(i);  
  20.         }  
  21.         //从第K个开始计数  
  22.         int k = 0;  
  23.         while (start.size() >0) {  
  24.             k = k + countNum;  
  25.             //第m人的索引位置  
  26.             k = k % (start.size()) - 1;  
  27.            // 判断是否到队尾  
  28.             if (k < 0) {  
  29.                 System.out.println(start.get(start.size()-1));  
  30.                 start.remove(start.size() - 1);  
  31.                 k = 0;  
  32.             } else {  
  33.                 System.out.println(start.get(k));  
  34.                 start.remove(k);  
  35.             }  
  36.         }  
  37.     }  
  38. }
复制代码




这个解法很经典
作者: lishuliang28    时间: 2014-12-7 21:34
还有更简单的！！



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