约瑟夫环的java实现

 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

 

以下是java的实现方式（基于LinkedList实现）：

 

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * 约瑟夫环的实现
 * 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
 * 从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；
 * 依此规律重复下去，直到圆桌周围的人全部出列。
 */

/**
 *
 */
public class SonotaTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        printArray(getTheNumbers(31, 9, 5));
    }

    /**
     * 约瑟夫环的实现
     * @param personNo 总人数
     * @param num 出列的数字
     * @param startNo 开始号
     * @return 出列号码的出列顺序
     */
    public static String[] getTheNumbers(int personNo, int num, int startNo) {

        ArrayList<String> returnList = new ArrayList<String>(personNo);
        LinkedList<String> personsList = new LinkedList<String>();
        for (int i = 1; i <= personNo; i++) {
            personsList.add(String.valueOf(i));
        }

        Iterator<String> it = personsList.iterator();
        for (int i = 1; i < startNo; i++) {
            it.next();
        }

        int tmpNum = 1;
        while(personsList.size() != 1) {

            if (!it.hasNext()) {
                it = personsList.listIterator();
            }

            String tmpNo = it.next();

            if (tmpNum == num) {
                returnList.add(tmpNo);
                it.remove();
                tmpNum = 1;
                continue;
            }

            tmpNum++;
        }
        returnList.add(personsList.get(0));

        return returnList.toArray(new String[0]);
    }

    public static void printArray(String[] array) {
        for (String ss : array) {
            System.out.print(ss.concat(","));
        }
    }
}

 

 输出结果：

      13,22,31,9,19,29,8,20,1,12,25,6,21,4,18,5,24,11,30,23,15,10,7,14,17,28,26,27,16,2,3