约瑟夫问题

问题来历:

      1: 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
     :2: 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。
 
---------------------我是分割线---------------------
 哈哈!简单分析一下上边两个问题来历:
来历1:细思极恐啊!约瑟夫是著名犹太历史学家,那就是说约瑟夫和他朋友应该都是犹太人,那么问题来了,大家都是犹太人,万一约瑟夫他朋友被一帮“爱国人士”感染了也想殉国,那么约瑟夫就危险了,然而约瑟夫是一个心机boy!!!他给朋友的位置是16,而他自己的是31,细心的朋友会发现,假如按规则只能活一个人,这个人必然是约瑟夫!
来历2:这个问题就有点奇葩了,问题目的很好,锻炼大家思维,但题目就有点“手撕鬼子”的感觉了,非教徒不是教徒,但不是傻子,死一个不明白,难道死五六个还不明白吗?除非这个教徒是不为人知的,地下工作者,身份隐藏的!哈哈!
 
好了,闲话不说了,直接上代码!
package com.sinolife.mtrs.apply.controller;

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

import org.junit.Test;

/** 
 * @author  delin Li 
 * @version createTime:2017-12-29下午09:10:37 
 * @Description  
 */
public class TestSort {
    @Test
    public void Test(){
        int n = 41;//总人数
        int num = 3;//指定第几个人
        int start = 1;//第几个人开始
        int stayNum = 2;//指定第留几个人
        List<Integer> list = YueSeFu(n,num,start,stayNum);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));//打印留下几个人的位置
        }
    }
    
    /**
     * 
     * @param n 总人数
     * @param num 指定第几个人
     * @param start 第几个人开始
     * @param stayNum 指定第留几个人
     * @return List<Integer>
     */
    public static List<Integer>  YueSeFu(int n,int num,int start,int stayNum){
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {//将所有人按顺序装进list
            list.add(i);
        }
        int m = start-1;//从list的第m个开始数
        while(list.size()>0){
             m = m+num;
             m = m%list.size()-1;
            if(m<0){
                list.remove(list.size()-1);
                m=0;
                if(list.size()==stayNum){//list元素等于指定第留几个人时返回
                    return list;
                }
            }else{
                list.remove(m);
                if(list.size()==stayNum){//list元素等于指定第留几个人时返回
                    return list;
                }
            }
        }
        return list;
    }  
}

运行结果:

上述如有问题请指出来,大家可以讨论讨论,毕竟学海无涯有一个或多个同行人感觉会好些,不是吗?

原文地址:https://www.cnblogs.com/lidelin/p/8144850.html