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

题目

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

思路与解答

按照书中的提示，我们需要弄一个双向循环链表，链表中保存竞争者的信息，假设有 n n n个竞争者，我们就要保证有 n − 1 n-1 n−1次循环，每次循环时，都要从当前结点（最开始是第一个结点）向下移动指针 m − 1 m-1 m−1次（ 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);
}

测试结果

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