约瑟夫问题公式,1-12按顺时针方向排圈

约瑟夫问题公式,1-12按顺时针方向排圈详细介绍

本文目录一览： 我想问一下约瑟夫问题的递推公式为什么是 s = (s + m) % i;谢谢

怎么理解呢？让我们来看一看
首先上题目，有n个人围成一圈，报数从1到m依次循环报数，报到m的就退出（死）。
现在我们来看递推，由于为了方便表示（s+m）%i=0的情况，我们让第一人的编号为0,（从一开始也可以）。
既然你问递推，那步骤就不说了，只说这个公式吧
让获胜者的编号为0（最后一个人只有他了当然是0）f(i)表示获胜者在剩下i个人时的那一局的编号
则f(1)=0
f(i)=[f(i-1)+m]%i.
这里我们可以这样理解
如果获胜者在这一局游戏中编号为k（从0开始编号），而每一局中会大声喊出他的编号的人是m个（注意喊得数字从0开始，则喊m-1的人死，但这个人是第m个人），而第m个人又是获胜者的前面第k+1个人，那么如果上一轮的游戏的人数足够（叫了m次还没有人重复叫），则获胜者在上一局的编号是[(m-1)+(k+1)]=m+k(m-1代表死的那个人的编号，而k+1代表死的那个人的后面第n个人的编号)，即在上一局中他是第m+k+1个人。
但是，为什么药%i，因为如果在上一局中，人数不够m-1个，那么是不是就会有的人重复报了两次甚至更多次数！！！！那么，就可以看成数学上的一个周期问题，那么%i，假设为倒数第二句，i=2
那么，i是不是就起了一个限定编号的作用呢，即可以得到的编号只有0和1（余数只有这两个），那么，又知道m+k为有足够人时的时候获胜者的编号，则（k+m）%i不就是把他的编号变成以0~i-1的周期轮换运动吗，即设k+m=3；i=2。 把 0 1 2 3 中的不能得到的2 3变成 0 1 则为 0101来表示吗
那么是不是就是获胜者在这一局当中的编号呢！
那么获胜者不就是第s+1个人吗！
楼主好，我也是昨天正好写到这个题的，看到你的问题于是把自己的感悟写了下来（可能不太好，不知道楼主能看得懂不，我也是第一次写这个题所以写的不好别怪我哈，楼主可以试一试不从0开始的从1开始计数的方法，应该会便于理解一些，刚才写的时候想的）
俺的实力就只有这些啦， 希望楼主采纳一下哦，有什么疑问可以追问 我们可以继续讨论下
顺便补充个东西给你

约瑟夫问题的一般形式

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。分析：（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。（2）开始时每个人都是活的，所以数组初值全部赋为false。（3）模拟杀人过程，直到所有人都被杀死为止。pascal代码var a:array [1..20] of integer;n,m,i,j,k,n1,m1:integer;beginreadln(m,n);for i:=1 to m doa[i]:=i;m1:=m;n1:=1;while m1>0 dobeginj:=(n+n1-1-1) mod m1 +1;n1:=j;m1:=m1-1;writeln(a[j]);for k:=j to m1 doa[k]:=a[k+1];end;end.C++代码： #include

usingnamespacestd;main(){bool a[101]={0};intn,m,i,f=0,t=0,s=0;cin>>n>>m;do{++t;//逐个枚举圈中的所有位置if(t>n)t=1;//数组模拟环状，最后一个与第一个相连if(!a[t])s++;//第t个位置上有人则报数if(s==m)//当前报的数是m{s=0;//计数器清零cout<
<t<
0k+1 --> 1k+2 --> 2......k-2 --> n-2变换后就完完全全成为了（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; (i>1）有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f，程序也是异常简单：c++ #include

using namespace std;const int m = 3;int main(){ int n, f = 0; cin >> n; for (int i = 1; i <= n; i++) f = (f + m) % i; cout << f + 1 << endl;}pascal var n,m,i,s:integer;beginwrite('N M =');read(n,m);for i:=2 to n dos:=(s+m) mod i;writeln('The winner is ',s+1）;end.这个算法的时间复杂度为O(n），相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。约瑟夫问题10e100版（from vijios)描述 Descriptionn个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。输入格式 Input Format一个正整数n，表示人的个数。输入数据保证数字n不超过100位。输出格式 Output Format一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。样例输入 Sample Input9样例输出 Sample Output3时间限制 Time Limitation各个测试点1s注释 Hint样例说明当n=9时，退出圈子的人的编号依次为：2 4 6 8 1 5 9 7最后剩下的人编号为3初见这道题，可能会想到模拟。可是数据实在太大啦！！我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...这样就好弄了！！大体思路如下：①read(a)②b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}③while c

</t<