约瑟夫问题I

[编程题]约瑟夫问题I

热度指数：10896 时间限制：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)

Python

ONE201801221014334

# -*- coding:utf-8 -*-
class Joseph:
    def getResult(self, n, m):
        s = 0
        for i in range(1, n+1):
            s = (s + m)% i
        return s+1

根据约瑟夫问题递归推导得：

f[n] = (f[n - 1] + K) mod n

上述公式可以用数据归纳法简单证明其正确性：

f[1] = 0
当只有一个***的时候，显然结果应该是0

f[n] = (f[n - 1] + K) mod n
f[n - 1]为第n - 1次数到的id序列，则第n次就是再往下数k个，最后进行取模运算即可得到结果序列

这种算法的时间复杂度为O(N)，空间复杂度为O(1)

编辑于 2018-03-22 11:16:50 回复(0)

Python

张淮

# -*- coding:utf-8 -*-
class Joseph:
    def getResult(self, n, m):
        # write code here
        if n==1:
            return 1
        x=self.getResult(n-1,m)
        return (x+m-1)%n+1

发表于 2017-07-14 19:55:25 回复(0)

Python

啥也没有

# -*- coding:utf-8 -*-
class node:
    def __init__(self,x):
        self.val = x
        self.next = None
class Joseph:
    def getResult(self,n, m):
            head = node(1)
            phead = head
            cishu = n-1
            n -= 1
            while n!= 0:
                head.next = node(head.val+1)
                head = head.next
                n -= 1
            head.next = phead
            shanchu = 0
            while cishu != shanchu:
                count = 1
                while count != m:
                    phead = phead.next
                    count += 1
                phead.val = phead.next.val
                phead.next = phead.next.next
                shanchu += 1
            return phead.val   
循环链表，不过感觉比较麻烦，不过好理解点

编辑于 2017-05-16 10:46:50 回复(0)