約瑟夫問題 C語言鏈表實現

1.首先，我們先來瞭解一下什麼是約瑟夫環問題：

講一個比較有意思的故事：約瑟夫是猶太軍隊的一個將軍，在反抗羅馬的起義中，他所率領的軍隊被擊潰，只剩下殘餘的部隊40餘人，他們都是寧死不屈的人，所以不願投降做叛徒。一群人表決說要死，所以用一種策略來先後殺死所有人。 
於是約瑟夫建議：每次由其他兩人一起殺死一個人，而被殺的人的先後順序是由抽簽決定的，約瑟夫有預謀地抽到了最後一簽，在殺了除了他和剩餘那個人之外的最後一人，他勸服了另外一個沒死的人投降了羅馬。

通俗來說就是：

按照如下規則去殺人：

• 所有人圍成一圈
• 順時針報數，每次報到3的人將被殺掉
• 被殺掉的人將從房間內被移走
• 然後從被殺掉的下一個人重新報數，繼續報3，再清除，直到剩餘一人

那麼程式實現為：

　　鏈表的定義： 定義為編號即可 所以data項為int

typedef struct NODE{
    struct NODE *next;
    int data;
}Node,*Linklist;

由於是迴圈，直到最後一個人， 所有可以使用特殊的鏈表： 迴圈鏈表。 當鏈表中只剩下一個元素後，便認為完事了。 即 L->next = L;

#include <stdio.h>
#include <stdlib.h>
#include "Linklist.h"

void Print_Linklist(Linklist L)
{
    Linklist head = L;
    printf("List: ");
    while(L->next != head)
    {
        printf("%d ",L->data);
        L = L->next;
    }
    printf("%d ",L->data);
    printf("\n");
}

int main()
{
    int i;
    Linklist L;
    Linklist head;
    Linklist Out;
    L = (Node*)malloc(sizeof(Node));
    head = L;
    L->data = 1;
    L->next = head;
    for(i=2;i<=41;i++)
    {
        L->next=(Node*)malloc(sizeof(Node));
        L->next->data = i;
        L->next->next = head;
        L = L->next;
    }
    Print_Linklist(head);
    L = head;
    while(L != L->next)
    {
         for(i=1;i<2;i++)
         {
             L = L->next;
         }
         Out = L->next;
         printf("%2d號 ----> 自殺！\n",Out->data);
         L ->next = Out->next;
         L = L->next;
         free(Out);
    }
    printf("幸存者是：%d",L->data);
    return 0;
}