【math】joseph loop

Joseph Loop

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

并不用模拟，是有递推公式的。

\(f(n, m)\) 代表此问题最后剩下的人的编号。

\[ \displaylines{ f(n, m) = f(n-1, m) + m \mod n } \]

class Solution {
public:
    int lastRemaining(int n, int m) {
        if (n == 1) return 0;
        int x = lastRemaining(n - 1, m);
        return (m + x) % n;
    }
};

递归转换为迭代：

class Solution {
public:
    int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
};

消除游戏

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 给你整数 n ，返回 arr 最后剩下的数字。

类似，设结果为\(f(n)\)，即先从左向右删除，再从右向左，...，直到剩下最后一个数字。

考虑对称过程\(f'(n)\)，即先从右向左删除，再从左向右，...，直到剩下最后一个数字。

# f(n) 表示从左到右剩下的数字的结果, f'(n) 表示从右到左删除的结果
# 对称性: f(n) + f'(n) = n + 1
# 递归性: f(n) = 2 * f'(n/2)
# 初始条件: f(1) = f'(1) = 1

# 根据以上条件可得: f(2 * n)/2 + f(n) = n + 1
# f(n)/2 + f(n/2) = n/2 + 1
# f(n) = (n/2 + 1 - f(n/2)) * 2

递归求解：

class Solution {
public:
    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
    }
};