约瑟夫问题

转载请注明来源chengyaogen.blog.chinaunix.net

 

设编号分别为:1,2,...,n的n个人围坐一圈。约定序号为k(1 <= k < = n)的人从1开始计数，数到m的那个人出列，他的下一位又从1开始计数，数到m的那个人又出列，依次类推，直到所有人出列为止。

设n=8,k=3,m=4时，如图所示:

 

出列为:6,2,7,4,3,5,1,8

算法思路:用一个不带头结点的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后从第k结点起从1计数，计到m时，对应结点从链表中删除；然后再从被删除结点的下一个结点起又从1开始计数....,直到所有结点都列出时算法结束。

代码如下:

#include <stdio.h>
#include <stdlib.h>

typedef struct _node_
{
    int data;
    struct _node_ *next;

}ListNode;

ListNode* get_node(int data)
{
    ListNode *temp;

    temp = (ListNode *)malloc(sizeof(ListNode));
    temp->data = data;

    return temp;
}

int insert_data(ListNode **p,ListNode *q)
{
    static ListNode *head;

    if(*p == NULL)
    {
        *p = q;
        head = q;

    }else{

        (*p)->next = q;
        q->next = head;
        //改变移动指针
        *p = q;
    }

    return 0;
}

ListNode *create_loop(int m)
{
    int i = 0;
    ListNode *temp = NULL;
    ListNode *pmove = NULL;

    for(i = 1;i <= m;i ++)
    {
        temp = get_node(i);
        insert_data(&pmove,temp);
    }

    return pmove;
}

int delete_data(ListNode **p,ListNode *q)
{
    (*p)->next = q->next;
    free(q);
    q = NULL;

    return 0;
}

int main()
{
    ListNode *p,*q,*temp;
    int i = 0;
    int n,k,m;

    printf("input n k m:");
    scanf("%d%d%d",&n,&k,&m);
    while(getchar()!= '\n');

    //创建约瑟夫环
    p= create_loop(n);

    //第一个人的位置
    q = p->next;

    //找到地k个人
    for(i = 1;i < k;i ++)
    {
        p = p->next;
        q = q->next;
    }

    while(q != p)
    {
        for(i = 1;i < m;i ++)
        {
            p = p->next;
            q = q->next;
        }

        printf("%d ",q->data);
        delete_data(&p,q);
        q = p->next;
    }

    printf("%d\n",p->data);

    return 0;
}

运行结果：