一.题目及剖析
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tab=note
这道题涉及到数学原理,有一般公式,但我们先不用公式,看看如何用链表模拟出这一过程
二.思路引入
思路很简单,就试创建一个单向循环链表,然后模拟报数,删去对应的节点
三.代码引入
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @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)%11
假设3：游戏中剩余N人，报到M者被杀，数组移动情况为：每杀一个人，下一个人成为头，相当于把数组向前移动M位。若已知剩余N-1人时胜利者下标为，则N个人时，就是往后移动M位。因此推导出递推公式：
f(N,M)=(f(N-1,M)+M)%N
