几个人围成一圈||猴子选大王(约瑟夫环)

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。



一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。


数组方式

#include<stdio.h>
#define N 5 //总人数
#define M 3 //报数最大值(1-M)
#define R 1 //留下的人数
void main()
{
    //声明一个数组代表N个人
    int r[N];
    //游戏开始之前所有的人都还在，所以当前人数为N
    int size = N;
    int remain = R;
    //设定报数起始值
    int count = 1;
    int i,j;
    //给每个人加上编号
    for(i=0; i<N; i++) r[i] = i+1;

    printf("%d个人从1报数，报到%d的出列，求最后剩余的%d个人\n", N, M, R);

    //循环到当前人数为指定的数目的剩余人数时终止
    while(size != remain)
    {
        //对当前剩余人数进行循环报数
        for(i=0; i<size; i++)
        {
            //报数到3，去掉当前这个人，将后面的人全部往前挪一个位置，当前人数减1，并保持这个for循环停留一次(因为后面一个人挪过来了，所以应该再次在这个位置上重新报数)
            if(count == M)
            {
                printf("第%d个人报数%d，%d号选手出列\n", r[i], count, r[i]);

                for(j=i; j<size-1; j++)
                {
                    r[j] = r[j+1];
                }
                i--;
                size--;
                count = 1;
            }
            else
            {
                printf("第%d个人报数%d\n", r[i], count);
                //继续报数
                count++;
            }
        }
    }
    printf("############剩余的%d个选手############\n", remain);
    for(i=0; i<remain; i++)
    {
        printf("第%d个人报数%d\n", r[i], count, r[i]);
    }

}

链表方式

#include<stdio.h>
#define M 10
#define N 3
#define LEN sizeof(struct Node)
struct Node
{
    int data;
    struct Node *next;
};
//创建一个循环链表
struct Node *create()
{
    int i;
    struct Node *head,*p1,*p2;
    //创建一个头节点
    head = p1 = p2 = (struct Node *)malloc(LEN);
    //头节点赋值
    head->data = 1;
    //使用p1,p2的叉开移动继续创建后面的节点  
    //(1)p2指向新节点  (2)p1的next指向p2  (3)p1和p2都指向新节点位置，repeat
    for(i=1; i<M; i++)
    {
        p2 = (struct Node *)malloc(LEN);
        p2->data = i+1;
        p1->next = p2;
        p1 = p2;
    }
    //将最后一个节点的next指向head
    p1->next = head;
    //返回头指针
    return head;
}
//找到待删除的元素的前一个元素的位置(方便后续的删除和重连接操作)
struct Node *find(struct Node *start,int n)
{
    struct Node *find = start;
    int i;
    for(i=0; i<n-2; i++)
    {
        find = find->next;
    }
    return find;
}

//删除find所指的后面的节点，并将find和find的后后面的节点连接起来
struct Node *del(struct Node *find)
{
    //后后面的节点
    struct Node *temp = find->next->next;
    printf("删除了%d\n", find->next->data);
    free(find->next);
    find->next = temp;
    return temp;
}

void main()
{
    //每一次开始报数的位置
    struct Node *startNode = create();
    //每一次报到N要被删除的数的位置
    struct Node *findNode;
    int i;
    //进行M-1次报数后就只剩下随后一个人
    for(i=0; i<M-1; i++)
    {
        //找一个报数为N的所在的位置
        findNode = find(startNode, N);
        //删掉它并返回下一个继续点的位置
        startNode = del(findNode);
    }
    //输出最后一个人的信息
    printf("#####剩下%d\n", startNode->data);
}

为了方面在链表中删除节点，前面的方法查找的节点实际上找的是待删除的节点的前面一个节点，然后删除的时候就通过这个节点指针将后面一个节点删除，这样的做法很简单，但是感觉很奇怪。昨天看了一下《编程之美》，被里面的一种方法吸引了，果断重写，现在咱这个链表中的节点就是直接找到所在的节点，并且直接把这个节点“删”了^_^，不多说，show code~

#include<stdio.h>
#define N 10
#define M 3
struct Node
{
    int data;
    struct Node *next;
};

//创建循环链表(1-10)
struct Node *create()
{
    int i;
    struct Node *head,*p1,*p2;
    head = p1 = p2 = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    for(i=1; i<N; i++)
    {
        p1 = (struct Node*)malloc(sizeof(struct Node));
        p1->data = i+1;
        p2->next = p1;
        p2 = p1;
    }
    p2->next = head;
    return head;
}

//寻找报数为num的数字(报数范围1-num)，返回指向它的指针
struct Node *find(struct Node *start, int num)
{
    struct Node *p = start;
    int i;
    for(i=1; i<num; i++)
    {
        p = p->next;
    }
    return p;
}

//删除p所指向的节点(实际删除的是p后面一个节点)
//基本思想：将p后面一个节点的数据复制到p上，然后让p指向p后后面的节点，然后删掉p后面的节点
//返回的是保存了p后面节点数据的节点
struct Node *del(struct Node *p)
{
    struct Node *pt = p->next;
    p->data = pt->data;
    p->next = pt->next;
    free(pt);
    return p;
}

void main()
{
    int i;
    struct Node *start = create();
    for(i=0; i<N-1; i++)
    {
        start = find(start, M);
        printf("删除%d\n", start->data);
        start = del(start);
    }
    printf("最后剩下%d\n", start->data);
}