Skip to content

【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));
    }
};