【数据结构】单向循环链表应用-约瑟夫环

落日映苍穹つ 2022-03-07 05:40 211阅读 0赞

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止

#include<iostream>
    using namespace std;
    int n=7, m=20;
    typedef struct node{
        int no;
        int key;
        struct node* next;
    }List;
    List *Create() {
        List *head=new node;
        head->next=NULL;
        List *q=head;
        cout<<"依次输入"<<n<<"个人的密码:"<<endl;
        for (int i=0; i<n; i++) {
            List *p=new node;
            p->no=i+1;
            cin>>p->key;
            p->next=NULL;
            q->next=p;
            q=p;
        }
        q->next=head->next;
        return head;
    }
    void Run(List *head) {
        List *p=head;
        cout<<"出列序列:"<<endl;
        for (int k=0; k<n; k++) {
             for (int i=0; i<m-1; i++)
                p=p->next;
            m=p->next->key;
            cout<<p->next->no<<" ";
            p->next=p->next->next;
        }
    }
    int main(){
        List *head=Create();
        Run(head);
        return 0;
    }
    // 测试数据：3 1 7 2 4 8 4
    // 输出：6 1 4 7 2 3 5

发表评论取消回复

表情：

评论列表（有 0 条评论，211人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构约瑟夫环问题，链表环的问题。

一.约瑟夫环问题使用单链表解决约瑟夫环问题，基本思想：设置一个计数器count和工作指针p和q，当计数器累加到m时，删除结点p。为了能够让计数器从1开始计数，将采

﹏ヽ暗。殇╰゛Y/ 2023年10月03日 02:21/ 0 赞/ 6 阅读

相关 PHP实现单向链表解决约瑟夫环问题

约瑟夫环问题：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆

痛定思痛。/ 2022年09月22日 11:39/ 0 赞/ 160 阅读

相关数据结构循环链表的应用：约瑟夫环问题

include <stdio.h> include <stdlib.h> include <iostream.h> defin

墨蓝/ 2022年09月19日 01:29/ 0 赞/ 150 阅读

相关【数据结构】循环单链表约瑟夫回环问题

include<stdio.h> include<stdlib.h> typedef struct data {

电玩女神/ 2022年08月25日 01:52/ 0 赞/ 172 阅读

相关约瑟夫问题(单向循环链表应用实例)

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于

ゞ浴缸里的玫瑰/ 2022年08月08日 06:14/ 0 赞/ 191 阅读

相关单循环链表--约瑟夫环

include <stdio.h> include <stdlib.h> //单链表类型定义 typedef struct node

男娘i/ 2022年06月17日 07:23/ 0 赞/ 210 阅读

相关约瑟夫环-(数组、循环链表、数学)

约瑟夫环（[约瑟夫问题][Link 1]）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他

╰+哭是因爲堅強的太久メ/ 2022年05月08日 05:24/ 0 赞/ 226 阅读

相关链表实现约瑟夫环

include<stdio.h> include<malloc.h> define false 0; define ok 1;

左手的ㄟ右手/ 2022年04月22日 12:06/ 0 赞/ 196 阅读

相关循环链表解决约瑟夫环问题

　　约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。　　什么是约瑟夫环？　　“约瑟

Love The Way You Lie/ 2022年04月10日 08:22/ 0 赞/ 217 阅读

相关【数据结构】单向循环链表应用-约瑟夫环

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人

落日映苍穹つ/ 2022年03月07日 05:40/ 0 赞/ 212 阅读