算法（1）-约瑟夫-白红宇

算法（1）-约瑟夫

阅读量：6229 次

发布时间：2019-06-21

本文共 3137 字，大约阅读时间需要 10 分钟。

1、算法介绍

约瑟夫算法的介绍：

约瑟夫环：已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，

数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，

直到圆桌周围的人全部出列

2、算法的思路

以下为log信息，帮助理解实现思路

所有的数据为：   1   2   3   4   5   6   7   8   9   10第1次循环，数据为：   1   2   3   4   5   6   7   8   9   10 -----------被删除的数据为：6第2次循环，数据为：   7   8   9   10   1   2   3   4   5 -----------被删除的数据为：2第3次循环，数据为：   3   4   5   7   8   9   10   1 -----------被删除的数据为：9第4次循环，数据为：   10   1   3   4   5   7   8 -----------被删除的数据为：7第5次循环，数据为：   8   10   1   3   4   5 -----------被删除的数据为：5第6次循环，数据为：   8   10   1   3   4 -----------被删除的数据为：8第7次循环，数据为：   10   1   3   4 -----------被删除的数据为：1第8次循环，数据为：   3   4   10 -----------被删除的数据为：10第9次循环，数据为：   3   4 -----------被删除的数据为：4总数：[10]  需要删除掉的数据的位置：[6]  最后一个被删除掉的数据[3]

主要的实现思想：

2.1、两个list：一个装之前已经读过的数据，一个装还没有读过的数据

2.2、从没有读过的数据里面删除应该删除的数据。

每次到应该删除的数据以后，将已经读过的数据放到没有读过的后面，之后再将已经读过的数据清空掉

如果没有读过的数据，已经为空了，那么则需要将已经读过的数据再加进去，并将已经读过的数据清空

2.3、判断，如果已经读过的数据list长度为1，未读数据为空，则结束循环

3、具体的代码实现

/** * 约瑟夫算法的实现 * 约瑟夫算法的介绍： * 约瑟夫环：已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数， * 数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去， * 直到圆桌周围的人全部出列 */public class YuesefuTest {    public static void main(String[] args) {        int total = 5;        int removeAt = 3;//        patternTwo(total, removeAt);//        patternTwo(10, removeAt);        patternTwo(10, 6);//        testOne();    }    private static void testOne(){        ArrayList
    
      unReadList = new ArrayList
     
      ();//没有读过的list        ArrayList
      
        readedList = new ArrayList
       
        ();//已经读过的list        for(int i = 0;i< 5;i++){            unReadList.add(i);        }        for(int i = 5;i<10;i++){            readedList.add(i);        }        readedList.addAll(readedList.size(),unReadList);        unReadList.clear();        System.out.println("所有的数据：");        for(int i = 0;i
        
          unReadList = new ArrayList
         
          ();//没有读过的list ArrayList
          
            readedList = new ArrayList
           
            ();//已经读过的list for(int i = 1;i<=total;i++){ unReadList.add(i); } System.out.println("所有的数据为："); printAllNum(unReadList); int loopCount = 1; while(true){ System.out.println("第"+loopCount+"次循环，数据为："); printAllNum(unReadList); for(int i = 1;i< removeAt;i++){ if(unReadList.size() == 0){//如果没有读过的数据，已经为空了，那么则需要将已经读过的数据再加进去，并将已经读过的数据清空 unReadList.addAll(unReadList.size(),readedList); readedList.clear(); } int value = unReadList.remove(0); readedList.add(value); } if(unReadList.size() == 0){ unReadList.addAll(unReadList.size(),readedList); readedList.clear(); } int i = unReadList.remove(0);//从没有读过的数据里面删除应该删除的数据。 System.out.print(" -----------被删除的数据为："+i+"\n"); //每次到应该删除的数据以后，将已经读过的数据放到没有读过的后面，之后再将已经读过的数据清空掉 unReadList.addAll(unReadList.size(),readedList); readedList.clear(); loopCount++; if(unReadList.size() == 1 && readedList.size() == 0){//判断，如果已经读过的数据list长度为1，未读数据为空，则结束循环 break; } } System.out.println("总数：["+total+"] 需要删除掉的数据的位置：["+removeAt+"] 最后一个被删除掉的数据["+unReadList.get(0)+"]"); } private static void printAllNum(ArrayList
            
              allNum){ if(null != allNum && allNum.size() > 0) { System.out.println(); for (int i =0;i