約瑟夫環

約瑟夫環（約瑟夫問題）是一個數學的套用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。通常解決這類問題時我們把編號從0~n-1，最後結果+1即為原問題的解。

基本信息

• 中文名：約瑟夫問題
• 英文名：Joseph problem

• 其他命名：約瑟夫環、丟手絹問題
• 學科：數學

概述

約瑟夫環

是一個數學的套用問題：
已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。
這個就是約瑟夫環問題的實際場景，有一種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題採用的是典型的循環鍊表的數據結構，就是將一個鍊表的尾元素指針指向隊首元素。 p->link=head

解決

解決問題的核心步驟：
1.建立一個具有n個鏈結點，無頭結點的循環鍊表
2.確定第1個報數人的位置
3.不斷地從鍊表中刪除鏈結點，直到鍊表為空
void JOSEPHUS(int n,int k,int m) //n為總人數，k為第一個開始報數的人，m為出列者喊到的數
{
/* p為當前結點r為輔助結點，指向p的前驅結點list為頭節點*/
LinkList p,r,list;
/*建立循環鍊表*/
for(int i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p>link=list; /*使鍊表循環起來*/
p=list; /*使p指向頭節點*/
/*把當前指針移動到第一個報數的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循環地刪除佇列結點*/
while(p->link!=p)
{
for(i=0;i<m;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被刪除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最後被刪除的元素是：％4d",P->data);
}