约瑟夫问题（常规代码，递归代码，链表代码）

1.约瑟夫问题：

题目描述

n个人围���一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。

题目输入：                                                            

第一行为人数n;第二行为报数k。

题目输出：

输出最后胜利者的标号数。

2.常规做法题目分析

约瑟夫问题是一个经典的问题，也称为约瑟夫环问题，主要描述的是有一个编号为 1 到 n 的圆圈，从第一个数字开始，按照固定的步长 m 不断地删除最后一个数字，直到圆圈中只剩下一个数字为止，该数字即为胜者。

例如，当 n=7、m=3 时，删除的数字依次为第 3、第 6、第 2、第 7、第 5、第 1 个数字，胜者为第 4 个数字。

数学公式来计算胜者的编号。

假设 n 个人处于圆圈中，编号从 1 到 n。每次删除第 m 个人，直到只剩下一个人为止。

我们可以使用递推的方式来计算胜者的编号。假设 f(n, m) 表示有 n 个人时，每次删除第 m 个人后的胜者编号。

当 n = 1 时，只剩下一个人，编号为 1，即 f(1, m) = 1。

当 n > 1 时，我们可以把约瑟夫问题看作是每次删除第 m 个人，然后从下一个人开始重新编号的问题。所以，当第一个人被删除后，问题变成了有 n-1 个人时，每次删除第 m 个人的约瑟夫问题。此时胜者的编号为 f(n-1, m)。但是，由于每次删除一个人后，编号都会向前移动 m 位，所以原来的第 m 个人的编号变成了新的第 1 个人，即编号为 m 的人成为了新问题的起点。

#include using namespace std;int josephus(int n, int m) {    int winner = 0;    for (int i = 2; i  n;    cout > m;    int result = josephus(n, m);    cout > k;    int result=f(n,k);    cout next = head; // 将尾节点的 next 指向头节点，形成循环链表    return head;}// 递归删除链表中每 m 个节点之前的前 m-1 个节点ListNode* deleteKth(ListNode* cur, int m) {    // 如果链表只剩一个节点，返回该节点    if (cur->next == cur) return cur;    // 找到当前节点的前 m-1 个节点    for (int i = 0; i next;    }    // 删除第 m 个节点，并将链表尾部连接到下一个节点    ListNode* next = cur->next->next;    delete cur->next;    cur->next = next;    // 递归删除下一个节点之前的前 m-1 个节点    return deleteKth(next, m);}int josephus(int n, int m) {    ListNode* head = buildLinkedList(n);    // 使用递归算法删除节点    ListNode* winner = deleteKth(head, m);    int ans = winner->val;    delete winner;    return ans;  // 返回胜者的编号}int main() {    int n, m;    cin >> n >> m;    int ans = josephus(n, m);    cout