简单粗暴
什么是约瑟夫循环
举个例子
1 2 3 4
四个人
从头开始报数 报到3 的人 淘汰 然后继续报数 规则依旧
我们来演示一下
开始是1 2 3 4
3 数3 淘汰
（下面顺序会调整）
剩下4 1 2
继续 淘汰 2（应该不用说为什么吧）
还剩 4 1
淘汰4（数到结尾就回到开头继续 是一个圈的形状 ）
还剩下最后的 1
OK 我们现在的问题就是给你一个数 n 现在开始有1到n 假设 判断标准是3 让你来判断 最后剩下的人的序号 （1到n 中的一个 就是一个数 例如上面的1）
当然你可以一个一个去数
那就失去这篇文章的意义了不是吗
所以这里将的是一个好方法
OK 我先来眼熟一遍
最后剩下一个对吧
我们1+3 4 对2取余 得 0 但是结果不能小于1 所以加2 故2
下面2+3 对3取余 得2
最后 2+3 对4取余 的 1
所以最后结果就是1
在来看看我们上面一个一个数的
怎么样 是不是 1
哈哈 牛不牛逼 开玩笑 哈
现在我们来讲讲为什么
我们数 数到三 然后淘汰 一个数 在继续数
例如 1 2 3 4
淘汰3 剩下的顺序是 4 1 2
他们对应对新序号分别是 1 2 3
其实就是 吧他们的序号全部向前移动3位 得到的
就是 他的 新位置
不过这个是圈形的
4-3=1
2-3=-1 -1+4=3
1-3=-2 -1+4=2
故 4 1 2 对应 1 2 3
下面继续往下的解析就不多说了 自己在本子上演算一下就OK
OK 我们言归正传
倒着怎么求
既然他是往前移动3 位 我们就往后移动 三位呗 这样不就找到这个数 在上一轮的对应位置了吗
OK 下面开始
还是 1 2 3 4
最后还剩一个数 对吧 对应位置是1
我们就往回走
一次 1+3=4 4%2=0 必须大于0 0+2=2
位置是2 注意此时长度为2
二次 2+3=5 5%3=2
位置是 2 此时为3
三次 2+3=5 5%4=1
位置是 1 此时 是4
因为我们要求的就是长度是4 的
所以我们可以结束了
即 开始位置是1 的就是最终剩下的哪一个
OK
下面是 代码实现
include
intmain ()
{
int n;//总长度
int max=1;
int m;//标准
scanf(“%d %d”,&n,&m);
int i;
for (i=2;i
max=(max+m)%i;
if (max==0) {
max+=i;
}
}
printf(“%d\n”,max);
return 0;
}
运行结果
ok 今天就到这 有什么不对的地方 烦请予以指正
Original: https://www.cnblogs.com/cndccm/p/12678302.html
Author: Mr小明同学
Title: 约瑟夫循环
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/710778/
转载文章受原作者版权保护。转载请注明原作者出处！