约瑟夫环公式是怎样推导出来的？
有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));
}
}
参考资料：百度百科——约瑟夫环
知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在将编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去刚好就是n个人情况的解。
若想知道知道(n-1)个人报数的问题的解，只要知道(n-2)个人的解即可。关于(n-2)个人的解，当然是先求(n-3)的情况。因此这是一个递推问题。
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序如下
#include <stdio.h>
main()
{
int n, m, i, s=0;
printf("N="); scanf("%d", &n);
printf("M="); scanf("%d", &m);
for(i=2; i<=n; i++) s=(s+m)%i;
printf("The winner is %d\n", s+1);
}
扩展资料：
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数。
数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1， 结果+1即为原问题的解。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head。
2.
解决问题的核心步骤：
1.建立一个具有n个链结点，无头结点的循环链表。
2.确定第1个报数人的位置。
3.不断地从链表中删除链结点，直到链表为空。