垃圾一枚 2017-11-24 02:40 采纳率: 50%
浏览 1396
已采纳

数据结构的题 有没有大佬

约瑟夫(Joseph)问题的一种描述是:设编号为1,2,…,n的n(n>0)个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。开始时任选一个整数作为报数上限值m,从一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。要求设计一个程序模拟此过程,求出出列顺序。
(2) 设计要求
设计一个程序,以人机交互方式执行,用户指定约瑟夫环游戏的总人数n和初始的报数上限m,然后输入每个人所持有的密码key。模拟约瑟夫环,从头开始报数,直到所有的人出列。系统按照出列顺序给出编号。
(3) 数据结构
本设计利用带头结点的单循环链表作为模拟约瑟夫环游戏的存储结构。

  • 写回答

5条回答 默认 最新

  • Debug_dodge 2017-11-24 02:57
    关注
     #include <iostream>
    using namespace std;
    
    struct monkey
    {
    int num;
    monkey *next;
    };
    
    int joseph(int sum, int cycle)
    {
    int i;
    monkey *p_old, *p_new, *head=NULL;
    
    head = new monkey;
    //此处创建一个循环链表(create a circular chained table)
    head->num = 1;
    p_old = head;
    for(i=2; i<=sum; i++)
    {
    p_new = new monkey;
    p_new->num = i;
    p_old->next = p_new;
    p_old = p_new;
    }
    p_new->next = head;
    
    p_old = head;
    i = 1;
    //循环删除元素直到只剩下最后一个元素(delete elements circularly until the last element left)
    while(1)
    {
    p_new = p_old->next;
    i++;
    if(p_new == p_old)
    break;
    if((i % cycle) == 0)
    {
    p_old->next = p_new->next;
    p_new->next = NULL;
    delete p_new;
    i = 0;
    }
    else
    {
    p_old = p_new;
    }
    }
    
    return p_new->num;
    }
    
    int main(void)
    {
    int n,m;
    cin>>n>>m;
    cout<<joseph(n,m)<<endl;
    return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

  • ¥15 如何基于Ryu环境下使用scapy包进行数据包构造
  • ¥15 springboot国际化
  • ¥15 搭建QEMU环境运行OP-TEE出现错误
  • ¥15 Minifilter文件保护
  • ¥15 有限元软件终止时间超过设定值
  • ¥15 onvif框架引用一直报错
  • ¥50 C#和C++混合编程,使用CLR托管,报错System.Runtime.InteropServices.SEHException
  • ¥30 .NET使用sqlite发布后报错
  • ¥15 Unity在WebGL平台导出Word报错问题
  • ¥15 ghpython这里总是报错而且rhino视图窗口内不显示怎么办