算法算术

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

字数统计: 2.1k字   |   阅读时长: 8分
, ,

摘要: 进制转换算法

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