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