C语言约瑟夫(Joseph)问题

六一儿童节到了,学校给桐桐班级(总共 30 人)分配了 15 个草莓蛋糕和 15 个冰激凌。为了公平起见,老师将 30 位同学围成一个圈,从第一个人开始依次报数,数到 9 的人出列并给他一个冰激凌;他的下一个人再从 1 开始报数,同样数到 9 的人出列并给他一个冰激凌;依此规律重复下去,直到还剩 15 个人为止。剩下的 15 个人每人给一个草莓蛋糕。

该问题中说“将 30 位同学围成一个圈”,因而可以构造一个单链环来表示。

30 位同学分别用编号 1~30 表示。声明一个结构体类型来构造单链环,链表中的每个结点都有两个成员,其中数值域存放同学的编号,指针域则指向其下一位同学。数值域存放 30 的结点的指针域指向头指针(即数值域存放 1 的结点),这样就构成了一个完整的单链环。
struct node{
    int num;           //存放同学编号
    struct node *next; //指向下一位同学
} *head;

设置两个计数器 i 和 left,left 表示链表中的结点数。从 head 结点开始遍历链表,每遍历一个结点i的值增加 1,到第 9 个结点时输出该结点数值域中的编号,并将其从链表中删除,left 减小 1;之后,计数器 i 归 0,继续从下一个结点开始遍历链表……直到 left 的值为 15(即还剩余 15 个结点)为止。

已经输出的 15 个编号的同学就是得到冰激凌的同学。最后再输出剩余链表中的 15 个编号,这 15 个编号的同学就是得到草莓蛋糕的同学。

代码清单 1:约瑟夫问题
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
    int num;
    struct node *next;
};
struct node *head,*p,*q;
int main( )
{
    int i,j,left;
    head = malloc(sizeof(struct node));
    head -> num = 1;    //建立初始的链环
    head -> next = head;
    q = head;
    for(i=2;i<=30;i++)    //以 i 作为数值域建立结点,并接入链环
    {    
        p = malloc(sizeof(struct node));
        p -> num = i;
        q -> next = p;
        p -> next = head;
        q = p;
    }
    q = head;      //出列操作
    left = 30;
    do {    //重复报数出列
        i = 1;    // i 作为报数器
        while (i < 9){    //循环报数,报 m 的出列
            p = q;
            i = i+1;
            q = q->next;
        }
        printf("%2d ",q->num);   //输出出列人的编号
        left = left-1;    //圈内剩余人数
        p->next = q->next;
        free(q);     //释放该结点
        q = p -> next;
    } while (left > 15);   //直到圈里还剩15人,结束操作
    printf("\n");
    for(i=1;i<=15;i++){
        printf("%2d ",q->num);
        q = q -> next;
    }
    system("pause");
    return 0;
}

运行结果为:

 9 18 27  6 16 26  7 19 30 12 24  8 22  5 23
25 28 29  1  2  3  4 10 11 13 14 15 17 20 21