约瑟夫问题(猴子选大王)(java实现)

题目描述: 
n个数,编号为 0 , 1, ……, n-1 排成一个圆圈,从数字 0 开始,每次从这个圆圈中删除第 m 个数,请问最后一个剩下的数是多少?

公式: f(1) = 0; f(i) = (f(i-1)+m)%i

推导过程 
定义一个函数 f(n, m) 为 n 个数中取 m 最后剩下的编号。 
第一个被删除的数是 (m-1)%n, 记为 k 。此时因为序列已经不连续,函数可以定义为 f’ ( n-1, m) 。 
明显,最后剩下的编号相等,于是: f(n,m) = f’(n-1, m)

然后我们对剩下的数做一个简单的映射:

k+1 –> 0 
k+2 –> 1 


n-1 –> n-k-2 
0 –> n-k-1 
1 –> n-k 


k-1 –> n-2

这个映射可以记为 
p(x) = (x-k-1)%n 
其中 x 为映射前的数 (可以自己推导一下)

那么逆映射就是: 
p-1(x) = (x + k + 1 ) %n 
(还是建议自己推导一下)

那么,对于上面的函数 f’(n-1, m),就有 
f’(n-1, m) = p-1[f(n-1, m)] = [f(n-1, m) + k +1]%n = f(n, m)

将 k= (m-1)%n 代入: 
f(n, m) = [f(n-1, m) + m]%n

这就是我们要的通项公式。 
很明显,当 n = 1 时,f = 0; 
于是:

f(n, m) = 0, n = 1 
f(n, m) = [f(n-1, m) + m]%n, n>1

应用:猴子选大王问题:

有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:

0 0

输出对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号
样例输入

6 2
12 4
8 3
0 0

样例输出

5
1
7
import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
     Scanner cin = new Scanner(System.in);
     while(true)
     {
         int n=0,m=0;
         int i,k = 0;
         n=cin.nextInt();
         m=cin.nextInt();
         if(n==0&&m==0) System.exit(0);
         for(i = 2;i<=n;i++)
         {
              k =(k + m) % i;
         }
          System.out.printf("%d\n",++k);
     }

   }
}

不推荐:模拟暴力做法 (代码引用自这里

import java.util.Scanner;
public class Monkey {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    //定义猴子总数,和被踢出猴子是第几个
    int n;
    int number;
    
    //输入猴子数量
    Scanner cc = new Scanner(System.in);
    System.out.println("请输入一共多少个猴子");
    n = cc.nextInt();
    System.out.println("请输入数到第几个猴子开始退出");
    number = cc.nextInt();
    
    //初始化,把所有的猴子先标记为1
    int[] a = new int[n];
    for(int i = 0; i < a.length; i++)
    {
      a[i] = 1;
    }		
    int leftCount = n;		//剩余猴子的数量
    int countNum = 0; 		//目前数到了第几个
    int index = 0;    		//定义当前的位置从0开始。
    
    //如果当前点的左边数量不为1的话
    //把踢出的猴子标记改为0,未被踢出的不变,依然万为1
    while(leftCount != 1){	
      if(a[index] == 1)
      {
        //如果当前剩余猴子的数量大于1,然后标记还为1,那么就在计数器中加1
        countNum++;
        
        //计数器的数和设定被踢出的猴子的数目相同的时候,踢出猴子,把标记改为0
        if(countNum == number){
          countNum = 0;           //刷新计数器,初始化为0
          a[index] = 0;           //改变当前的标记为0
          leftCount--; 			//在剩余的猴子里面减一
        }
      }
      index ++;       //改变当前的位置
      //改变现有猴子的长度
      //当走到了末尾,转到第一个位置
      if(index == a.length){
        index = 0;
      }
    }
    //从第一个到最后一个查找哪个的标记是0,如果是0的话说明被踢出,如果是1的话,则为剩余的猴王
    for(int i = 0; i < a.length; i++){
      if(a[i] == 1){
        System.out.println("第" + (i+1)+ "只猴子被选为大王!");
      }
    }
  }
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

18 + 6 =