约瑟夫问题
今天力扣周赛刚好涉及到了这个知识点，于是顺手记录一下~
问题描述：问题描述：编号为 1-n 的 n 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后
的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。
方法一、暴力模拟
int main(){
int n,m;
cin >> n >> m;
int cnt = 0 ,dead = 0 , i = 0;
while(dead <= n){
i++;
if(i > n) i = 1; //当计数超过n时，需要回到1
if(!vis[i]) cnt ++; //报数是只有没有出列的人才能报数
if(cnt == m) { //报数时报到m的人需要出列
cnt = 0; //下一轮需要从0开始报数
dead ++; //出列的人个数
vis[i] = 1; //标记其已经出列
if(dead == n) //当第n个人出列时，它就是安全的
cout << i ;
}
}
return 0;
}方法二、模拟链表
思路：学过链表的人，估计都会用链表来处理约瑟夫环问题，用链表来处理其实和上面处理的思路差不多，只是用链表来处理的时候，对于被选中的编号，不再是做标记，而是直接移除，因为从链表移除一个元素的时间复杂度很低，为 O(1)。当然，上面数组的方法你也可以采用移除的方式，不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下：
struct ha{
int num;
int next;
};
ha a[1000]; //用数组模拟链表，其实直接用指针也可以
int main(){
int n,m,live,count = 0,cur,pre;
cin >> n >> m;
for(int i = 1;i< n; i++){
a[i].num = i;
a[i].next = i+1; //当前节点下一个指向的位置
}
a[n].num = n, a[n].next = 1;
live= n;
cur = 1;
pre = n;
while(live> 1){
count ++;
if(count == m){
a[pre].next = a[cur].next;
live-- ;
count = 0;
}
else{
pre = cur;
}
cur = a[cur].next;
}
cout << a[cur].num << endl;
return 0;
}方法三、数学方法（原理就是递归）
先是n个人玩这个游戏，编号从0->n-1编号，数m退出，当第一个m-1号人退出后，就变成了n-1个人玩这个游戏了，将这n-1个人重新编号，如下图，会发现是由原来的编号 - m得到这重新编的号。那么这时问题变成了n-1个人玩这个游戏了，机智的你会发现问题没变，只是问题规模变了，这是不是有点递归的味道。
那么想想递归式，设f(n)表示n个人数m退出时问题的解，那么f(n-1)是n-1个人数m退出时问题的解，假设f(n-1)已求出，那么：
f( n ) = f(n - 1) + m;
因为考虑到如图中红色字样的编号为 n-m、n-m+1、n-m+2…加过m之后会超出n,那么需要将等式更改为：
f( n ) = (f(n - 1) + m)%n;
那么,当得知f(n-2)的解时，反推至f(n-1)时，需要编号不超过n-1,因此等式为：
f（n-1）=(f(n-2) + m) % n-1;
那么推广到一般：
f( i ) = (f (i - 1) + m )% i;
那么递归的边界是什么呢，想想当只有一个人玩的时候f(1)= 1;那么程序便可以用递归写了，当然，也可以反之从已知的1推出未知的n的解。
//数学方法
int ha(int n,int m){
int f = 0;
for(int i = 2; i <= n; ++i){
f = (f + m)%i; //即f( i ) = (f (i - 1) + m )% i;
}
return f;
}
//补充一种递归解法
int f(int n, int m){
if(n == 1) return 0;
return (f(n - 1, m) + m) % n ;
}反约瑟夫问题
所谓反约瑟夫，就是通过n和其他信息来求报的数m。
一、经典反~
问题描述：著名的约瑟夫问题是这样描述的：N个人排成一个圆圈，然后把这N个人按逆时针方向编号为1、2、…、N；随机产生一个正整数M，然后从编号为1的人开始按逆时针计数，当某人计数为M的倍数时，该人出队；如此循环下去，直到队列里只有一个人留下。你现在的任务是：对于输入文件的N和K，其中N为初始时约瑟夫圆圈中的人数，K为约瑟夫问题中最后留下的人的编号；请你确定一个最小能发生这种结果的正整数M。
Input
为N和K，0＜N≤1000
Output
为最小的正整数M
#include<bits/stdc++.h>
using namespace std;
int n, k;
int num[1005];
bool check(int m)
{
for(int i = 2; i <= n; i++)
num[i] = (num[i - 1] + m) % i;//O(n)的递推，这里是不可能爆的
if(num[n] + 1 == k) return true;//毕竟是从0开始编号，所以要+1
return false;
}
int main()
{
cin>>n>>k;
if(k == n) cout<<1; //当然可以直接处理！！！
else
{
for(int i = 1; ; i++)//不能设上界，不然就WA了
{
if(check(i))
{
cout<<i;
return 0;
}
}
}
}二、好人与坏人
问题描述：原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人
Input
只有一行就是k,0 < k < 14
Output
只有一行就是m
其实也就是在之前的经典反上加了一个条件——在n>k时，出圈的人的编号全部 > k。
#include<bits/stdc++.h>
using namespace std;
int k, res = 0;
bool check(int m)
{
res = 0;
for(int i = 1; i <= k; i++)
{
res = (res + m - 1) % (k * 2 - i + 1);这里从1开始……我也不知道为什么从0开始就WA了
if(res < k) return false;
}
return true;
}
int main()
{
scanf("%d", &k);
for(int i = k; ; i++)//第一轮当然要直接保证>k啊~
{
if(check(i))
{
printf("%d\n", i);
return 0;
}
}
} 以上列举的只是部分反约瑟夫问题，当然还有许多变式没有全部介绍到。
