一.题目及剖析
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tab=note
这道题涉及到数学原理,有一般公式,但我们先不用公式,看看如何用链表模拟出这一过程
二.思路引入
思路很简单,就试创建一个单向循环链表,然后模拟报数,删去对应的节点
三.代码引入
代码语言：javascript复制/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
#include <stdlib.h>
typedef struct ListNode ListNode ;
ListNode* BuyNode(int x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = x;
newNode->next = NULL;
return newNode;
}
ListNode* createList(int n)
{
ListNode* phead = BuyNode(1);
ListNode* ptail = phead;
for(int i = 2; i <=n; i )
{
ptail->next = BuyNode(i);
ptail = ptail->next;
}
ptail->next = phead;
return phead;
}
int ysf(int n, int m ) {
// write code here
ListNode* head = createList(n);
ListNode* prev = NULL;
ListNode* pcur = head;
int count = 1;
while (pcur != pcur->next) {
if(count == m)
{
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}
else
{
prev = pcur;
pcur = pcur->next;
count ;
}
}
return pcur->val;
}四.扩展
关于约瑟夫问题,我们可以利用递归将时间复杂度降低
在Donald E. Knuth的《具体数学》中，对m=2的情况使用了递归的解决方法，并推出了一个常数表达式，使得此种情况下，算法的复杂度为常量。同时，这种思路也可以应用于n>2的情况，但无法得出常数表达式，推广后的递归算法具体的思路如下：
当n个人围成一圈并以m为步长第一次报数时，第m个人出列，此时就又组成了一个新的，人数为n-1的约瑟夫环，要求n个人的约瑟夫环问题的解，就依赖于求n-1个人的约瑟夫问题的解，要求n-2个人的约瑟夫问题的解，则依赖于求n-2个人的约瑟夫换问题的解，依次类推，直至求1个人的时候，该问题的解。
递推公式：f(N,M)=f((N-1,M) M)%N
其中，f(N,M)表示N个人报数，每报到M时杀掉的那个人，最终胜利者的编号
推导过程：
举例：11个人参与游戏，每报到3的人被杀掉
第一轮：从No.1开始报数，No.3被杀
第二轮：No.4从1开始报数，这时可以认为队伍的头是No.4，No.6被杀
……
第九轮：No.2从1开始报数，成为队伍的头，No.8被杀
第十轮：No.2从1开始报数，……No.2被杀
胜利者为No.7
假设1：当游戏中剩余11人时，我们知道胜利者为No.6。那么下一轮剩余10人时，胜利者为No.6。因为删掉No.3后，之后的人都往前移动了3位；
假设2：当游戏中剩余10人时，我们知道胜利者为No.3。那么下一轮剩余11人时，胜利者的编号是几？该问题可以看作假设1的逆过程，因此：f(11,3)=f(10,3) 3
为防止数组越界，对当前人数取模：
f(11,3)=(f(10,3) 3)
假设3：游戏中剩余N人，报到M者被杀，数组移动情况为：每杀一个人，下一个人成为头，相当于把数组向前移动M位。若已知剩余N-1人时胜利者下标为，则N个人时，就是往后移动M位。因此推导出递推公式：
f(N,M)=(f(N-1,M) M)%N
