取模与分数取整

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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) + dkm + 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