约瑟夫问题I_

推荐

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)

念润

思路

建立一个有n个元素的链表，然后从链表头开始遍历并记数，数到第m个踢出，在遍历过程中要判断当前元素是否到达链表末尾，如果到达末尾，把迭代器移到链表的头部。在删除第m个时记得要记录下一个元素的地址，以便删除之后重新从1开始报数。

代码

class Joseph {
public:
    int getResult(int n, int m) {
        list<int> circle;
        // 初始状况
        for(int i = 1;i <= n;++i){
            circle.push_back(i);
        }//for
        list<int>::iterator cur = circle.begin();
        while(circle.size() > 1){
            // 数到m的人出局
            for(int i = 0;i < m - 1;++i){
                ++cur;
                if(cur == circle.end()){
                    cur = circle.begin();
                }//if
            }// for
            // 因为删除数到m的人要记录下一个人的地址
            list<int>::iterator next = ++cur;
            if(next == circle.end()){
                next = circle.begin();
            }//if
            --cur;
            // 删除数到m的人
            circle.erase(cur);
            // 从下一个人继续开始
            cur = next;
        }//while
        return circle.front();
    }
};

发表于 2015-08-18 19:56:44 回复(2)

Aurora1

public int getResult(int n, int m) {
        int x = 0;
        for (int i = 1; i < n; i++) {
            x = (x + m) % (i + 1);
        }
        return x + 1;
    }

发表于 2016-12-19 19:54:20 回复(0)

丕子李

	public int getResult(int n, int m)
	{
		// write code here
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 1; i < n + 1; i++)
			list.add(i);
		int r = 0;
		while (list.size() > 1)
		{
			int k = (r + m) % list.size();
			if (k == 0)
				r = list.size() - 1;
			else
				r = k - 1;
			list.remove(r);
		}
		return list.get(0);
	}

发表于 2015-08-19 17:36:35 回复(0)

阿狸不是猫

import java.util.*;
/*
思路：因为本题的知识点是链表，因此想到可以用链表来做,至于数学方法，我真的不想用那个，第一我推不清楚，第二不符合题目考点吧
*/
public class Joseph {
    public int getResult(int n, int m) {
        LinkedList<Integer> list =new LinkedList<Integer>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        int count=0;
        while(list.size()>1){
            int goal =(count+m-1)%list.size();
            list.remove(goal);
            count =goal%list.size();//这里要注意的，就是count！=goal/////count=goal%list.size()，因为前面删了一个，size变了,不过测试例子检查不出来
        }
        return list.get(0);
    }
}

发表于 2017-06-30 10:45:38 回复(0)

Ron

    public int getResult(int n, int m) {
        // write code here
    	/*
    	 * 存在递推公式：
    	 * f(n,m)表示n个人报数m的离开，最后留下来的人的初始号码
    	 * f(n,m) = (f(n-1,m)+m)%n;
    	 */
    	if(n < 1 || m < 1){
    		return -1;
    	}
    	int last = 0;
    	if(n == 1){
    		return last;//最后一轮出局的人肯定是最后轮的第0个，要找到其初始号码
    	}
    	for(int i = 2; i <= n; i++){
    		last = (last + m) % i;//最后出来的人在倒数第i轮的号码是last
    	}
    	return last+1;//注意编号是1-n编号的，而算法是从0~n-1排序的
    }

编辑于 2016-06-04 22:40:21 回复(0)

南少201911241210480

class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        vector<int>a(n);
            int j=0;
            for(int i=0;i<n;i++)
                a[i]=i+1;
        for(int i=0;a.size()!=1;i=(++i)%a.size())
        {
            j++;
            if(j==m)
            {
                j=0;
                a.erase(a.begin()+i);
                i--;
            }
        }
        return a[0];
    }
};
创建一个数组1、2、3...n;,每次删除一个元素，最后剩下的就是需要的结果

发表于 2020-03-07 21:48:02 回复(0)

Leomh

    //链表
    int getResult(int n, int m) {
        ListNode *head = new ListNode(1),*p = head;
        for(int i=2;i<=n;++i){
            ListNode *node = new ListNode(i);
            p->next = node;
            p = p->next;
        }
        p->next = head;
        while(p->next->val!=p->val){
            int cnt = m;
            while(--cnt){
                p = p->next;
            }
            p->next = p->next->next;
        }
        return p->val;
    }

发表于 2019-09-03 22:52:13 回复(0)

C/C++

Salmon-William

思路：hh代码减了又减，这样我自己很满意了。我用vector（就是数组）来存放每个人
的编号，vector[0]=1,依次递增，数到m的元素删除，最后剩下的元素的值就是其最开
始的编号。p这个参数是上次删除的元素的位置。其实很好记： (m+p-1)%n
最简单的思路： 下面把第一次删除一个后的数组进行演示，
(k+1,...,n-1,0,1,...k-1)转换为(0~n-2)的形式，  k+1对应0  k+2对于1  ...  k-1对应n-2 可以得到这样的递推关系式：x=（x+k+1）%n;这里的n是上一次的总人数，k=(m-1)%n;
所以从最后一个剩下的人开始推算，那么就是（last+m）%2；这里的“2”是因为倒数
第一次数数的时候还剩两个人。
class Joseph {
public:
    int getResult(int n, int m) {
        vector<int> ya;
        for(int i=0;i<n;i++)
            ya.push_back(i+1);
        return  Ysf(ya,n,m,0);
    }
    int Ysf(vector<int> &ya,int n,int m,int p)
        {
        if(n==1)
            return ya.front();
        else
        {
            ya.erase(ya.begin()+(m+p-1)%n);
             return Ysf(ya,n-1,m,(m+p-1)%n);
        }     
    }
};

编辑于 2017-10-27 17:11:25 回复(0)

Zurich

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        if(n == 1) return 1;
        if(m < 1 ) return 0;
        
        int pos = 1;
        for(int i=2;i<=n; i++){
            pos = (pos + m -1)%i + 1;
        }
        return pos;
    }
}

发表于 2017-08-05 14:33:51 回复(0)

jiangcw

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        // write code here
        if(n == 1) {
            return 1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1; i<= n; i++) {
            list.add(i);
        }
        int index = 0;
        while(list.size() != 1) {
            index = (m + index - 1) % list.size();
            list.remove(index);
            
        }
        return list.get(0);
    }
}

//方法二：
import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {

        if(n<=0||m<=0)
              return -1;
        int s=0;
        for(int i=2;i<=n;i++)
            s=(s+m)%i;
        return s+1;
    }
}

编辑于 2017-06-08 19:36:41 回复(0)

disdader

数组的方式实现：

class Joseph {

public:

int getResult(int n, int m) {

vector<int> a(n);

int cur = 0;

int pre = n-1;

int count = 0;

int allPeopleCount = n;

int i;

for(i = 0; i < n-1;i++){

a[i] = i+1;

}

while(allPeopleCount){

if(++count >= m)

{

allPeopleCount--;

count = 0;

a[pre] = a[cur]; //类似指针

}

else

pre = cur;

cur = a[cur];

}

return cur+1;

}

};

递归方式实现（要提前找出递归关系）：

class Joseph {

public:

int getResult(int n, int m) {

if(n == 1)

return 1;

return (getResult(n-1,m)+m-1)%n + 1;

}

};

编辑于 2016-08-26 11:10:40 回复(0)

兔子的救兵

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：

k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1. 由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：

if(n<=0||m<=0)
           return -1;
        int s=0;
        for(int i=2;i<=n;i++)
            s=(s+m)%i;
        return s+1;

编辑于 2015-09-13 15:36:13 回复(3)

C/C++

Shari

渣渣用队列来做的 想不出递归 大神勿喷
class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        queue<int> q;
        int i = 1,j = m,k;
        while(i <= n)
            {
            q.push(i);
            i++;
        }
        while(q.size()>1)
            {
            while(j > 1)
                {
                k = q.front();
                q.pop();
                q.push(k);
                j--;
            }
            q.pop();
            j = m;
        }
        return q.front();
    }
};

发表于 2017-08-10 09:21:03 回复(0)

Java

一神

/*
 * 使用链表真实模拟踢除过程即可
 */
import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 1; i <= n; i ++) {
            list.add(i);
        }
        
        int bt = 0;
        while (list.size() > 1) {
            int delPos = (bt + m - 1) % list.size();
            list.remove(delPos);
            bt = delPos % list.size();
        }
        
        return list.get(0);
    }
}

发表于 2017-04-01 10:22:26 回复(5)

我的头最大

使用了队列这个数据结构

class Joseph {
  public:
    int getResult(int n, int m) {
        // write code here
        queue<int> qu;
        stack<int> st;
        int count = 0, pNum = 0;
        for (int i = 1; i <= n; i++) {
            qu.push(i);
        }
        while (count != n) {
                pNum++;
            if (pNum != m) {             
                qu.push(qu.front());
                qu.pop();
            } else {
                st.push(qu.front());
                qu.pop();
                pNum=0;
                count++;
            }
        }
        return st.top();
    }
};

发表于 2023-04-03 15:43:34 回复(0)

Pony_Bai

class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        if(n<1||m<1)
            return 0;
        list<int>numbers;
        for(int i=1;i<=n;++i)
            numbers.push_back(i);
        list<int>::iterator current=numbers.begin();
        while(numbers.size()>1)
        {
            for(int i=1;i<m;++i)//向后移动m次
            {
                current++;
                if(current==numbers.end())
                    current=numbers.begin();
            }
            //在删除current节点时要记录下current的下一个节点
            list<int>::iterator next=++current;//这里不能写成current+1,因为只有顺序存储结构的迭代器才有加法操作
            if(next==numbers.end())
                next=numbers.begin();
            numbers.erase(--current);
            current=next;
        }
        return *current;
    }
};


//用环形链表模拟圆圈，用list模拟环形链表
//list的底层是链表，vector的底层是数组，因此list在删除的时候要提前记录好待删除元素的下一个位置
//每次在对迭代器做完移动操作完之后都要判断迭代器是否走到了numbers的末尾，若走到了numbers的末尾，要把迭代器返回numbers的开始位置

发表于 2020-07-08 17:24:54 回复(0)

牛客280978516号

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        //初始化队列
        Queue<Integer> queue = new LinkedList<>();
        //向队列中添加元素
        for (int i=1; i<=n; i++){
            queue.offer(i);
        }
        //判断队列的元素是否为1
        while (queue.size() != 1){
            //向队列尾部添加队列前m-1个元素，同时删除队列前m-1个元素
            for (int i=1; i<m; i++){
                queue.offer(queue.poll());
            }
            //删除队列第m个元素
            queue.poll();
        }
        //如果队列只有1个元素，输出元素，不删除队列元素
        return queue.peek();
    }
}

发表于 2020-07-05 20:52:35 回复(0)

金水永

 public int LastRemaining_Solution(int n, int m) {
        if(m<=0)return -1;
        ArrayList<Integer> child = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            child.add(i);
        }
        int size=n;
        int start=0;//下一轮索引开始位置
        for(int i=0;i<size;i++){
            if (n==1)break;
            start=m%n-1==-1?(n-1 +start)%n:(m%n-1+start)%n;
            System.out.println(child.get(start));
            child.remove(start);
            n--;
        }
        return child.get(0);
    }

发表于 2020-04-03 01:37:25 回复(0)

mszjaas2

最后赢的那个人编号为1，他在上一轮里编号应为 m+1 % n。具体如下：

n=6,m=3时：1 2 3 4 5 6 删除 3 后

下一轮 1 2 3分别对应上一轮的 4 5 6，即 x + m

下一轮 4 5 对应上一轮的 1 2 ，即 (x + m) % n

但考虑余数为 0 对应时应对应上一轮的 n。

于是有代码：

int win = 1;
for (int _n=2; _n<=n; i++) {
    win = (win + m) % _n;
    if (win == 0) win = _n;
}
return win;

编辑于 2020-03-25 09:18:10 回复(0)

敢问offer在何方？

class Joseph {
public:
int getResult(int n, int m) {
list<int> lt;
    for(int i=1;i<=n;i++){
        lt.push_back(i);
    }
    list<int>::iterator it=lt.begin();
    int k;
    while(lt.size()!=1){
        k=1;
        while(k<m){
            k++;
            it++;
            if(it==lt.end()){
                it=lt.begin();
            }
        }
        it=lt.erase(it);
        if(it==lt.end()){
            it=lt.begin();
        }
    }
return lt.front();
}
};

发表于 2020-03-22 19:14:54 回复(0)

约瑟夫问题I

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题