带余除法 | 算法式证明 | 进制转换

  |  

摘要: 进制转换算法

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


各位好,今天我们来看 leetcode 每日一题的题目,每日一题是 leetcode 的一个长期活动,大概长这个样子:

每天会从题库中选一道题,很多人会去参与讨论,也有一些大博主会跟着每日一题的进度更新题解,很多写的都比官方题解好。基本上做过每日一题的题目,其题解质量都很高。

今天的题目是标为简单的一道题,主要是把 10 进制数转换为 2 进制,涉及到的算法是短除法,此前的文章有讨论过,参考文章 进制转换

本文首先介绍带余除法,然后证明每个正整数 $b$ 都可以作为正整数表示的基底,也就是给定 $b$,任意正整数 $n$ 都可以唯一地表示为 $n = \sum\limits_{i=0}\limits^{k}a_{i}b^{i}$,证明过程给出了进制转换的算法,这种证明过程给出了一个算法的情况,可以称其为算法式证明,此前我们见过类似的例子,比如 SJT算法:沿哈密顿路径枚举全排列

此前我们用二进制分解的思想解决过很多问题,比如倍增法、比如快速幂,这是 $b=2$ 的情况。

在 Kenneth H.Rosen 的《初等数论及其应用》第二章中有相关论述,本书从头梳理了很多我们从小学就接触的东西,可以从以下链接下载。

带余除法

定理

设 $a$,$b$ 为整数,$b > 0$,则存在整数 $q, r$ 使得:

证明(构造性证明)

记 $\left\lfloor \frac{a}{b} \right\rfloor$ 表示不超过分数 $\frac{a}{b}$ 的最大整数,则:

取 $q = \left\lfloor\frac{a}{b}\right\rfloor$,$r = a - \left\lfloor\frac{a}{b}\right\rfloor b$ 即可。

$\Box$

称 $r$ 为 $b$ 除 $a$ 的最小正剩余,$a = qb + r$ 称为带余除法,其含义是如果 $b$ 不能整除 $a$ 时,依然可以执行 $b$ 除 $a$,只是需要增加一个余数 $r$ 来表示结果。

当余数 $r=0$,则 $b$ 整除 $a$,$b$ 为 $a$ 的因子,记为 $b \mid a$。

正整数的 b 进制的唯一表示

整数的表示方法对用计算机处理整数影响很大,一个整数可以通过 $b$ 进制展开,通过展开式可以进行整数的基本算术运算的算法。包含着负数的不同表示方法,计算机算术的算法会有所不同。

这里我们只证明一个基本结论,即对每个大于 $1$ 的整数作为基底,都可以得到所有正整数唯一的 $b$ 进制展开。

定理

若正整数 $b > 1$,则每个正整数 $n$ 都可以唯一表示为以下形式:

其中 $k$ 为非负整数,$0 \leq a_{j} \leq b - 1$ 为整数,$j=0,2,\cdots,n$,且 $a_{k} \neq 0$。

证明(算法式证明)

按照以下步骤,通过连续应用带余除法,来得到最终的表示方法。

首先用 $b$ 除 $n$,根据带余除法,有:

如果 $q_{0} \neq 0$,则用 $b$ 除 $q_{0}$,根据带余除法,有:

以此类推,直至某个 $k$ 上 $q_{k} = 0$ 结束(后面说明其正确性),有:

注意到商的序列满足 $n > q_{0} > q_{1} > q_{2} > \cdots \geq 0$,因此商序列中最多存在 $n$ 个项,因此上述过程是可以有限步内结束的。

然后依次代入即可。首先将第二个方程的 $q_{0}$ 的表达式代入第一个方程 $n = bq_{0} + a_{0}$ 代替 $q_{0}$,得到:

以此类推,依次将 $q_{1}, q_{2}, \cdots, q_{k-1}$ 替换($q_{k} = 0$)。得到:

下面通过反证法证明该展开的唯一性。假设有两个等于 $n$ 的这种形式的展开式,即:

其中 $0 \leq a_{k} < b, 0 \leq c_{k} < b$,如果两个展开式项数不一样,则添加零系数的项使得项数相同。

将两个展开式相减,得到:

如果两个展开式不同,则存在某个最小的整数 $j \in [0, k]$ 使得 $a_{j} \neq c_{j}$,因此:

解出 $a_{j} - c_{j}$:

因此 $b \mid (a_{j} - c_{j})$。

但是由于 $0 \leq a_{j} < b$,$0 \leq c_{j} < b$,所以 $-b < a_{j} - c_{j} < b$,因此 $b \mid (a_{j} - c_{j}) \Rightarrow a_{j} = c_{j}$,与假设矛盾。

$\Box$

有以上定理,我们知道任意 $b > 1$,我们都可以将任意正整数 $n$ 唯一表示乘 $b$ 进制展开。当 $b=2$ 时,即为在算法中最常用的二进制的情况,也就是每个正整数都可以表示为 2 的不同幂次的和,这是倍增法,快速幂等算法的理论基础。

以上定理的证明过程给出了将 10 进制数 $n$ 转换为 $b$ 进制数 $(a_{k}a_{k-1}\cdots a_{0})_{b}$ 的算法,称为短除法

题目

给你一个字符串 date,它的格式为 yyyy-mm-dd,表示一个公历日期。

date 可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循 year-month-day 的格式。

返回 date 的 二进制 表示。

示例 1:
输入: date = “2080-02-29”
输出: “100000100000-10-11101”
解释:
100000100000, 10 和 11101 分别是 2080, 02 和 29 的二进制表示。

示例 2:
输入: date = “1900-01-01”
输出: “11101101100-1-1”
解释:
11101101100, 1 和 1 分别是 1900, 1 和 1 的二进制表示。

提示:

1
2
3
date.length == 10
date[4] == date[7] == '-',其余的 date[i] 都是数字。
输入保证 date 代表一个有效的公历日期,日期范围从 1900 年 1 月 1 日到 2100 年 12 月 31 日(包括这两天)。

题解

算法:短除法

首先识别 “xxxx-xx-xx” 形式的字符串 date 中的三个数字,将其转换为整数,然后将每个整数用短除法表示为 2 进制,然后将二进制数以字符串放入结果当中。

在用短除法转换 $n$ 为 b 进制时,不断地做带余除法 $n = qb + a$,$a$ 即为新增的 $b$ 进制位,$q$ 赋值回 $n$ 作为下一轮带余除法的被除数。直至 $n$ 为零。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def convertToBase2(n: int) -> str:
if n == 0:
return "0"
result = []
b = 2
while n > 0:
a = n % b
n = n // b
result.append(str(a))
result.reverse()
return "".join(result)

class Solution:
def convertDateToBinary(self, date: str) -> str:
dates = date.split("-")
result = []
for date in dates:
n = int(date)
result.append(convertToBase2(n))
return "-".join(result)

Share