Josephus约瑟夫环问题的不同实现方法与总结

/************************************************************************/
/*                  Josephus问题——数组实现                          */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>

int Josephus(int times, int number, int id){
    int *a;
    int i, count = 0, t = 0;
    a = (int *)malloc(sizeof(int) * number);

for(i = 0; i < number; i++)
        a[i] = i + 1;            // 数组a用于储存每个元素的编号
    i = id - 1;

while(count < number - 1){
        if(a[i] != 0)
            t++;
        if(t == times){
            t = 0;
            count++;
            printf("%4d", a[i]);
            a[i] = 0;                // 当该元素被剔除时，该数组元素置为0
        }
        i++;
        if(i == number)
            i = 0;
    }
    for(i=0;i<number;i++)
        if(a[i]!=0)
        {
            printf("\n最后剩余的结点是:%4d\n",a[i]);
            return;
        }

}

int main(){
    int times, number, id;
    printf("请输入总人数：");
    scanf("%d", &number);
    printf("请输入报数周期:");
    scanf("%d", &times);
    printf("请输入开始报数的编号：");
    scanf("%d", &id);
    Josephus(times, number, id);

return 0;
}

/************************************************************************/
/* 总结：
        优点为可以得出每次被剔除的元素编号
        缺点为内存空间占用较大，没有数学归纳法快速                        */
/************************************************************************/

/************************************************************************/
/*                  Josephus问题——循环链表实现                      */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*Linkhead;
void Josephus(int m,int n,int k)
{
    Linkhead p,r,head = NULL;
    int i;
    for(i = 1;i <= n;i++)
    {
        p = (Linkhead)malloc(sizeof(LNode));//申请一个新的链结点
        p->data = i;//存放第i个结点的编号
        if(head == NULL)
            head = p;
        else
            r->next = p;      // 因为Insert和Del操作都需要之前一个节点的地址，故用r来存储。其作用类似栈的top
        r = p;
    }
    p->next = head;//至此，建立一个循环链表

p = head;
    for(i = 1;i < k;i++)
    {
        r=p;
        /*请注意，此行不是多余的，因为当k!=1,但m=1时如果没有这条语句，此时删除动作无法完成*/
        p=p->next;
    }        //此时p指向第1个出发结点

while(p->next != p)
    {
        for(i = 1;i < m;i++)
        {
            r = p;
            p = p->next;
        }                        //p指向第m个结点,r指向第m-1个结点
        r->next = p->next;        //删除第m个结点
        printf("%4d",p->data);    //依次输出删除结点的编号
        free(p);                //释放被删除结点的空间
        p = r->next;            //p指向新的出发结点
    }
    printf("\n最后剩余的结点是:%4d\n",p->data);//输出最后一个结点的编号
}