约瑟夫问题I

[编程题]约瑟夫问题I

热度指数：10900 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知n个人坐成一圈，按顺时针由1开始给大家编号。然后由第一个人开始顺时针循环报数，数到m的人出局，循环此过程直到最后只剩一个人。给定两个int n和m，要求编写函数返回最后一个人的编号。保证n和m小于等于1000。

示例1

输入

5,3

输出

算法知识视频讲解

推荐

orgcheng

把n个人的编号改为0~n-1，然后对删除的过程进行分析。
第一个删除的数字是(m-1)%n，几位k，则剩余的编号为(0,1,...,k-1,k+1,...,n-1)，下次开始删除时，顺序为(k+1,...,n-1,0,1,...k-1)。
用f(n,m)表示从(0~n-1)开始删除后的最终结果。
用q(n-1,m)表示从(k+1,...,n-1,0,1,...k-1)开始删除后的最终结果。
则f(n,m)=q(n-1,m)。

下面把(k+1,...,n-1,0,1,...k-1)转换为(0~n-2)的形式，即
k+1对应0
k+2对于1
...
k-1对应n-2
转化函数设为p(x)=(x-k-1)%n, p(x)的你函数为p^(x)=(x+k+1)%n。
则f(n,m)=q(n-1,m)=p^(f(n-1,m))=(f(n-1,m)+k+1)%n，又因为k=(m-1)%n。
f(n,m)=(f(n-1,m)+m)%n;

最终的递推关系式为
f(1,m) = 0; (n=1)
f(n,m)=(f(n-1,m)+m)%n; （n>1）

代码如下

import java.util.*;

public class Joseph {
    /*
	 * 编号为(0~n-1)
	 */
    public int getResult(int n, int m) {
        if (n < 0 || m < 0) {
			return -1;
		}
		int last = 0;
		for(int i=2;i<=n;++i){
			last = (last+m)%i;
		}
		// 因为实际编号为(1~n)
		return (last+1);
    }
}

编辑于 2015-08-18 19:21:29 回复(11)