杰哥私房题──约瑟夫问题

问题描述
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号
开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，
直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编
号。
输入数据
每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m, n < 300)。最后一行
是：
0 0
输出要求
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
输入样例：
6 2
12 4
8 3
0 0
输出样例：
5
1
7

#include <stdio.h>
void initialize(char* arg, int n){
	int i;
	for(i = 0; i < n; i ++){
		arg[i] = i + 1;
	}
}
int finalMonkey(char* arg, int n){
	int i;
	for(i = 0; i < n; i++){
		if(arg[i])
			return arg[i];
	}
}

int main(){
	int n, m;
	while(scanf("%d %d", &n, &m) && n != 0 && m != 0){
		char monkeyLoop[300] = {0};
		initialize(monkeyLoop, n);
		int i,j = 0, k = 0, ptr = 0;
		while(1){
			while(j < n){
				if(monkeyLoop[j])
					ptr ++;
				if(ptr == m){
					monkeyLoop[j] = 0;
					ptr = 0;
					k ++;
				}
				j++;
			}
			if (k == n -1){
				break;
			}
			j %= n;
		}
		int result = finalMonkey(monkeyLoop, n);
		printf("%d\n", result);
	}

	return 0;
}

 

评论

14 楼 soft901 2009-08-15  

用递归写了个

	private void josephus(int n, int m) {
		List list = new ArrayList();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
		f(m, m - 1, list);
	}
	
	private void f(int m, int increase, List list) {
		
		if (list == null || list.size() == 0) return;
		if (list.size() == 1) {
			System.out.println(list.get(0));
			return;
		}
		
		m = checkSize(m, list.size());
		
		list.remove(m - 1);
		
		m = m + increase;
		f(m, increase, list);
	}
	
	private int checkSize(int m, int size) {
		if (m > size) {
			m = m - size;
		}
		
		if (m > size) {
			return checkSize(m, size);
		} 
		return m;
	}

13 楼 zhang_jie439 2009-08-14  

学学小学奥数，有这个题。

12 楼 苏东坡放牛 2009-08-14  

哈哈，这个算法我研究过，很多人讨论过这个无比经典的算法，真的是纯数学的脑子才想的出来的……
这里不知允不允许贴链接：
http://topic.csdn.net/u/20070916/15/11a62d59-3d7a-4aa6-81be-b1bef25ac404.html
这里提供了两种数学思路，第一种太复杂了，实在是不敢看下去…………
第二种我的理解是这样的，基于这个链接里的说法，不过这个说法我也看得一知半解……
f(i)表示从i个猴子中数到第m个退出的最后剩下的猴子编号，于是本问题要求的也就是f(n)。如果可以的话我们可以画一个n个猴子围成圈的图，方便理解。
于是：
假设从某个位置开始，我们标注1，然后不停的找，找到第一个m的位置，然后将它踢出去，从第m+1个位置接着找。一直到最后找到了f(n)，也就是问题的解。
注意了！这个意思也就是说，我们从n个猴子中从第1个开始找起和n-1个猴子中从第m+1个（相对于n个猴子中的m）找起的结果是一样的！这样我们就有了一个递归的思路……
那么这个问题现在我们这样思考，从n-1个猴子中从第m+1找起和第1个位置（上面定义的那个第1个位置）找起有什么关系呢？
我们不妨将m+1先简单想成2，n-1个猴子，从第1个位置找起和从第二个位置找起结果f(n-1)有什么不同？？？
一定是相差1！没有证明，但是想想那-1个猴子围成的圈就好像一个齿轮一样，它的找法都是一样的，所以就是一个错一个嘛，从第1个位置找起是f(n-1)，从第2个位置找起结果一定是f(n-1)+1嘛！！为了确保正确，应该是（f(n-1)+1)%n，也就是加个取模操作，注意此时长度是n-1,所以取模用n……
所以从第m+1个位置找起，一定就是（f(n-1)+m）%n嘛！
也就是说，n-1个猴子，从第m+1个找起的结果是（f(n-1)+m）%n。而上面说了，它又是和从n个猴子中从第1个找起是等价的，也就是f(n).
于是这个结论就出来了：f(n)=（f(n-1)+m）%n
同时初始条件f(1)=1.这样就可以用递归很简洁的写出来了………………

哎呀呀，用文字写确实麻烦多了，可是我觉得思路很明白，那些数学公式看着太头疼了，我觉得这样写出来反而明白。
看公式看不懂的不妨看看我的啊……哈哈，欢迎指教

11 楼 rappizit 2009-03-21  

netalpha 写道

jiyanliang 写道

pe1011 写道

来个牛点的：
int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

我关心的这个到底是啥子算法

我也很关心 应该是某个大牛想出来的 某个经典算法。

http://hi.baidu.com/wuxyy/blog/item/464471f03802fcafa40f523c.html
这里有解答

10 楼 netalpha 2009-03-17  

liyingeye 写道

写了个JS的版本，随便看看
function findMonkeyKing(n,m)
{
  var a = new Array();
  for(i=0;i<n;i++)
  a.push(i+1);
  while(a.length>1)
  {
    for(i=1;i<m;i++)
      a.push(a.shift());
    a.shift();
  }
  return a.shift();
}
alert(findMonkeyKing(6,2)+"\n"+findMonkeyKing(12,4)+"\n"+findMonkeyKing(8,3));

大侠果然牛，偶最近也在学习js和php

9 楼 liyingeye 2009-03-17  

写了个JS的版本，随便看看
function findMonkeyKing(n,m)
{
  var a = new Array();
  for(i=0;i<n;i++)
  a.push(i+1);
  while(a.length>1)
  {
    for(i=1;i<m;i++)
      a.push(a.shift());
    a.shift();
  }
  return a.shift();
}
alert(findMonkeyKing(6,2)+"\n"+findMonkeyKing(12,4)+"\n"+findMonkeyKing(8,3));

8 楼 netalpha 2009-03-06  

jiyanliang 写道

pe1011 写道

来个牛点的：
int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

我关心的这个到底是啥子算法

我也很关心 应该是某个大牛想出来的 某个经典算法。

7 楼 jiyanliang 2009-03-06  

pe1011 写道

来个牛点的：
int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

我关心的这个到底是啥子算法

6 楼 netalpha 2009-03-06  

leeldy 写道

做算法题目不要被java的强大功能限制住了。。。

这句话深得我心，我就是因为这个才不用java写算法题，而选择了c，其实我最拿手的也是java，最近试着用C写程序，深深的感觉到了这一点。

5 楼 leeldy 2009-03-06  

做算法题目不要被java的强大功能限制住了。。。

4 楼 netalpha 2009-03-06  

pe1011 写道

来个牛点的：
int findMonkey(int n, int m)
{
&nbsp;&nbsp;&nbsp; int r = 0;
&nbsp;&nbsp;&nbsp; for (int i = 2; i &lt;= n; i++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; r = (r + m) % i;
&nbsp;&nbsp;&nbsp; return r+1;
}

望ls解答这个是个什么金典算法嘛？确实是对的，受教了。

3 楼 pe1011 2009-03-05  

来个牛点的：
int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

2 楼 netalpha 2009-03-05  

ilovemmmm 写道

我写了个java代码

import java.util.*;

public class Haha {
	public static void main(String[] args) {
		final int N = 10;
		final int M = 5;
		List<Integer> num = new ArrayList<Integer>();
//		List<Integer> num2 = new ArrayList<Integer>();
		for (int i = 1; i <= N; i++) {
			num.add(i);
		}
		Iterator<Integer> it = num.iterator();
		int ii = 0;
		for (int n = 1;; n++) {
			if (num.size() == 1) {
				System.out.println(num.get(0));
//				num2.add(num.get(0));
				break;
			}
			for (int i = 1; i <= M; i++) {
				if (it.hasNext()) {
					ii = it.next();
				}
				else {
					it = num.iterator();
					ii = it.next();
				}
			}
			System.out.print(ii + "\t");
//			num2.add(ii);
			it.remove();
		}
//		System.out.println(num2);
	}
}

恩 你这个是用list来写的，以后我也会推出一系列关于链表等的处理程序，希望大家关注

1 楼 ilovemmmm 2009-03-05  

我写了个java代码

import java.util.*;

public class Haha {
	public static void main(String[] args) {
		final int N = 10;
		final int M = 5;
		List<Integer> num = new ArrayList<Integer>();
//		List<Integer> num2 = new ArrayList<Integer>();
		for (int i = 1; i <= N; i++) {
			num.add(i);
		}
		Iterator<Integer> it = num.iterator();
		int ii = 0;
		for (int n = 1;; n++) {
			if (num.size() == 1) {
				System.out.println(num.get(0));
//				num2.add(num.get(0));
				break;
			}
			for (int i = 1; i <= M; i++) {
				if (it.hasNext()) {
					ii = it.next();
				}
				else {
					it = num.iterator();
					ii = it.next();
				}
			}
			System.out.print(ii + "\t");
//			num2.add(ii);
			it.remove();
		}
//		System.out.println(num2);
	}
}