约瑟夫环问题
问题：
约瑟夫环问题递推公式：
将约瑟夫环中的每个人看作数组的元素，f为幸存者的下标
先考虑从编号为1的开始报数的情况，f为N,M的函数。设报到M的人出队，总人数为N
递推公式为：
推导过程：
约瑟夫环问题的进行过程可看成数组的移动，以N=11，M=3为例：
进行过程为：
从上图可看出，约瑟夫环问题进行的过程为数组的循环移动，在每次删除元素的过程中，数组中的元素循环左移M位。从下往上看即为循环右移M位，对于移出的情况，取模即可。
f的初始值为f(1,3)=0
对于从编号为k的人开始报数的情况,相当于最开始就把数组元素左移了k-1位，输出结果时右移k-1位还原即可
代码：
#include<stdio.h>
int main()
{
int n;
int k;
int m;
int i;
int f;
scanf( "%d %d %d\n",&n,&k,&m );
int array[n];
for( i=0;i<n;i++ )
array[i]=i+1;
f=0;
for( i=2;i<=n;i++ )
f=( f+m )%i;
printf( "%d\n",array[ (k+f-1)%n ] );
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153879.html
