约瑟夫环公式的问题

Question

f(N,M)=(f(N−1,M)+M)%N

已知公式如上，如果n=41, m=3，最后的结果是多少？

高中数学都忘完了，只知道这个好像是个函数。不知道怎么计算。

 

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

 

最后的结果应该是31。

 

Answer 1

最初41人，编号设置从0开始：0，1，2，3，4, …., 40.

解释 f(N,M)=(f(N−1,M)+M)%N：

1. f(N,M) 表示，N个人报数，每报到M时杀掉那个人，最终生还者的编号
2. f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终生还者的编号

按公式列表计算如下。审查此表得知:

1. 当N等于 1 是，能直接得解：这个编号为 0 的人就是幸存者。
2. 当 N 等于 2，3，4，即 有2，3，4 个人的情况，分别 通过 实际模拟 和 
3. 用公式 f(N,M)=(f(N−1,M)+M)%N 计算的结果一致。
4. 说明 可以用 递归法 recurion解决此问题：
   

   N	f(N,M)
   1	0
   2	(0+3)%2 =1
   3	(1+3)%3 =1
   4	(1+3)%4 =0
   ...	...
   N	f(N,M)=(f(N−1,M)+M)%N

   于是列出方法如下：

   int joseph(int n, int m){
    	if (n==1) return 0;
    	else
    	return (joseph(n-1,m)+m)%n;	
    }

   最后指出，如果标号系统不是从0而是从 1开始，那每个人的编号都要自增 1。 就是说，原先的0号，改为1号，原先的1号，改为2号，…..。因此，要将调用上述方法得出的结果加 1， 才是从 1 起始的标号系统。

    // f(N,M)=(f(N?1,M)+M)%N 
   public class Joseph{
    
    static int joseph(int n, int m){
    	if (n==1) return 0;
    	else
    	return (joseph(n-1,m)+m)%n;	
    }
   public static void main(String args[]) {
   	System.out.println(joseph(41,3)+1);
   	}
   }

   输出：31

复习:     

递归方法可以用以下两个特点来定义：

1. 一个简单的基本案例，即一个不必再用递归来产生答案的终结场景。
2. 一套朝着上述基本案例 简化/缩小场景的规则

递归函数(Recursive Function)即自调用函数，即在函数体内有直接或间接地自己调用自己的语句。 例如： 求n的阶乘

             n! = n(n-1)!               (当n>1时)

             n! = 1                         (当n=0，1时)

于是可以写出：

int factorial(int  n){
        if (n ==1)
            return  1;
        else  
            return  (n*factorial(n-1));
       } 

 

Answer 2

我就是因为那个公式看不懂才来问的。

Answer 3

如果是一个普通人，想要快速知道答案， 请翻阅 约瑟夫环——公式法（递推公式）。那里详细讲述如何用命题给出的公式求解。

public class Joseph{	
static int cir(int n,int m) {
    int p=0;
    for(int i=2;i<=n;i++){
        p=(p+m)%i;
    }
    return p+1;
}
public static void main(String args[]){
System.out.println(cir(41,3)); 
	}
}

输出: 31

Answer 4

嗯，这个倒是没有听说过，如果是一个普通人，想要快速知道答案，用公式如何求解呢？这个数学公式有些不太懂，谢谢解答

Answer 5

不同的故事说法。这里是 猴子选大王。任务：一堆猴子都有编号，编号是1，2，3 ...m , 这群猴子（m个）按照1 至 m的顺序围坐一圈， 从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。亦参考：JAVA求解。

/* 任务：一堆猴子都有编号，编号是1，2，3 ...m ,
这群猴子（m个）按照1-m的顺序围坐一圈，
从第1开始数，每数到第N个，该猴子就要离开此圈，
这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，
输出为大王的猴子是几号 ，建立一个函数来实现此功能
*/

import javax.swing.JOptionPane;
public class monkey {
static int workarr[] = new int[1000];
static int Work(int m, int n) {
int i, j, k = 0;
 for (i=0; i<m; i++)
         workarr[i] = i+1;
    for (i=m; i>1; i--)
    {
        k = (k+n-1)%i;
        for (j=k+1; j<i; j++)
            workarr[j-1] = workarr[j];
     }
     return workarr[0];
}

public static void main(String args[]) {
String sm = JOptionPane.showInputDialog( "键入猴子数目 m." );
int m = Integer.parseInt( sm );
String sn = JOptionPane.showInputDialog( "键入数到几？ n  (n<m)." );
int n = Integer.parseInt( sn );

String s = "There are " + m + " monkeys.n";
s += "They are numbering up to " + n + "n";
s += "The " + Work(m, n) + " monkey will be the King.";
JOptionPane.showMessageDialog( null, s, "Wellcome to JAVAJIA !",
JOptionPane.INFORMATION_MESSAGE);
System.exit(0);
}
}