算法数学算法

取模与分数取整

字数统计: 1.3k字   |   阅读时长: 5分
, ,

摘要: 分数取整与取模的关系，约瑟夫环问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一下在数学算法中常见的分数取整问题，以及分数取整与取模的关系。我们直接给出结论公式，然后详细拆解约瑟夫环问题。

$1 取模与分数取整

我们直接给出取模与分数取整的两个结论公式，详细内容可以参考《具体数学》第 8 章。

$2 平均分配问题

问题

如何平均分配 n 个东西给 m 个人。

分析

首先分给每个人 $\lfloor \frac{n}{m}\rfloor$ 个，剩下 $n \mod m$ 个给前 $n \mod m$ 个人。

因此前 $n \mod m$ 个人，每个人 $\lceil \frac{n}{m}\rceil$ 个，后 $m - (n \mod m)$ 个人，每个人 $\lfloor \frac{n}{m}\rfloor$ 个。

统一公式，每个人分配的个数：

$3 约瑟夫环

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
输入: n = 5, m = 3
输出: 3

示例 2：
输入: n = 10, m = 17
输出: 2

限制：

1
2
1 <= n <= 1e5
1 <= m <= 1e6

算法1：递推法(逆向思维)

从最后剩下的数字倒推，推出该数字在之前每一轮次的位置。

初始时，也就是只剩一个数的时候，该数下标为 0。

考虑 f(n)，长度为 n 的序列，首先删除第 m % n，然后剩下一个长为 n - 1 的序列。如果记 x = f(n - 1) 即长为 n - 1 的序列最终留下的下标，那么长为 n 的序列最终留下的下标 f(n) 的结果就是从 m % n 向后数的第 x 个。

因此 f(n) = (m % n + x) % n = (m + x) % n = (m + f(n - 1)) % n。

1
2
3
4
f(n) := 一共有 n 个人的时候，最终剩下的人的编号。

f(1) = 0
f(n) = (f(n - 1) + m) % n

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int lastRemaining(int n, int m) {
        int idx = 0; // 对应 i = 1
        for(int i = 2; i <= n; ++i)
        {
            idx = (idx + m) % i;
        }
        return idx;
    }
};

优化：循环节优化

n >> m 时，f(n) = (f(n - 1) + m) % n 要加很多次才会开始取余。

在求 f(n) 时，加 t 次 m : f(n + t - 1) = (f(n - 1) + tm) % (n + t - 1)

如果加 t 次 m 之后开始取余，则 f(n - 1) + tm >= (n + 1 - 1)，t 的结果为：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lastRemaining(int n, int m) {
        if (m == 1) return n - 1;
        int last = 0, t = 1;
        for (int i = 2; i <= n; i += t) 
        {
            t = (i - last + m - 3) / (m - 1);
            if (i + t - 1 > n) 
            {
                last += (n - i + 1) * m;
                break;
            }
            (last += t * m) %= (i + t - 1);
        }
        return last;
    }
};

算法2：分数取整

初始编号为 1 到 n。模拟每次踢人，每次踢人后假设编号不从 0 开始编，而是在当前编号后面继续累加编号。

若当前踢掉的是第 k 个人，编号为 km，则剩下的人的新编号为 n + k(m-1) + 1, n + k(m-1) + 2,..., n + k(m-1) + (m-1)。

因此编号为 km + d 的人，新编号为 n + k(m - 1) + d, 其中 1 <= d < m，模拟下去会发现最后一个编号为 mn。

从 mn 开始，用 n + k(m - 1) + d 与 km + d 的关系倒推初始编号。

若当前编号为 N = n + k(m - 1) + d，则上一轮编号为 km + d，将 d 代换掉：

1
km + d = km + N - n - k(m - 1) = k + N - n

即上一轮编号为 k + N - n，下面的问题是 k 是多少，如果从 n - 1 逐渐向 1 迭代，则又回到未做循环节优化的递推法了。

由 N = n + k(m - 1) + d，可以将 k 写出来，k = (N - n - d) / (m - 1)。

因为 1 <= d < m, k 可以用取整的方式写出来。

因此上一轮的编号可以写为 $\lfloor \frac{N - n - 1}{m - 1} \rfloor + N - n$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int lastRemaining(int n, int m) {
        using ll = long long;
        ll N = (ll)m * n;
        while(N > n)
        {
            N = (N - n - 1) / (m - 1) + N - n;
        }
        return N - 1;
    }
};
Share