ジョセフリングの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