约瑟夫环公式最终(约瑟夫斯环算法)
约瑟夫环的问题
#include stdio.h
int main()
{
int n, m, i, s=0;
printf ("N M = ");
scanf("%d%d", n, m);
for (i=2; i=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
下面是运行结果
N M = 4 3
The winner is 1
约瑟夫环问题的第推公式是怎么来的阿～～
/*约瑟夫问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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个人（以编号1，2，3....n分别表示）围坐在一张圆桌周围。
从编号为k的人开始报数，数到m的那个人出圈；他的下一个人又从1开始报数，数到m的那个人又出圈；依次规律重复下去，直到剩余最后一个胜利者。
例如：有10个人围成一圈进行此游戏，每个人编号为1-10。若规定数到3的人出圈。则游戏过程如下：
(1) 开始报数，第一个数到3的人为3号，则3号出圈
? ? ? ? 1，2，【3】，4，5，6，7，8，9，10
(2) 从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈
? ? ? ? 1，2，【3】，4，5，【6】，7，8，9，10
(3) 从7号重新从1开始计数，则接下来数到3的人为9号，则9号出圈
? ? ? ? 1，2，【3】，4，5，【6】，7，8，【9】，10
(4)? 从10重新从1开始计数，由于10个人称环形结构，则接下来数到3的人为2号，2号出圈
? ? ? ? 1，【2】，【3】，4，5，【6】，7，8，【9】，10
(5) 从4号重新从1开始计数，则接下来数到3的人为7号，7号出圈
? ? ? ? 1，【2】，【3】，4，5，【6】，【7】，8，【9】，10
(6) 从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈
? ? ? ? 【1】，【2】，【3】，4，5，【6】，【7】，8，【9】，10
(7) 从4号重新从1开始计数，则接下来数到3的人为8号，8号出圈
? ? ? ? 【1】，【2】，【3】，4，5，【6】，【7】，【8】，【9】，10
(8) 从10重新从1开始计数，则接下来数到3的人为5号，5号出圈
? ? ? ? 【1】，【2】，【3】，4，【5】，【6】，【7】，【8】，【9】，10
(9) 从10重新从1开始计数，则接下来数到3的人为10，10号出圈
? ? ? ? 【1】，【2】，【3】，4，【5】，【6】，【7】，【8】，【9】，【10】
(10) 最终剩余4号，4号为胜利者
? ? ? ? 用数组求解的基本思想就是用一个数组去标识这n个人的状态，默认全为1，也就是都在圈子内。
? ? ? ? 当数到m的人出圈之后，标识置为0（就是出圈了），同时报数器清0，下一个要从1开始。
? ? ? ? 在每次报数之前要判断他是否在圈子内（也就是他的标识是否为1），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数，出圈? ? ? ? ? ? 的人数等于n-1时，则游戏结束。
约瑟夫环问题的输出结果是多少?
对于n个数字（0,1,2.....n-1）排成一圈，每次删除第m个数字的情况，有递推公式：
则根据这个公式，实现的代码为：
#includeiostream
using?namespace?std;
int?LastRemaining(unsigned?int?n,?unsigned?int?m)
{
????if?(n??1?||?m??1)
????????return?-1;
????int?last?=?0;
????for?(int?i?=?2;?i?=?n;?i++)
????????last?=?(last?+?m)?%?i;
????return?last;
}
int?main()
{
unsigned?int?m,?n;
cin??n??m;
cout??"The?last?remaining?number?is?"??LastRemaining(n,?m)??endl;
return?0;
}
最后的结果为：
约瑟夫环问题 经典求循环公式
提问时 应该把问题说清,不要只帖代码
要中说查错的话:
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
约瑟夫环问题
问题描述：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