C语言经典例题：猴子选大王

问题：有n只猴子顺序编号，从第一只猴子开始报数，凡是报道m的猴子退出，最终剩下的一只猴子及当选为猴王

输入：n、m

输出：猴王编号

第一种方法：用数组实现：（较为简单省略步骤）

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
        a[i]=1;
    int i=1;
    int j=0;
    int k=0;
    while(k<n-1)
    {
        if(i==3)
        {
            a[j]=0;
            i=1;
            j++;
            k++;
        }
        else
        {
            i++;
            j++;
        }
    }
    for(int g=0;g<n;g++)
    {
        if(a[g]==1)
            printf("%d",g+1);
    }
    return 0;
}

第二种方法：用循环单链表实现：

                    第一步：创建一个循环单链表，注意释放头结点的空间，每个结点包括编号和指针域

                    第二步：从首结点p开始循环报数，循环报数结点到需要删除结点的前一个结点，然后删除这个报数结点后面的结点，并更新报数结点（p=p->pnext）

                    第三部：当p=p->pnext时循环停止，输出剩余的一个结点的编号，即猴王的编号

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct node
{
    int number;//保存编号
    struct node *pnext;
}node,*pnode;
pnode create_list(int len);
void function(pnode p,int baoshu);
int main()
{
    int len;//猴子的数目
    int baoshu;
    printf("请输入猴子的数目:");
    scanf("%d",&len);
    printf("请输入报数的大小:");
    scanf("%d",&baoshu);
    pnode p=null;
    p=create_list(len);
    function(p,baoshu);
}
pnode create_list(int len)
{
    int i;
    pnode phead=(pnode)malloc(sizeof(node));//创建头结点
    if(null==phead)
    {
        printf("动态内存分配失败！");
        exit(-1);
    }
    phead->pnext=null;
    pnode ptail=phead;//创建始终指向尾结点的指针
    for(i=0;i<len;++i)
    {
        pnode p=(pnode)malloc(sizeof(node));
        if(null==p)
        {
            printf("动态内存分配失败！");
            exit(-1);
        }
        p->number=i+1;
        ptail->pnext=p;
        p->pnext=null;
        ptail=p;
    }
    ptail->pnext=phead->pnext;//尾结点指向首结点
    free(phead);
    return ptail->pnext;//返回首结点的地址
}
void function(pnode p,int baoshu)
{
    int i=0;
    int j=0;
    for(p;p!=p->pnext;p=p->pnext)
    {
        i++;
        if(i==baoshu-1)
        {
            j++;
            pnode q=p->pnext;
            p->pnext=q->pnext;
            printf("第%d个退出的猴子编号为：%d\n",j,q->number);
            free(q);
            i=0;
        }
    }
    printf("最终获选的猴子大王编号为：%d\n",p->number);
    return;
}