????????約瑟夫環問題由古羅馬史學家約瑟夫（Josephus）提出，他參加并記錄了公元66—70年猶太人反抗羅馬的起義。在城市淪陷之后，他和40名死硬的將士在附近的一個洞穴中避難。起義者表示“寧為玉碎不為瓦全”，約瑟夫則想“留得青山在不愁沒柴燒”。于是，約瑟夫建議41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。問：約瑟夫及其朋友應該站在哪個位置?、

????????n個人圍成一個圓圈，然后從第一個人開始，按：1,2,3,…,m報數，數到m的人出圈，并有出圈者的下一個人重新開始報數，數到m又要出圈，如此類推，直到所有人都出圈，打印出圈的次序，其中n和m為輸入數據

????????這個問題可以通過數學推理和遞歸算法來解決。通過不斷地計算，可以發現每次移除一個人后，剩下的人重新排列成一個新的圓圈，規模減小并且從下一個人開始。通過不斷地遞歸計算，可以找到最后一個人的位置。

? ? ? ? 本篇博客用C語言，利用循環單鏈表求解約瑟夫環問題。

? ? ? ? 引用的頭文件

#include<stdio.h>
#include<malloc.h>
#include<time.h>//計算執行時間 

????????在main函數中，首先輸入總人數count和報數規律num，然后調用Solve_lijie函數求解約瑟夫環問題。為了計算程序執行時間，使用了clock函數來記錄開始和結束時刻，然后計算差值得到執行時間。

int main()
{int count, num;double duration; Loop* L;printf("輸入總人數count和報數規律num：");scanf("%d%*c%d", &count, &num);//循環單鏈表求解clock_t start, finish;//長整型數 start = clock();Solve(L, count, num);finish = clock();//記錄前后時刻 duration = (double)(finish - start) / CLOCKS_PER_SEC;//這個是有定義的宏 printf("\n使用循環單鏈表存儲所用執行時間：%lf", duration);return 0; } 

結構體定義

typedef int ElemType;
typedef struct Josephus
{ElemType MEN;	struct Josephus* next;
}Loop;

// 循環單鏈表初始化
void Init(Loop* &L)
{L = (Loop *)malloc(sizeof(Loop));L -> next = L;	// 頭尾相連 
}void Create(Loop* &L, int count)
{if(count < 1){printf("介個是個空環\n");return;}Loop *s, *r;Init(L); //初始化頭節點 L->MEN = 1; r = L;	//指向頭節點 for(int i = 2; i <= count; i++){	//對頭節點后面的節點進行初始化并錄入數據 Init(s);s->MEN = i;s->next = L;//循環，尾部也是L r->next = s;//r指向頭節點 r = s;}
}void Display(Loop* &L)//用于檢測是否正常錄入數據 
{Loop *p = L;if(L == NULL)return;	printf("報數：\n");do{printf("%d\t", p->MEN);p = p->next;}while(p != L);//兜兜轉轉回到原點 printf("\n");return; 
}
void Solve(Loop* &L, int count, int num)
{Create(L, count);Display(L);int j;//循環，根據報數規律num讓成員出列，受總人數count影響//每殺一個，count--; 每到第num個，就打印后free一個 Loop *p, *r;r=p = L;while(r->next != L)r = r->next;for(int i = count; i > 1; i--){j = 1;do{		r = p;	//形成一前一后兩指針 p = p->next;j++;}while(j < num);// 不符合出列條件。此時兩指針各下移一個單位r->next = p->next;printf("這個人死了: %d\n", p->MEN);free(p);p = r->next;//符合條件。此時后指針后續鏈接前指針的后續，釋放前指針p，然后恢復前后位置順序。}printf("獲勝者是%d\n", p->MEN);
}