约瑟夫问题
约瑟夫问题： 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。 n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
方法一：数组模拟
思路： 将每个成员按照对应的编号放在数组中，然后将数组中每一个元素对应的值都初始化为一个相同的数（比如 0），然后设置一个变量记录离开的人的数量作为循环的条件。在游戏过程中，如果当前成员对应的值没有发生变化过，就继续报数，此时如果他报的数等于目标值，那么就对这个成员对应在数组中的值进行改变（比如 0 -> 1），作为其离开的标志，最后再循环遍历整个数组，输出那个始终没有发生变化的成员的编号。
int ycf(int num, int target) {
int member[10000]={0};
int cnt=0;//记录退出的个数
int k=-1;这里假定开始为第一个人，下标为0，编号为1，如需从编号x开始，则k=x-2
while(cnt<num-1)
{
int i=0;//记录当前数的编号
while(i<target)
{
k=(k+1)%num;
if(member[k]==0)
i++;
if(i==target)
{
member[k]=-1;
cnt++;
}
}
}
for(int i=0;i<num;i++)
{
if(member[i]==0)
return i;
}
return 0;
}方法二：链表模拟
思路： 首先要创建一个单向不带头循环链表，在创建时是先创建一个单链表，并设置头尾指针，最后单链表创建完成之后，将头尾指针连接成环。
然后是删除相应的结点，我们可以使用循环的方法，循环的条件就是cur->next!=cur，即链表中只剩下一个结点。最后，返回该结点对应的值就可以了。
typedef struct ListNode ListNode;
ListNode* ListBuyNode(int x)
{
ListNode* node=(ListNode*)malloc(sizeof(ListNode));
if(node==NULL)
{
perror("malloc");
exit(-1);
}
node->val=x;
node->next=NULL;
return node;
}
//创建带环链表
ListNode* CreateList(int n)
{
//创建链表
ListNode* phead=ListBuyNode(0);
ListNode* ptail=phead;
for(int i=1;i<n;i++)
{
ListNode* node=ListBuyNode(i);
ptail->next=node;
ptail=ptail->next;
}//创建了一个单链表
//将尾结点和头结点连接成环
ptail->next=phead;
return ptail;//有尾结点就能找到头节点，返回头节点的话还需要遍历链表
}
int iceBreakingGame(int num, int target) {
ListNode* prev=CreateList(num);
//进行约瑟夫游戏
ListNode* cur=prev->next;//头结点
int cnt=1;
while(cur->next!=cur)
{
if(cnt==target)
{
//删除结点
prev->next=cur->next;
free(cur);
cur=prev->next;
cnt=1;//重新报数
}
else {
{
//继续报数
prev=cur;
cur=cur->next;
cnt++;
}
}
}
return cur->val;
}方法三：数学+递归
思路
题目中的要求可以表述为：给定一个长度为 num 的序列，每次向后数 target 个元素并删除，那么最终留下的是第几个元素？ 这个问题很难快速给出答案。但是同时也要看到，这个问题似乎有拆分为较小子问题的潜质：如果我们知道对于一个长度 num - 1 的序列，留下的是第几个元素，那么我们就可以由此计算出长度为 num 的序列的答案。
算法
我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。 首先，长度为 num 的序列会先删除第 target % num 个元素，然后剩下一个长度为 num - 1 的序列。那么，我们可以递归地求解 f(num - 1, target)，就可以知道对于剩下的 num - 1 个元素，最终会留下第几个元素，我们设答案为 x = f(num - 1, target)。 由于我们删除了第 target % num 个元素，将序列的长度变为 num - 1。当我们知道了 f(num - 1, target) 对应的答案 x 之后，我们也就可以知道，长度为 num 的序列最后一个删除的元素，应当是从 target % num 开始数的第 x 个元素。因此有 f(num, target) = (target % num + x) % num = (target + x) % num。 我们递归计算 f(num, target), f(num - 1, target), f(num - 2, target), ... 直到递归的终点 f(1, target)。当序列长度为 1 时，一定会留下唯一的那个元素，它的编号为 0。 （力扣官方题解）
递归：
class Solution {
int f(int num, int target) {
if (num == 1) {
return 0;
}
int x = f(num - 1, target);
return (target + x) % num;
}
public:
int iceBreakingGame(int num, int target) {
return f(num, target);
}
};迭代：
class Solution {
public:
int iceBreakingGame(int num, int target) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 1; i <= num; i++) {
ans = (ans + target) % i;
}
return ans;
}
};腾讯云开发者
