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;
} */ 
    
    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;
}