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

数据结构的题 有没有大佬

约瑟夫(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;
    }
    
    点赞 打赏 评论
  • Debug_dodge 2017-11-24 02:42

    基础题,百度一下就有答案了

    点赞 打赏 评论
  • qq_23497599 2017-11-24 02:53

    可以google一下 哈哈

    点赞 打赏 评论
  • qq824827715 2017-11-24 02:55
    点赞 打赏 评论
  • qqxiaolifeidao 2017-11-24 03:08

    这个度娘上就有答案 百度一下就知道了

    点赞 打赏 评论

相关推荐