约瑟夫环公式是怎样推导出来的？

有n个人，编号从0开始，数到m-1退出，网上很多说的公式为： f(1) = 0; f(i) = (f(i-1)+m)%i; 那如果n个人，编号从1开始，数到m退出，公式是什么样子的呢？ 求：详细说明。。。

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));

}

}

参考资料：百度百科——约瑟夫环