首页 > 试题广场 >

约瑟夫环是一个数学应用题：已知n个人（编号1、2、..n）围

[问答题]

约瑟夫环是一个数学应用题：已知n个人（编号1、2、..n）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个又从1开始报数，数到m的那个人又出列；依次规律重复下去，直到圆桌周围的人全部出列。请编写一个程序，给定n、m计算出列人员先后顺序。

查看答案及解析
添加回答
少吃点吧头像 少吃点吧 
#include<list>
#include<iostream>
#include<vector>
using namespace std;
vector<int> Yuesefu(int n, int m) {
    list<int> myList;
    vector<int> res;
    for (int i = 1; i <= n; i++)
        myList.push_back(i);
    int index = 0;
    while (myList.size() > 1) {
        list<int>::iterator it = myList.begin();
        index = (index + m - 1) % myList.size();
        advance(it, index);
        res.push_back(*it);
        myList.erase(it);
    }
    return res;
}
int main() {
    int n, m;
    cin >> n;
    cin >> m;
    vector<int> res = Yuesefu(n, m);
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << endl;
}

编辑于 2020-03-06 16:26:33 回复(0)
倚杖听江声头像 倚杖听江声

#include "iostream"

using namespace std;
struct Listnode
{
    int data;
    Listnode* next;
    Listnode(int a)
    {
        data = a;
        next = nullptr;
    }
};
Listnode* create(int size)
{
    Listnode* head = new Listnode(1);
    Listnode* p = head;
    for (int i = 0; i < size - 1; i++)
    {
        p->next = new Listnode(i + 2);
        p = p->next;
    }
    p->next = head;
    return head;
}

Listnode* dele(Listnode* begin, int m)//递归 将上一次处理的结果当做下一次处理的输入
{
    if (begin == begin->next)
    {
        cout << begin->data << endl;
        return begin;
    }
    Listnode* p = begin;
    for (int i = 0; i < m - 1; i++)
    {
        p = p->next;
    }
    cout << p->data << endl;
    p->data = p->next->data;
    Listnode* temp = p->next;
    p->next =temp->next;
    delete temp;
    return dele(p, m);
}

int _tmain(int argc, _TCHAR* argv[])
{
    Listnode *head = create(5);
    dele(head, 2);

    return 0;
}

发表于 2018-08-07 17:54:13 回复(1)
寻路201809200937255头像 寻路201809200937255
对于这种带有循环结构的题，一般都可以建立循环链表然后队链表进行操作，这样不仅可以输出最后一个，还可以一次输出淘汰的编号
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n==0||m==0){
            return -1;    
        }
        Node head = new Node();
        head.value = 0;
        head.next = head;
        Node nn = head;
        Node e = head;
        for(int i = 1;i<=n-1;i++){
            while(nn.next!=head){
            nn = nn.next;
            }
            Node node = new Node();
            node.value = i;
            nn.next = node;
            node.next = head;
        }
        for(int k = 1;k<=n-1;k++){
            for(int i=1;i<=m-2;i++){
                e = e.next;
            }
            Node d = e.next;
            e.next = d.next;
            e = d.next;
        }
        return e.value;
    }
}
class Node {
    public int value;
    public Node next = null;
}

发表于 2019-03-05 01:04:19 回复(1)
veralane头像 veralane
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int a[1001];
    for(int i=0;i<1001;i++)
    {
        a[i]=0;
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        int t=m;
        while(t>0)
        {
            if(a[k]==0)
            {
                t--;
            }
            k=(k+1)%n;
        }
        if(k==0)
        {
            a[n-1]=1;
            cout<<n<<endl;
        }
        else
        {
            a[(k-1)%n]=1;
            cout<<k<<endl;
        }
    }
    return 0;
} 

发表于 2018-08-13 10:33:35 回复(0)
qtSunnylove头像 qtSunnylove
这个参考答案是不是不太对，main函数里面应该调用的是fun(L,m-1),出来的结果才是对的。
发表于 2018-08-03 15:50:45 回复(0)
求杭州收留头像 求杭州收留 
# *_* coding: utf-8 *_*


class Node():
    def __init__(self, data):
        self.data = data
        self.next = None


def create(n):
    head = Node(1)
    p = head
    for i in range(2, n+1):
        q = Node(i)
        p.next = q
        p = q
    p.next = head
    return head


def get_sequence(n, m):
    linklist = create(n)
    print("check created linklist")
    print(linklist.data)
    print(linklist.next.data)
    print(linklist.next.next.data)
    print(linklist.next.next.next.data)
    print(linklist.next.next.next.next.data)
    print(linklist.next.next.next.next.next.data)
    print(linklist.next.next.next.next.next.next.data)
    print('*' * 20)

    p = linklist
    while p.next != p:
        for i in range(1, m):
            q = p
            p = p.next
        # print the mth node
        print(p.data)
        q.next = p.next
        p = p.next
    # print the last one in the list
    print(p.data)


def main():
    n, m = 7, 5
    get_sequence(n, m)


if __name__ == '__main__':
    main()
发表于 2018-08-03 09:11:04 回复(0)
牛客589895105号头像 牛客589895105号
import java.util.*;
public class Main {
    public static void main(String[] args) {
        CirCleSingleLinkedList list = new CirCleSingleLinkedList();
        Scanner scan=new Scanner(System.in);
        int num1=scan.nextInt();
        int num2=scan.nextInt();
        list.add(num1);
        list.chu(num2);
    }
    
}
class CirCleSingleLinkedList{
    private HeroNode1 first=null;
    
    public void chu(int count){
        HeroNode1 temp=first;
        while(true){
            if(temp.next==first){
                break;
            }
            temp=temp.next;
        }
        
        
        
        while(true){
            if(temp==first){
                break;
            }
            
            for(int i=0;i<count-1;i++){
                first=first.next;
                temp=temp.next;
            }
            //System.out.println(first.id);
            first=first.next;
            temp.next=first;
            
        }
        System.out.println(first.id);
        
    }
    
    public void add(int num){
        if(num<1){
            return;
        }
        HeroNode1 temp=null;
        
        for(int i=1;i<=num;i++){
            HeroNode1 boy=new HeroNode1(i);
            if(i==1){
                first=boy;
                first.next=first;
                temp=first;
            }else{
                temp.next=boy;
                boy.next=first;
                temp=boy;
            }
        }
        
    }
    
    
        
    
    
}



class HeroNode1{
    public int id;
    public HeroNode1 next;
    public HeroNode1(int id) {
        super();
        this.id = id;
    }
    @Override
    public String toString() {
        return "HeroNode1 [id=" + id + "]";
    }
    
    
}


发表于 2021-11-11 14:22:59 回复(0)
违约金好贵头像 违约金好贵
for(i=1;i<=m;i++)应该是for(i=1;i<m;i++)，这样子才是第m个出去
发表于 2019-06-04 13:52:24 回复(0)
小人物啊头像 小人物啊
#include<iostream>
#include<list>
#include<vector>
using namespace std;
vector<int> yuesefu(int m, int n)
{
    list<int> li;
    vector<int> v;
    for (int i = 0; i < n; ++i)
        li.push_back(i+1);
    auto iter = li.begin();
    while (!li.empty())
    {
        for (int i = 1; i < m; ++i)
        {
            iter++;
            if (iter == li.end())
                iter = li.begin();
        }
        v.push_back(*iter);
        iter=li.erase(iter);
        if (iter == li.end())
            iter = li.begin();
    }
    return v;
}
int main()
{
    vector<int> v(yuesefu(5, 20));
    for (auto ele : v)
        cout << ele << endl;
    return 0;
}
发表于 2019-06-03 15:38:58 回复(0)
足坛吴彦祖头像 足坛吴彦祖 
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
  int n,m;
  cin>>n>>m;
  if(n<1||m<1)
  {
     return 0;
  }
  int last =0;
for(int i=2;i<=n;i++)
{
last = (last+m)%i;
}
cout<<last<<endl;
  return 0;
}

发表于 2019-05-28 11:26:36 回复(0)
mudrich-fang头像 mudrich-fang 
约瑟夫问题的数列转换解法，原理参照：[https://www.nowcoder.com/questionTerminal/11b018d042444d4d9ca4914c7b84a968](https://www.nowcoder.com/questionTerminal/11b018d042444d4d9ca4914c7b84a968)

======================================================================

链接：https://www.nowcoder.com/questionTerminal/11b018d042444d4d9ca4914c7b84a968
来源：牛客网
把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）

本题解法：上约瑟夫问题解法只能求出最后一个删除的元素，需要转换n-1次。
最后一个元素的原序列标号可以通过上述方法解得，需要经过n-1次转换，若要求倒数第二个元素的原序列标号，需要两步：
(1)求出倒数第二个元素在其删除时的编号（第n-1次删除时的编号，k=(m-1)%i）；
(2)经过n-2次约瑟夫转换（f(i) = (f(i-1)+m)%i）即可得到删除序列逆向序列。


public ArrayList transfer(int n,int m){
    ArrayList res = new ArrayList();
    if(n<=0) return res;
    for(int i=1;i<=n;i++) {//将序列1-n表示为0-(n-1),方便通过求余的方法求出每次被选中的元素
        int index = (m-1)%i;//每次被抽取的数，逆向添加数
        res.add(index);
        for(int j=0;j<res.size();j++) {//转化n-1次
            if(i<n)//未到最后一次，仍然需要转化
                res.set(j, (res.get(j)+m)%(i+1));
            if(i==n) {//转化完成
                res.set(j, (res.get(j)+1));
            }
        }
    }
    Collections.reverse(res);
    return res;
}
发表于 2019-05-27 17:09:47 回复(0)
学习使我快乐虚妄头像 学习使我快乐虚妄 
ArrayList<Integer> list = new ArrayList<>(n); List<Integer> returnList=new ArrayList<>(n); if (n == 0 || m == 0) { return list; } for (int i = 1; i <= n; i++) {
    list.add(i); } int index=0; for (int i = 0; i < n; i++) {
    index=(index+m-1)%list.size();  returnList.add(list.get(index));  list.remove(index); } return (ArrayList<Integer>) returnList;

发表于 2019-05-20 21:45:19 回复(0)
但求八月九月好运！头像 但求八月九月好运！ 

	//方法很多





	#include <iostream>





	#include<vector>





	#include<algorithm>





	usingnamespacestd;





	voidgetpop(vector<int>&pp,vector<int>num,intm)





	{





	    intcursize=num.size(),cnt=0,index=-1;





	     vector<int>state(cursize);





	     fill(state.begin(),state.end(),0);





	     while(cursize>0)





	     {





	         ++cnt;





	         index=(index+1)%num.size();





	         while(state[index]!=0)





	             index=(index+1)%num.size();





	         if(cnt==m)





	         {





	             pp.push_back(num[index]);





	             cnt=0;





	             --cursize;





	             state[index]=1;





	         }





	     }





	}





	intmain()





	{





	    intm,n;





	    cin>>n>>m;





	    vector<int>num(n);





	    iota(num.begin(),num.end(),1);





	    vector<int>p;





	    getpop(p,num,m);





	    for(inti=0;i<p.size();++i)





	        cout<<p[i]<<" ";





	    cout<<endl;





	    return0;





	}

发表于 2019-05-18 15:50:35 回复(0)
ColorfulBlack头像 ColorfulBlack 
public class calOutOrder {
    public static void main(String[] args) {
        cal(10, 3);
    }
    /**
     * 输出报数m的人的编号
     *
     * @param n 人数
     * @param m 报数出列
     */
    public static void cal(int n, int m) {
        int[] outList = new int[n + 1];
        int outNum = 0;
        for (int i = 1, count = 0; outNum  < n; i = i < n ? i + 1 : 1) {
            if (outList[i] == 0) {
                count++;
                if (count == m) {
                    count = 0;
                    outList[i] = 1;
                    outNum++;
                    System.out.println(i);
                }
            }
        }
    }
}

发表于 2019-04-10 20:56:57 回复(0)
Mr_vox头像 Mr_vox 
//java版
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Ysf {     public static void main (String[] args)     {         System.out.println("please input n:");//总数         Scanner scanner=new Scanner(System.in);         int n=scanner.nextInt();         System.out.println("please input k:");//开始编号,从1到n         int k=scanner.nextInt();         System.out.println("please input m:");//增量         int m=scanner.nextInt();         System.out.println("*****************************************");         ysf(n,k,m);         scanner.close();              }     static void ysf(int n,int k,int m)     {         List<Integer> list=new ArrayList<Integer>();         for    (int i=0;i<n;i++)         {             list.add(i+1);         }                  int index=k-1;         while(list.size()>0)         {                          index=(index+1+m)%list.size()-1;             if(index==-1)             {                 System.out.println(list.get(list.size()-1));                 list.remove(list.size()-1);                 index=0;             }             else {                 System.out.println(list.get(index));                     list.remove(index);             }         }     }
}

发表于 2019-03-03 16:39:06 回复(0)
hustlgz头像 hustlgz 
#include<stdio.h>
int main()
{     int num[100];     int m,n,i,k=0,s=0;     printf("请输入总人数n和输出序号m:\n");     scanf("%d%d",&m,&n);     for(i=1;i<=n;i++)         num[i]=i;     i=1;     while(k<=n) //k统计出队的人数     {         if(num[i]!=0)             s++; //表示报数报到第几个人         if(s==m)         {             printf("%4d",i);             num[i]=0;             k++;             s=0;         }         ++i;         if(i>n)             i=1;     }     }

发表于 2018-09-12 22:00:18 回复(0)
DreamGrean头像 DreamGrean 
//  约瑟夫环的问题     循环链表 // m 表示跳几个位置    n 表示几个人   import java.util.Scanner; public class test1 { public static class Node{ // 建立内部节点类   int val ; // 节点的值   Node next; // 下一个节点的地址   public Node(int val){ this.val = val;
                       }

                  }  public static void main(String[] args) {
           
            Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 总人数  int m = sc.nextInt(); // 跳几个   // 建立循环单链表  Node head = new Node(1); // 头节点   Node cur = head; for (int i = 2; i<=n;i++){
            cur.next= new Node(i);
            cur = cur.next;
               }
           cur.next = head ;
           cur = cur.next; // 指向头节点   Node p ; while (cur.next!=cur){ // 当不是一个节点时   for (int i = 1 ;i<m-1;i++){ // 循环为m-2   cur = cur.next;
           }
           p = cur.next; // 指向循环后的第一个节点  System.out.print(p.val+"--"); // 输出该值   cur.next = p.next; //   cur = p.next; // 删除节点操作   }
           System.out.print(cur.val); // 输出该值  }

    }

发表于 2018-09-11 10:31:58 回复(0)
TangAihui头像 TangAihui 

	

import java.util.*;
public class Main{  public static void main(String[] args) {  josephRing(10,5);
    }  private static void josephRing(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();  for (int i = 1; i <= n; i ++) {
            list.add(i);
        } int index = m - 1;  while (list.size() != 0) {
            index %= list.size();
            System.out.print(list.remove(index) + "\t");
            index += m - 1;
        }
        System.out.println();
    }
}

system  ['sɪstəm]  详细X
基本翻译
n. 制度，体制；系统；方法
网络释义
System: 系统
Nervous System: 神经系统
binary system: 联星系统
发表于 2018-08-26 19:35:07 回复(0)
very-day头像 very-day
#include <iostream>

using namespace std;

struct Node{
    int num;
    Node* next;
    Node(int d): num(d), next(nullptr){}
};

Node* creatList(int n)
{
    Node *p = new Node(1);
    Node *head = p;
    for(int i = 2; i <= n; i++) {
        Node *q = new Node(i);
        p->next = q;
        p = q;
    }
    p->next = head;
    return head;
}

void output(Node *root, int m) 
{
    Node* p = root;
    while(p->next != p) {
        for(int i = 1; i < m-1; i++) {
            p = p->next;
        }
        Node *temp = p->next;
        p->next = temp->next;
        p = temp->next;
        cout << temp->num << " ";
        delete temp;
    }
    cout << p->num << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    Node* root = creatList(n);
    output(root, m);
    return 0;
}
发表于 2018-08-09 19:48:31 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa 
#include "stdafx.h"  
#include <iostream>
#include <vector>

using namespace std;

struct List {
    List(int a = 0,List * b=NULL):x(a),next(b) {}
    int x;

    List * next;
};
void recurise(vector<int> & ans, List * head, int & m) {
    List * tmp = head;
    if (tmp->next == tmp) {
        ans.push_back(tmp->x);
        return;
    }
    for (int i = 2; i<m; ++i) tmp = tmp->next;
    ans.push_back(tmp->next->x);
    tmp->next = tmp->next->next;
    recurise(ans, tmp->next, m);
}
List * create_List(int n) {
    List * head = new List(1, NULL),* tmp=head;
    for (int i = 2; i <= n; ++i) {
        tmp->next = new List(i, NULL);
        tmp = tmp->next;
    }
    tmp->next = head;
    return head;
}

void delete_List(List * head) {
    for (List * tmp=head,* save;;) {
        save = tmp->next;
        if (save == head)
            break;
        delete tmp;
        tmp = save;
    }
}

int main(void) {
    int m, n;
    vector<int> ans;
    List * head;
    while (cin >> n >> m) {
        head=create_List(n);
        recurise(ans,head, m);
        delete_List(head);
        for (int i = 0; i < ans.size(); ++i)
            cout << ans[i] << " ";
        cout << endl;
        ans = {};
    }
}
循环链表，可以解决，但是如果使用循环数组，时间复杂度太大，不应该采用，此时，整个算法时间复杂度为O(mn),空间复杂度为O(n);
发表于 2018-08-09 18:07:01 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 2018 PHP工程师 vivo Java工程师
来自：vivo 2018秋招...
上传者：小小
难度：
28条回答 7042浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号