十、 約瑟夫問題

據(jù)說著名猶太歷史學(xué)家 Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。
然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

• 代碼：

//n個人圍圈報數(shù)，報m出列，最后剩下的是幾號？
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}node;
node *create(int n)
{
    node *p = NULL, *head;
    head = (node*)malloc(sizeof (node ));
    p = head;
    node *s;
    int i = 1;
    if( 0 != n )
    {
        while( i <= n )
        {
            s = (node *)malloc(sizeof (node));
            s->data = i++;    // 為循環(huán)鏈表初始化，第一個結(jié)點(diǎn)為1，第二個結(jié)點(diǎn)為2。
            p->next = s;
            p = s;
        }
        s->next = head->next;
    }
    free(head);
    return s->next ;
}
int main()
{
    int n = 41;
    int m = 3;
    int i;
    node *p = create(n);
    node *temp;
    m %= n;   // m在這里是等于2
    while (p != p->next )
    {
        for (i = 1; i < m-1; i++)
        {
            p = p->next ;
        }
        printf("%d->", p->next->data );
        temp = p->next ;                //刪除第m個節(jié)點(diǎn)
        p->next = temp->next ;
        free(temp);
        p = p->next ;
    }
    printf("%d\n", p->data );
    return 0;
}

作業(yè)：編號為1～N的N個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)，可以自由輸入），開始人選一個正整數(shù)作為報數(shù)上限值M，從第一個人按順時針方向自1開始順序報數(shù)，報道M時停止報數(shù)。報M的人出列，將他的密碼作為新的M值，從他順時針方向上的下一個人開始從1報數(shù)，如此下去，直至所有人全部出列為止。

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUM 100
#define TRUE 1U
#define FALSE 0U

typedef struct NodeType
{
    int id;
    int cipher;
    struct NodeType *next;
} NodeType;

/* 創(chuàng)建單向循環(huán)鏈表 */
static void CreaList(NodeType **, const int);
/* 運(yùn)行"約瑟夫環(huán)"問題 */
static void StatGame(NodeType **, int);
/* 打印循環(huán)鏈表 */
static void PrntList(const NodeType *);
/* 得到一個結(jié)點(diǎn) */
static NodeType *GetNode(const int, const int);
/* 測試鏈表是否為空, 空為TRUE，非空為FALSE */
static unsigned EmptyList(const NodeType *);

int main(void)
{
    int n, m;
    NodeType *pHead = NULL;
    while (1)
    {
        printf("請輸入人數(shù)n（最多%d個）: ", MAX_NODE_NUM);
        scanf("%d", &n);
        printf("和初始密碼m: ");
        scanf("%d", &m);
        if (n > MAX_NODE_NUM)
        {
            printf("人數(shù)太多，請重新輸入！\n");
            continue;
        }
        else
            break;
    }
    CreaList(&pHead, n);
    printf("\n------------ 循環(huán)鏈表原始打印 -------------\n");
    PrntList(pHead);
    printf("\n-------------刪除出隊(duì)情況打印 -------------\n");
    StatGame(&pHead, m);
}

static void CreaList(NodeType **ppHead, const int n)
{
    int i, iCipher;
    NodeType *pNew, *pCur;
    for (i = 1; i <= n; i++)
    {
        printf("輸入第%d個人的密碼: ", i);
        scanf("%d", &iCipher);
        pNew = GetNode(i, iCipher);
        if (*ppHead == NULL)
        {
            *ppHead = pCur = pNew;
            pCur->next = *ppHead;
        }
        else
        {
            pNew->next = pCur->next;
            pCur->next = pNew;
            pCur = pNew;
        }
    }
    printf("完成單向循環(huán)鏈表的創(chuàng)建!\n");
}

static void StatGame(NodeType **ppHead, int iCipher)
{
    int iCounter, iFlag = 1;
    NodeType *pPrv, *pCur, *pDel;
    pPrv = pCur = *ppHead;
    /* 將pPrv初始為指向尾結(jié)點(diǎn)，為刪除作好準(zhǔn)備 */
    while (pPrv->next != *ppHead)
        pPrv = pPrv->next;
    while (iFlag)
    {
        for (iCounter = 1; iCounter < iCipher; iCounter++)
        {
            pPrv = pCur;
            pCur = pCur->next;
        }
        if (pPrv == pCur)
            iFlag = 0;
        pDel = pCur; /* 刪除pCur指向的結(jié)點(diǎn)，即有人出列 */
        pPrv->next = pCur->next;
        pCur = pCur->next;
        iCipher = pDel->cipher;
        printf("第%d個人出列, 密碼: %d\n", pDel->id, pDel->cipher);
        free(pDel);
    }
    *ppHead = NULL;
    getchar();
}

static void PrntList(const NodeType *pHead)
{
    const NodeType *pCur = pHead;
    if (EmptyList(pHead))
        return;
    do
    {
        printf("第%d個人, 密碼: %d\n", pCur->id, pCur->cipher);
        pCur = pCur->next;
    }
    while (pCur != pHead);
    getchar();
}

static NodeType *GetNode(const int iId, const int iCipher)
{
    NodeType *pNew;
    pNew = (NodeType *)malloc(sizeof(NodeType));
    if(!pNew)
    {
        printf("Error, the memory is not enough!\n");
        exit(-1);
    }
    pNew->id = iId;
    pNew->cipher = iCipher;
    pNew->next = NULL;
    return pNew;
}

static unsigned EmptyList(const NodeType *pHead)
{
    if(!pHead)
    {
        printf("The list is empty!\n");
        return TRUE;
    }
    return FALSE;
}