首页 > 试题广场 >

约瑟夫问题II

[编程题]约瑟夫问题II
  • 热度指数:9847 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

现有n个人围坐一圈,顺时针给大家编号,第一个人编号为1,然后顺时针开始报数。第一轮依次报1,2,1,2...没报1的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1,2,3,1,2,3...没报1的人都出局。以此类推直到剩下以后一个人。现给定一个int n,要求返回最后一个人的编号。

测试样例:
5
返回:5
思路请参考第一赞的回答
# -*- coding:utf-8 -*-
class Joseph:
    def getResult(self, n):
        if n <= 0:
            return -1
        
        con = range(1, n + 1)
        rest = n
       	
        round = 1
        while con:
            start = 1
            for key, person in enumerate(con):
                if start == round + 2:
                    start = 1
                if start != 1:
                    rest -= 1
                    con[key] = -1
                start += 1
            con = [i for i in con if i != -1]
            if rest == 1:
                return con[0]
            con.insert(0, con.pop())
            round += 1

编辑于 2016-08-08 07:49:50 回复(1)

class Joseph {
public:
    int getResult(int n) {
        // write code here
        return helper(n,2)+1;
//换一种编号策略,从0开始,这样方便计算,所以返回结果时加1
    }
    
    int helper(int n,int c){
        if(n<=c)return 0;
        //int left=n/c+(!!(n%c));
        int left=(n-1)/c+1;//计算剩余人数
        return (helper(left,c+1)+left-1)%left*c;
//先把剩余人数看做从最后一个开始的0到left-1编号,递归返回后寻找与原始编号的关系
    }
};

编辑于 2018-09-27 23:04:33 回复(0)
自己遇到了的坑:
1.开始用了ArrayList,结果没有addFirst()方法,于是用add(index,Obiect)
的方法添加到表头,实际上只添加到index-1后。
2.在遍历链表删除报数非1的过程中,不敢在判断报数非1后直接调用remove()方法,感觉
会破坏后面的顺序,采用了比较笨的方法,改变值为-1,下一次遍历的时候根据值来删除
import java.util.*;

public class Joseph {
    public int getResult(int n) {
        // write code here
        /* 新建一个链表,依次将1-n添加到列表中(存储每个值得索引)*/
        LinkedList<Integer> list=new LinkedList<Integer>();
        for(int i=1;i<n+1;i++)
        {
            list.add(i);            
        }       
        /* 报数时的初始步长*/
        int origenStep=2;
        /* 遍历链表,直到只剩一个元素时退出 */
       	while(list.size()>1)
        {
           /* 模拟报数,将报数过程中与origenStep取余值非1的值设为-1,方便后面删除*/
            for(int i=0;i<list.size();i++)
            {            
                if((i+1)%origenStep!=1)
                {
                    list.set(i,-1);     
                }                
            }
            /*报数最大值加1*/
            origenStep++;
            /*再一次遍历链表,将值为-1的对象删除,得到报数一遍后的剩余队伍*/
            Iterator<Integer> iter=list.iterator();
            while(iter.hasNext())
            {
                if(iter.next()==-1)
                {
                    iter.remove();                 
                }        
            }
            /* 去队伍的最后一个人,加入链表头,模拟从最后一个人开始*/
           list.addFirst(list.get(list.size()-1));  
            /* 删除最后一个元素(已经加入表头中)*、         
           list.remove(list.size()-1);            
        }
        /*返回链表的第一个元素值*/
        int num=list.get(0);
        return num;      
    }
}

编辑于 2016-08-29 14:52:47 回复(0)
public static int getResult(int n) {
    // write code here
    if (n < 1) {
        return -1;
    }

    LinkedList<Integer> idList = new LinkedList<>();
    for(int i = 1; i <= n; i += 2){//第一轮偶数全都出局,所以初始化列表只需要奇数就行
        idList.add(i);
    }

    int j = 3;//第二轮开始就是报三个数了
    while(j <= n){
        idList.addFirst(idList.removeLast());//尾部移动到头部

        int len = idList.size();
        int k = 1;
        for(int i = 1; i <= len; i++){//删除时注意列表是在不停缩短的
            if (i % j != 1) {
                idList.remove(i - k);
                k++;
            }
        }

        if(idList.size() <= j){
            return idList.getLast();
        }

        j++;
    }
    
    return 1;
}
发表于 2016-04-21 19:31:09 回复(0)
怎么最后一个报数的会是第一个开始呢?还得重新调整

public class 约瑟夫问题II队列 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }
        int num = 2;
        queue.add(queue.poll());
        while (queue.size()!=1) {
            int len = queue.size();
            for (int i = 2; i <= len; i++) {
                if (i%num == 1) {
                    queue.add(queue.poll());
                }else {
                    queue.poll();
                }
            }
            num++;
        }
        System.out.println(queue.poll());
    }
}
发表于 2021-08-19 00:11:12 回复(0)
//list
int getResult(int n){
	list<int>A;
	for(int i=1;i<=n;++i)A.push_back(i);
	int index,cnt = 2;
	while(A.size()>1){
		index = 0;
		auto it = A.begin();
		while(it != A.end()){
			index = (index + 1)%cnt;
			if(index!=1)it = A.erase(it);
			else it++;
		}
		A.push_front(A.back());
		A.pop_back();
		++cnt;
	}
	return A.back();
} 

//vector
int getResult(int n) {
	vector<int>A;
	for(int i=1;i<=n;++i)A.push_back(i);
	int index,cnt = 2;
	while(A.size()>1){
		index = 0;
		for(int i=0;i<A.size();){
			index = (index+1)%cnt;
			if(index != 1)A.erase(A.begin()+i);
			else ++i;
		}
		A.insert(A.begin(),A.back());
		A.pop_back();
		cnt++;
	}
	return A[0];
}

发表于 2019-09-04 13:15:48 回复(0)
#用字典来解决约瑟夫问题
# -*- coding:utf-8 -*-
class Joseph:
    def getResult(self, n):
        # write code here
        dic = {}
        for i in range(1,n+1):
            dic[i] = 0
        k = 2
        t = 1
        while len(dic) > 1:
            if t == 1:
                j = 1
                for i in dic:
                    if j > k:
                        j =1
                    dic[i] = j
                    j += 1
                k += 1
                t += 1
                for i in dic.keys():
                    if dic[i] != 1:
                        dic.pop(i)
            else:
                if t == 2:
                    rese = []
                    for i in dic:
                        rese.append(i)
                rese.insert(0,rese.pop())
                i = len(rese)
                while i > 0:
                    j = 1
                    for p in range(len(dic)):
                        if j > k:
                            j = 1
                        dic[rese[p]] = j
                        j += 1
                    i = i -1
                k += 1
                t += 1
                for i in dic.keys():
                    if dic[i] != 1:
                        dic.pop(i)
                        rese.remove(i)
        for i in dic.keys():
            return i
编辑于 2018-11-14 23:29:46 回复(0)
 public int getResult(int n) {
        // write code here
        if(n<=2){
            return 1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1;i<=n;i+=2){//第一轮 先淘汰掉偶数  剩下全是奇数
            list.add(i);
        }
        int count = 3;
        while(count<=n){
            int last = list.removeLast();
            list.addFirst(last);
            int k = 1;//这个k用的比较好
            int len = list.size();//保留原来列表长度
            for(int i = 1;i<=len;i++){//接下来列表长度是在变化的
                if(i%count!=1){
                    list.remove(i-k);
                    k++;//所以删除一个元素就让k加1,因为删除元素后面的元素都进行了前移,这样下次再删除时能够删除正确元素
                }
            }
            if(count>=list.size()){
                return list.getLast();
            }
            count++;
        }
        return 1;//这个其实就是为了编译通过,根本不会走到这一步的
    }

发表于 2017-07-09 18:19:05 回复(0)
每次记录上次最后报数的位置,不断更新每轮剩下的人,直至剩下一个人
class Joseph {
public:
    int getResult(int n)
    {
        if (n <= 2) return 1;
        n >>= 1;
        vector<int> people(n + 1);
        for (int i = 0; i <= n; ++i) people[i] = 1 + (i << 1);
        int last = n;
        int m = 3;
        while (people.size() > 1)
        {
            vector<int> pre, post;
            int curNum = 1;
            post.emplace_back(people[last]);
            for (int i = last + 1; i < people.size(); ++i)
            {
                ++curNum;
                if (curNum == m + 1) curNum = 1;
                if (curNum == 1) post.emplace_back(people[i]);
            }
            for (int i = 0; i < last; ++i)
            {
                ++curNum;
                if (curNum == m + 1) curNum = 1;
                if (curNum == 1) pre.emplace_back(people[i]);
            }
            last = pre.size() - 1;
            pre.insert(pre.end(),post.begin(), post.end());
            swap(pre, people);
            ++m;
        }

        return people[0];
    }
};

发表于 2017-06-29 11:38:58 回复(0)
有没有数学大神可以提供数学关系式来计算结果?
发表于 2016-12-28 22:03:08 回复(0)
public int getResult(int n) {
        Node head, t, p; //p记录上一个节点,t是临时节点
        p = head = t = new Node(1);
        for (int i = 2; i <= n; i++, t = t.next) {
            t.next = new Node(i);
        }
        t.next = head; // 构成环

        for (int k = 2; n != 1; k++) { //k代表级数,当只有一个节点时跳出循环
            t = p;
            final int size = n;
            for (int i = 1, cnt = 1; i <= size; i++, cnt++, t = t.next) { //cnt计数, size代表一圈的Node个数
                if (cnt == 1) {
                    p = t;
                    continue;
                }
                if (cnt == k)
                    cnt = 0;
                p.next = t.next;
                n--;
            }
        }
        return t.val;
    }

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

发表于 2016-12-20 13:14:22 回复(0)
class Joseph {
public:
    int getResult(int n) {
        list<int> l;
        for(int i = 1; i <= n; ++i)
            l.push_back(i);

        for(int i = 2; i < INT_MAX; ++i)
        {
            if(l.size() == 1)
                	break;
            int j = 1;
            for(auto itr = l.begin(); itr != l.end(); ++j)
            {
                if(j % i != 1)
                    l.erase(itr++);
                else
                   ++itr;
            }
            l.push_front(l.back());
            l.pop_back();
        }
        return l.front();
    }
};
编辑于 2016-09-06 09:38:42 回复(0)
int getResult(int n) {
        if (n <= 0)return 0;
        if (n <= 1)return 1;
        int CNT = 1;
        vector<int> arr;
        vector<int> arr2;
        for (int i = 1; i <= n; i++)
            arr.push_back(i); //index
        while (CNT++)
        {            
            for (int jj = 0; jj < arr.size();jj += CNT)
                arr2.push_back(arr[jj]);
            if (arr2.size() <= 1)break;
            swap(arr2, arr);
            arr2.clear();
            int tmp = arr[arr.size() - 1];
            arr.erase(arr.end() - 1);
            arr.insert(arr.begin(), tmp);
        }      
        return arr2[0];
    }
编辑于 2016-08-08 21:08:32 回复(0)
int getResult(int n) {
	vector<int>a(n, 0);
	for (int i = 0; i < n; i++)
		a[i] = i+1;
	vector<int>b;
	int num = 2;
	while (a.size() != 1)
	{
		for (int i = 0; i < a.size(); i++)
		{
			if ((i+1) % num == 1)
			{
				b.push_back(a[i]);
			}
		}
		int tmp = b[b.size() - 1];
		b.pop_back();
		a = b;
		a.insert(a.begin(), tmp);
		b.clear();
		num++;
	}
	return a[0];
	// write code here
}

发表于 2015-09-21 16:33:30 回复(0)
思路:新建一个数组a[n],让每一个留下的人对应在数组里的值为下一个留下的人的序号
然后遍历数组,把报数不为1的人剔除。注意记录开始位置
代码如下:
class Joseph {
public:
    int getResult(int n) {
        // write code here
        int *a = new int[n];
 int i, b_pos = 0, prepos, pos;
 for(i = 0; i < n - 1; i ++)
  a[i] = i + 1;
 a[i] = 0;
 int count = 2;
 int num;
 while(a[b_pos] != b_pos)
 {
  //报数从1开始
  num = 1;
  //pos和prepos赋值为开始位置
  pos = b_pos;
  prepos = b_pos;
  //先判断下一个pos是不是b_pos
  while(a[pos] != b_pos)
  {
   pos = a[pos];
   num ++;
   //判断报数是否到达最大值
   if(num == count)
   {
    num = 1;
    //判断下一个可以留下的人是否是开始位置的人
    if(a[pos] == b_pos)
     break;
    pos = a[pos];   //当前留下的人的位置
    a[prepos] = pos;  //上一个留下的人指向
    prepos = pos;   //更新上一个留下的人的位置
   }
  }
  a[prepos] = b_pos;
  b_pos = prepos;
  count ++;
 }
 return (b_pos + 1);
    }
};
发表于 2015-08-17 17:16:11 回复(0)
解题思路:
1. 由于涉及到频繁的删除操作,故数据结构应该选择链表,这里选择LinkedList,其底层实现是循环双链表。
2. 每一轮报数完毕之后,将链表尾部节点移动到链表首部,开始新一轮的报数。
3. 链表中仅剩一个节点,程序结束。
4. 举个例子:假设n = 24,第一个人编号为1。
(1)第一轮:依次报1,2,1,2...然后报到2的人出局,则第一轮过后未出局的编号为1、3、5、7、9、11、13、15、17、19、21、23;
(2)第二轮:从上一轮最后一个报数的人开始依次报1,2,3,1,2,3...报到2,3的人出局。我这里做的处理是,先将上一轮最后一个报数的编号移动到最前面,即23、1、3、5、7、9、11、13、15、17、19、21;然后开始第二轮报数,未出局的编号为23、5、11、17;
(3)第三轮:从上一轮最后一个报数的人开始依次报1,2,3,4,1,2,3,4...报到2,3,4的人出局。同样,我这里做的处理是,先将上一轮最后一个报数的编号移动到最前面,即17、23、5、11;然后开始第三轮报数,未出局的编号为17,此时链表中仅剩一个节点,故程序结束。
	/**
	 * 核心数据结构:双链表
	 */
	public int getResult(int n) {
		if (n < 1)
			return -1;
		LinkedList<Integer> list = new LinkedList<Integer>();
		int round = 2, i, curr = 0;
		for (i = 1; i <= n; i++) {
			list.add(i);
		}
		while (list.size() > 1) {
			i = 0;
			while (list.size() > 1 && i < list.size()) {
				curr = (curr + 1) % round;
				if (curr != 1) {
					list.remove(i);
				} else {
					i++;
				}
			}
			round++;// 下一轮的最大报数
			curr = 0;// 表示还未开始报数
			if (list.size() > 1) {// 将最后报数的元素移动到链表首部,即确保每次报数从链表首部开始。
				int last = list.removeLast();
				list.addFirst(last);
			}
		}
		return list.pop();// 返回最后一个元素
	}

发表于 2015-09-07 12:55:48 回复(11)
解题思路,模仿约瑟夫环问题
假设n=30, 每次跳跃距离为m, 初始为m=2
第一次筛选后剩下为 [29, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27], m=3  
第二次筛选后剩下为 [23, 29, 5, 11, 17], m=4
第三次筛选后剩下为 [17, 23] m=5
此时结果已出, 最后剩下肯定是17, 其实在第二次筛选后结果已出, 因为此时n/4+1<m+1, 表示下次筛选时剩下结果小于m, 为下次筛选后的第一个, 也就是本次筛选后的最后一个.
为什么选择第二次的筛选结果呢?  因为此时还保留着位置信息x
计算出第二次筛选后x的位置为5, 则第一次筛选的位置x=(5-2)*m+1=10, 正好是17所在的位置数
同理, 原位置x=(10-2)*m+1=17, 所以答案为17
描述的可能不清楚, 各位大佬对着代码凑合看吧(⊙﹏⊙)
import java.util.*;

public class Joseph {
    public int getResult(int n) {
		return ysf(n, 2);
    }
    public int ysf(int n, int m) {
        int tmp = n%m==0 ? n/m : n/m+1;
        if(tmp <= m+1) {
            return (tmp-1)*m+1; //终止条件
        }
        int path = ysf(tmp, m+1); //m+1次时最后一人编号的位置
        return (path-2)*m + 1;
    }
}

发表于 2017-05-02 22:40:04 回复(7)
其实这个题用vector<int>来做是非常方便,链表这些太复杂了,下面是思路:
1、数组joseph为[1,n],每次循环就用一个局部变量tmp来存放保留的元素;
2、将tmp的最后一个元素插入到tmp的头,再将最后一个元素删除;
3、将tmp与joseph交换。
代码如下:
class Joseph {
public:
    int getResult(int n) {
        // write code here
        vector<int> joseph;
        for (int i = 1; i <= n; i++) {
            joseph.push_back(i);    // 生成joseph数组
        }
        int m = 2;                // 起始间隔
        while (joseph.size() != 1) {    // 直到只有一个元素为止
            vector<int> tmp;
            tmp.push_back(0);    // 先放一个元素进去,避免第2步头插数组整体后移
            for (size_t i = 1; i <= joseph.size(); i += m) {
                tmp.push_back(joseph[i - 1]);    // 把要保留的元素取出来
            }
            tmp[0] = tmp.back();// 第2步,把最后一个元素放在第一位置
            tmp.erase(tmp.end() - 1);// 去掉最后一个元素
            joseph.swap(tmp);        // 交换
            m++;        // 间隔增1
        }
        return joseph.back();    // 返回唯一的元素
    }
};

发表于 2017-08-16 15:46:09 回复(4)
/*
思路:
以n=5举例:
1 2 3 4 5	遍历第1次
1 2 1 2 1
1 3 5		遍历第2次
2 3 1
==>5

(1)每次遍历的个数不同,用两个变量控制
count计数器,len更新每次链表长度
(2)三个迭代器控制删除,起始位置
cur:当前位置
next:链表删除会使cur失效,next用来记忆cur位置
last:用来更新每次遍历的初始位置
*/
class Joseph {
public:
	int getResult(int n) {
		// write code here
		list<int> circle;
		for (int i = 1; i <= n; i++)
		{
			circle.push_back(i);
		}

		list<int>::iterator cur, next, last = circle.begin();
		int count, len, m = 1;
		while (circle.size() > 1)
		{
			len = circle.size();
			count = 1;
			m++;
			cur = last;
			while (count <= len)	//遍历1次
			{
				for (int i = 0; i < m; i++)
				{
					next=++cur;
					if (next == circle.end()) next = circle.begin();
					cur--;
					if (i != 0) circle.erase(cur);
					else last = cur;
					cur = next;
					count++;
					if (count > len) break;		//if (count >= len) error!!!
				}
			}
		}

		return circle.front();
	}
};

发表于 2017-02-20 15:31:29 回复(0)
输入210得到77的同学:
注意题目的意思:
从上一轮最后一个报数的人开始
就相当于,把最后一个拉倒第一个
                  然后开始正序报数
大概是一道语文题
发表于 2017-09-15 17:07:07 回复(3)