算法-约瑟夫环问题

约瑟夫环问题


10个人围成一个圆圈,编号为1~10,从第一号开始报数,报到3的倍数的人离开,* 一直数下去,直到最后只有一个人,* 求此人编号

解题代码


package com.che.carcheck.rxjava;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 约瑟夫问题
 * <p>
 * 10个人围成一个圆圈,编号为1~10(令N=10),
 * 从第一号开始报数,报到3(令M=3)的倍数的人离开,
 * 一直数下去,直到最后只有一个人,
 * 求此人编号
 */
public class Question1 {

    @Test
    public void test() {
        int N = 10, M = 3;
        System.out.println("模拟法:最后的人=" + mock(N, M));
        System.out.println("递归法:最后的人=" + recursion(N, M));
    }

    /**
     * 约瑟夫问题的模拟法
     *
     * @param N 人数
     * @param M 离开的报数
     * @return 最后的人
     */
    private int mock(int N, int M) {
        List<Integer> list = new ArrayList<>();
        //初始化数组,代表所有人
        for (int i = 1; i <= N; i++) {
            list.add(i);
        }
        // 每次计数开始的索引
        int startIndex = 0;
        // 删除的位置
        int removeIndex;
        //循环删除
        while (true) {
            // 【起始位置】+【报号数】-1 =【len】
            int len = startIndex + M - 1;
            // 如果 len > list.size(),相当于转了一圈,又重新开始;
            if (len > list.size() - 1) {
                removeIndex = len % list.size();
            } else {
                removeIndex = len;
            }
            list.remove(removeIndex);
            startIndex = removeIndex;
            //只有最后一位时,返回
            if (list.size() == 1) {
                return list.get(0);
            }
        }

    }

    /**
     * 约瑟夫问题的递归法
     * <p>
     * 递推公式:
     * (1)、f[1]=0;
     * (2)、f[i]=(f[i-1]+m)%i; (i>1)
     * <p>
     * 参考:http://www.acmerblog.com/joseph-problem-3394.html
     */
    public int recursion(int N, int M) {
        int s = 0;
        for (int i = 2; i <= N; i++) {
            s = (s + M) % i;
        }
        return s + 1;
    }

}

2016-10-29 13:3812
  • Aly Chiman2018-12-01 10:42

    Hello there,

    My name is Aly and I would like to know if you would have any interest to have your website here at farbox.com promoted as a resource on our blog alychidesign.com ?

    We are in the midst of updating our broken link resources to include current and up to date resources for our readers. Our resource links are manually approved allowing us to mark a link as a do-follow link as well
    .
    If you may be interested please in being included as a resource on our blog, please let me know.

    Thanks,
    Aly