十进制转任意进制的算法原理

在中学课本里,我们学到了一个将十进制数转换为任意进制的算法:将十进制数除以新的进制,然后将商作为下一次除法的被除数,直到商为 0,然后将每次除法的余数从右到左写,就得到了新的进制。这篇小文章用数学公式来说明这个神奇算法中的数学道理。

首先,我们不妨假设十进制正数为 \(N\),新的进制为 \(R (R \geq 2)\) 进制。我们设第 \(i\) 次除法的商和余数分别记作 \(q_i\) 和 \(y_i\)。根据算法,我们可以得到下面的递推公式:$$ q_{i-1} \div R = q_{i} \cdots \cdots y_i (1 \leq i \leq k)$$

其中,我们约定 \(q_0 = N\),\(q_k = 0\),\(q_{k-1} \neq 0\)

根据余数的意义,我们将上述公式变为 $$ q_{i} \times R + y_i = q_{i-1} \tag{*}$$

我们的出发点是要证明 $$ N = \sum_{i=1}^{k} y_i \times R^{i-1} $$

因此,我们很容易联想到将 \((*)\) 式左右同时乘上 \(R^{i-1}\),得到 $$ q_{i} \times R^i + y_i \times R^{i-1} = q_{i-1} \times R^{i-1} $$

当我们把公式累加起来之后,等式左右两边许多的项都相互抵消了,所以可以得到一个简单的公式:$$ q_{k} \times R^k + \sum_{i=1}^{k} y_i \times R^{i-1} = q_{0} \times R^{0} $$

根据约定,我们最终得到 $$ \sum_{i=1}^{k} y_i \times R^{i-1} = N \times R^{0} = N $$

其中等式左边便等于用余数从右到左排列得到的 \(R\) 进制数,而它又等于十进制数 \(N\),这就是进制转换的算法的数学道理。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注