【算法】约瑟夫环原理及其公式
问题描述
将n个人围成一个圈，从1开始依次数数，数到k或者k的倍数时，这个人出局，如此循环直到环中只剩一个人的时候这个人获胜
算法原理
可以把这个圈想想成一条直线，假设一开始有11人，k=3
将这11个人从1到11进行编号
从1开始报数，此时的人数是11
第一个被淘汰出局的是3
注意，这里淘汰到三继续往后数的话，就相当于4是第一个人，再从1开始计数，此时的人数为10
可以看出11个人从1开始报数，可以等效为10个人从4开始报数，不过少一个3号，但是我们找的是对应的下标，而不是具体的人，所以并没有什么影响
数次循环往复，相当于每淘汰一个人，数组整体向前移动k位（此处k=3，所以是移动三位），因为是整体移动，说明最后获胜的人也是向前移动k位，当已知11个人k=3时最终获胜的人的标号为6（数组中的下标为5）时，易推出10个人k=3时最终获胜的人为(6-3)%10（当前的人数）
可以推出，每增加一个人后，数组整体向后移动k位，这样n就可以从1开始通过递归推出
每当淘汰一个人，数组整体向前移动k位
每当增加一个人，数组整体向后移动k位
公式为
f(n,k)=(f(n-1,k)+k)%n 求出的是下标位置，而不是这个人的编号，如果是编号的话还需要加1
（下标是从0开始的，编号是从1开始的）
当n=1时，代表只有一个人，获胜者就是这个人，他的编号是1，但是下标位置为0
当n=2时，f(1,k)=0,f(2,k)=k%n；
...
依次类推即可求出f(n,k);
最后结果要+1，因为求出来的结果是下标位置，而不是这个人的编号
核心代码实现
int cir(int n,int k)
{
int p=0;
for(int i=2;i<=n;i++) //因为i==1开始的时候就是p=0，所以直接让p=0，跳过第一个
{
p=(p+k)%i;
}
return p+1; //返回的是下标位置，+1才是人的编号
}
例题
