【吉大刘大有数据结构绿皮书】约瑟夫问题:旅游代理商选择了n个顾客来竞争最后的免费环游世界大奖。代理商让顾客们排成一个圆圈,然后从帽子里抽出一个数字m(1<=m<=n)。游戏开始后,代理商按顺时针方向绕

【吉大刘大有数据结构绿皮书】约瑟夫问题:旅游代理商选择了n个顾客来竞争最后的免费环游世界大奖。代理商让顾客们排成一个圆圈,然后从帽子里抽出一个数字m(1<=m<=n)。游戏开始后,代理商按顺时针方向绕,第1张

题目

旅游代理商选择了n个顾客来竞争最后的免费环游世界大奖。代理商让顾客们排成一个圆圈,然后从帽子里抽出一个数字m(1<=m<=n)。游戏开始后,代理商按顺时针方向绕着圆圈踱步,每当他经过第m位顾客时就停下来,请他退出游戏。接着,代理商继续顺时针绕圈。随着时间的过去,最后只剩下一个竞争者,他就是环游世界大奖的赢家。

思路与解答

按照书中的提示,我们需要弄一个双向循环链表,链表中保存竞争者的信息,假设有 n n n个竞争者,我们就要保证有 n − 1 n-1 n1次循环,每次循环时,都要从当前结点(最开始是第一个结点)向下移动指针 m − 1 m-1 m1次( m m m是在1和链表长度直接的随机数),并删除当前结点,假设当前结点是哨位结点,还要绕过哨位结点,避免哨位结点被删除,由于循环是一个圈,所以m超过了当前链表长度也没问题,多顺时针走圈便是了,其C语言代码如下(思路在注释中):

#include 
#include
#include
#include
//顾客结构体
typedef struct Customer
{
    char name[20];//顾客姓名
}Customer;
//模拟面向对象的构造函数
void constructCustomer(Customer* c,char n[20])
{
    strcpy(c, n);
}
//双向循环链表结点结构体
typedef struct DualCircLinkNode {
    Customer data;//数据域
    struct DualCircLinkNode* next;//指向下一个结点的指针
    struct DualCircLinkNode* prior;//指向前一个结点的指针
}DualCircLinkNode;
//双向循环链表
typedef struct DualCircLinkList {
    int len;//链表长度
    struct DualCircLinkNode* head;//哨位结点
}DualCircLinkList;
//初始化双向循环链表
void InitDualCircLinkList(DualCircLinkList* L)
{
    L->len = 0;
    L->head = (DualCircLinkNode*)malloc(sizeof(DualCircLinkNode*));
    if (L->head == NULL)
    {
        printf("内存不足!\n");
        return;
    }
    //最开始是空表,next指针和prior指针都指向哨位结点
    L->head->next = L->head;
    L->head->prior = L->head;
    return;
}
//尾插
void InsertTail(DualCircLinkList* L, Customer elem)
{
    DualCircLinkNode* p = L->head->prior;//获取尾结点
    //双向循环链表尾插较为方便,头结点的prior指针指向的内存空间就是要插入的结点
    DualCircLinkNode* q = (DualCircLinkNode*)malloc(sizeof(DualCircLinkNode));//准备新结点
    if (q == NULL)
    {
        printf("内存不足!\n");
        return;
    }
    q->data = elem;
    L->head->prior = q;//让哨位结点的前一个结点变为q
    q->next = L->head;//要尾插的结点的后继结点变为哨位结点
    p->next = q;//让未插入前的尾结点的后继结点变为q
    q->prior = p;//让q的前驱结点变为未插入前的尾结点
    L->len++;
    return;
}
//删除双向循环链表中的指定结点
void deleteNode(DualCircLinkList* L, DualCircLinkNode* node)
{
    if (L->head->next == L->head->prior)
    {
        printf("链表为空,无法删除!\n");
        return;
    }
    if (node == NULL || node->next == NULL || node->prior == NULL)
    {
        printf("要删除的结点不是标准的双向链表结点!\n");
        return;
    }
    //如果删除的是第一个结点
    if (node == L->head->next)
    {
        L->head->next->next->prior = L->head;
        L->head->next = L->head->next->next;
        return;
    }
    DualCircLinkNode* p = node->prior;//p是要删除结点的前驱结点
    DualCircLinkNode* q = node->next;//q是要删除结点的后继结点
    node->prior->next = node->next;
    node->next->prior = node->prior;
    free(node);
    L->len--;
}
//打印双向循环链表
void printDualCircLinkList(DualCircLinkList* L)
{
    //判空的条件并不是L->head->next == L->head->prior,如果链表中存在一个元素,也会判断为空,画图可以明白
    if (L->head->next == L->head)
    {
        printf("表空!\n");
        return;
    }
    DualCircLinkNode* p = L->head->next;//获取哨位结点后第一个结点
    //遍历打印,循环截止条件是p!=L->head,因为到了哨位结点,相当于又循环了一圈
    while (p != L->head)
    {
        printf("%s   ", p->data.name);
        p = p->next;
    }
    printf("\n");
    return;
}
//反向打印链表
void printRDualCircLinkList(DualCircLinkList* L)
{
    //判空的条件并不是L->head->next == L->head->prior,如果链表中存在一个元素,也会判断为空,画图可以明白
    if (L->head->next == L->head)
    {
        printf("表空!\n");
        return;
    }
    DualCircLinkNode* p = L->head->prior;//获取哨位结点后第一个结点
    //遍历打印,循环截止条件是p!=L->head,因为到了哨位结点,相当于又循环了一圈
    while (p != L->head)
    {
        printf("%s   ", p->data.name);
        p = p->prior;
    }
    printf("\n");
    return;
}
//解决约瑟夫问题,n代表参加比赛的人数
void josephus(int n)
{
    if (n < 0)
    {
        printf("请输入正确的数字!\n");
        return;
    }
    static unsigned int seq = 0;//额外使用定增序号,防止出现随机序列一致
    srand(time(0) + (seq++));//使用srand函数初始化随机数种子
    DualCircLinkList* L = (DualCircLinkList*)malloc(sizeof(DualCircLinkList));
    if (L == NULL)
    {
        printf("内存不足!\n");
        return 0;
    }
    InitDualCircLinkList(L);
    char temp[20] = "";
    Customer c = { "" };
    for (int i = 0; i < n; i++)
    {
        printf("请输入第%d个人的名字:", i + 1);
        scanf("%s", temp);
        strcpy(c.name, temp);
        InsertTail(L, c);
    }
    printf("参与抽奖的名单:");
    printDualCircLinkList(L);
    DualCircLinkNode* p = L->head->next;//获取第一个结点
    if (p == NULL)
    {
        printf("链表为空!\n");
        return;
    }
    //循环,每次随机从剩余的人中抽取一个删除直到还剩下一个(即选取0,L->len的随机数)
    int m = rand() % (L->len - 1) + 1;//获取1-链表长度的随机数,即题中的第m位顾客
    printf("m的值为%d\n", m);
    DualCircLinkNode* curr = L->head->next;//从第一个结点开始
    for (int i = 1; i < n; i++)//因为要抽到还剩一个人,所以需要从1到L->len遍历,遍历n-1次
    {
        //顺时针找一圈,找到第m个(大于链表长度就多转几圈)结点的前驱结点
        //记录当前竞争者是第几位,删除第m位竞争者
        //必须向后移动m-1步 
        for (int j = 1; j <= m-1; j++)
        {
            //移动指针
            curr = curr->next;
            //如果移动到哨位结点,则还需要再向前移动一位,这样避开头结点
            if (curr == L->head)
            {
                curr = curr->next;
            }
        }
        printf("\n");
        printf("第%d轮淘汰了%s\n", i, curr->data.name);
        //让当前指针向前移动一个内存单位(删除后,指针正常应该指向被删除结点后继结点)
        curr = curr->next;
        //删除操作,curr->prior是被删除的结点(如果剩下一个结点就不删除)
        if (L->head->next->next != L->head)
        {
            deleteNode(L, curr->prior);
        }
        //如果删除的表尾结点,则它的下一个结点是哨位结点,避免删除哨位结点,还需要将指针再向下移动一个内存单位
        if (curr == L->head)
        {
            curr = curr->next;
        }
        printf("当前参与者还有:");
        printDualCircLinkList(L);
    }
    printf("获奖者是:");
    printDualCircLinkList(L);
}
int main()
{
    josephus(6);
}
测试结果

为了证明随机数是随机的,弄三组测试结果为证:


欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/2991810.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

随机推荐

  • 二氧化碳灭火器的使用方法

    右手捂住喷嘴,左手执筒底边缘,上下摇晃;在上风源处,拔掉铅封和保险销,对准火源根部,按压灭火器。使用时要尽量防止皮肤因直接接触喷筒和喷射胶管而造成冻伤。扑救电器火灾时, 如果右手捂住喷嘴,左手执筒底边

    2022-09-30
    0 0 0
  • 蟑螂怕香水味道吗

    蟑螂是不怕香水味道的。蟑螂不喜欢刺激性气味,一开始可能会排斥香水味,但过一段时间,等蟑螂适应后,就不怕了,蟑螂只对有毒或有辛辣刺激气味的植物味道特别敏感,只要闻到这些植物的蟑螂是不怕香水味道的。蟑螂不

    2022-09-30
    0 0 0
  • 游泳衣里面需要穿内裤吗

    游泳衣里面不需要穿内裤。泳衣使用高弹性面料制成,内裤不可能比它更贴合身体,如果泳衣内穿内裤会浮现很明显的内裤形状的凸起,诚然不美观。按泳裤的设计,一般会在裆部放置一块软游泳衣里面不需要穿内裤。泳衣使用

    2022-09-30
    0 0 0
  • 水管被水垢堵了怎么办

    方法一:将柠檬酸与水充分混合,然后利用水管清洗机和混合的柠檬酸溶液对堵住的水管进行冲洗;方法二:或者还可以直接更换掉有水垢的水管;方法三:关闭进水口和出水口,倒入些许盐酸,然后方法一:将柠檬酸与水充分

    2022-09-30
    0 0 0
  • 瓜娃子是爱称吗

    瓜娃子是爱称中的一种,但是瓜娃子还可以表示为愚笨,傻等意思。瓜娃子一般指骂人傻瓜,但是对亲近之人如长辈对晚辈,及关系要好的朋友之间是一种爱称。瓜娃子属于地方方言,在四川地瓜娃子是爱称中的一种,但是瓜娃

    2022-09-30
    0 0 0
  • 蛇最怕什么药

    蛇害怕的药有六六六粉(六氯环己烷)、敌敌畏、石灰粉、驱蛇粉等。这些药物会产生强烈的刺激性味道,可以驱蛇。除了药物之外,一些化学类的试剂也是蛇较为害怕的物质,比如酒精、硫蛇害怕的药有六六六粉(六氯环己烷

    2022-09-30
    0 0 0
  • 中元节上午烧纸还是下午烧纸

    中元节一般在下午烧纸。中元节属于我国重要的传统节日之一,也是一个祭祀的节日,传说在这天祖先会回家看望后人,在白天要给祖先供品,表示丰衣足食,待到下午或晚上的时候先人离去,再中元节一般在下午烧纸。中元节

    2022-09-30
    0 0 0
  • 淘宝定位在哪里设置

    相信很多朋友们都玩过微信和高德地图,我们可以通过软件来定位位置分享给朋友们,让他们可以按照我的实时位置来找我,其实淘宝也有定位功能,那么淘宝定位在哪里设置呢?一起来看看吧相信很多朋友们都玩过微信和高德

    2022-09-30
    0 0 0
  • 什么是多彩仿石漆

    多彩仿石漆是艺术涂料中,制作难度非常大的一类涂料,又称为仿石涂料,是用涂料仿石材,仿做天然石材,其效果形象生动,无论是质感,还是色彩都接近天然石材,只是在硬度上略有欠缺,仿石漆包多彩仿石漆是艺术涂料中

    2022-09-30
    0 0 0

发表评论

登录后才能评论

评论列表(0条)

保存