C语言约瑟夫（Joseph）问题

时间：10-08来源：作者：点击数：90

六一儿童节到了，学校给桐桐班级（总共 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;
}