1、約瑟夫環公式推導：已知n個人（以編號1，2，3...n分別表示）圍坐在壹張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下壹個人又從1開始報數，數到m的那個人又出列。
依此規律重復下去，直到圓桌周圍的人全部出列。
這個就是約瑟夫環問題的實際場景，有壹種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題采用的是典型的循環鏈表的數據結構，就是將壹個鏈表的尾元素指針指向隊首元素。 p->link=head。
2、解決問題的核心步驟：
1.建立壹個具有n個鏈結點，無頭結點的循環鏈表。
2.確定第1個報數人的位置。
3.不斷地從鏈表中刪除鏈結點，直到鏈表為空。
擴展資料
算法例子
C#
//1、循環鏈表存儲結構 ?
class LinkData
{
public int value { get; set; }//小孩子的ID
public LinkData next { get; set; }//下壹個小孩子的位置
private LinkData(int m_value)
{
value=m_value;
}
//孩子們圍坐壹圈
public static LinkData CreateLink(int []arr)
{
LinkData head = new LinkData(0);
LinkData p = head;
for(int i=0;i<arr.Length-1;i++)
{
p.value = arr[i];
p.next = new LinkData(0);
p = p.next;
}
p.value = arr[arr.Length - 1];
p.next = head;//循環鏈表，尾巴指向頭
return head;
}
//丟手絹算法
public static void Yuesefu(LinkData head, int i, int M)
{
//DateTime dt = DateTime.Now;
//Console.WriteLine("link go:");
LinkData f = head;//頭
LinkData r=f;//尾
for (; i > 0; i--) //進入移動到第壹次丟手絹的位置
{
r = f;
f = f.next;
}
while (r.next != r)//是否剩下最後壹個小孩子
{
for(int j=0;j<M;j++)
{
r=f;
f=f.next;
}
Console.Write(f.value.ToString() + " ");//小孩子報上名來
f = f.next;//踢掉壹個小孩子
r.next = f;
}
Console.WriteLine(r.value.ToString());//小孩子報上名來
//Console.WriteLine(string.Format("耗時{0}毫秒",(DateTime.Now-dt).TotalMilliseconds));
}
}
//2、List<Int>存儲結構
class ListData
{
//丟手絹算法，直接通過在List<Int>集合中定位元素，再移除元素,循環往復，直到集合為空
public static void Yuesefu(List<int> src, int i, int M)
{
int len = src.Count;
i = (i + M) % src.Count;
//Console.WriteLine("list go:");
//DateTime dt = DateTime.Now;
while (src.Count > 1)
{
Console.Write(src[i].ToString() + " ");//小孩子報上名來
src.RemoveAt(i);//踢掉壹個小孩子
i = (i + M) % src.Count;
}
Console.WriteLine(src[i].ToString());//小孩子報上名來
//Console.WriteLine(string.Format("耗時{0}毫秒", (DateTime.Now - dt).TotalMilliseconds));
}
}
參考資料：