约瑟夫问题

约瑟夫问题简述

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。

代码实现

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

typedef struct node
{
    int local;
    struct node * next;
}LNode,*LinkList;

void CreateLinkList_L(LinkList L,int n);
void Josephus(LinkList L,int n,int m,int k);

void main()
{
    //创建循环单链表 结点个数是 n
    //报数 报到m的出去  也就是 删除该结点
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->local = 1;
    CreateLinkList_L(L,10);
    Josephus(L,10,4,3);
}

void CreateLinkList_L(LinkList L,int n)
{
    int i;
    LinkList s,r;
    r = L;

    for(i = 2;i <= n;i++)
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->local = i;
        r->next = s;
        r = r->next;
    }
    r->next = L;
}

void Josephus(LinkList L,int n,int m,int k) //m = 3 , k = 2
{
    int i = 1,j = 1;

    LinkList p,q,s;
    p = L;
    //确定第一个喊话的同学
    while(i < k)
    {
        q = p;
        p = p->next;
        i++;
    }
    while(p->next != p)
    {

        //一个循环用来喊话，一直喊m次
        while(j < m)
        {
            q = p;
            p = p->next;
            j++;
        }
        s = p;
        p = p->next;
        q->next = p;
        printf("%d号淘汰！\n",s->local);
        free(s);
        j = 1;
    }

    printf("%d胜出！",p->local);
}