约瑟夫环公式(约瑟夫环公式数学推导)

约瑟夫环问题

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod 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个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

f[1]=0;

f=(f+m) mod i; (i1)

有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

C语言约瑟夫环问题中这个 i = (i + m - 1) %n公式是怎么把3 6 9之类的删掉的

i = (i + m - 1) %n 只是用于循环内部，i的赋值（即用于计算下一个i值）；

请参考下方链接中的解法一

网页链接

约瑟夫环问题 经典求循环公式

提问时 应该把问题说清,不要只帖代码

要中说查错的话:

cout "The winner is No."index".\n";//少了个后引号

while(countM)// 对成功的报数开始计数

{

index=(index+1)%N;//计算要报数的小孩编号 这步谁能帮我分析下？

if (in_circle[index])count++;

}

这个循环的作用就是让还在环中的小孩报数,考虑到报到队尾时必须回到头再重报,所以就有了

index=(index+1)%N;

举例来说:

从队尾index=19回队头index=0

第一圈报数时,第20个小孩(index==19)报count==5然后出圈了//if (in_circle[index])count++;

再持行index=(index+1)%N;时即从队头开始.

第二圈报数时,到第19(index==18)个小孩报数count==1后,

再持行index=(index+1)%N//index==19

if...//不计数

index=(index+1)%N//回到第一个小孩

if....//第一个小孩报count==2

约瑟夫环问题的第推公式是怎么来的阿～～

/*约瑟夫问题的数学方法

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是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个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%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; (i1)

有了这个公式，我们要做的就是从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);

}

/*这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。*/

有n个人围成一圈，顺序排号。凡报到3的人退出圈子，问最后留下的是原来第几号的那位？

这是约瑟夫环的数学解法(迭代法)的公式,我们可以这样理解

把n个人想成标号从0开始到n-1的n个人,报到3的人退出圈子,

那么退出圈子的人在0到n-1的标号为(k+3)%n(其中k为n-1个人时退出圈子的人的标号)

因为有一个人退出了圈子,所以还剩下n-1个人,我们对剩下的人重新从0到n-2编号,

同样有公式(k1+3)%n(其中k1为n-2个人时退出圈子的人的标号)得出n-1个人时退出圈子人的标号,

以此类推直到n等于1时kn-1=0也就是1个人时留下的就是标号为0的人

以此有递推公式f(1)=0,f(i)=(f(i-1)+3)%i f(i)为第i次退出圈子的人

我们用for循环从2个人时开始反推,经过n-1次迭代,去除退出圈子的人,

从而可以得到n个人时最后一个退出的人的标号为几,也就是最后留下的人的标号是几,

因为我们每次标号都是从0开始所以最后退出的人的实际编号=标号+1.

有了上述分析我们就不难得出程序(见图)

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

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;iarr.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;jM;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、ListInt存储结构

class ListData

{

//丢手绢算法，直接通过在ListInt集合中定位元素，再移除元素,循环往复，直到集合为空

public static void Yuesefu(Listint 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));

}

}

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