当前位置：首页 > article >正文

【十进制整数转换为其他进制数——短除形式的贪心算法】

article 2025/2/1 14:08:37

之前写过一篇用贪心算法计算十进制转换二进制的方法，详见：用贪心算法计算十进制数转二进制数（整数部分）_短除法求二进制-CSDN博客

经过一段时间的研究，本人又发现两个规律：

1、不仅仅十进制整数转二进制可以用贪心算法，十进制转其他进制一样适用；

2、可以用短除的形式进行贪心算法转换，使转换更加直观。

一、按权展开求和法

二、贪心法的思路

三、贪心算法的短除形式

1、短除法

2、图解说明

四、实例

一、按权展开求和法

假设要转换的十进制数为D，转换的目标进制为N进制，假设转换完的结果为

$D=( k_{n-1}k_{n-2}...k_{0})_{N}$ (1)

在转换完的N进制数中，从右向左，数字的位置编号(也叫数位) $i$ 从0开始，一直到 $n-1$ （有些文献把最右边最低位的编号定为1，本文为了方便后续计算，定为0）。 $k_{i}$ 为第 $i$ 位的数字，对应位的权值（权值就是在这个数位上，每个1代表的数值）为 $N^{i}$ 。

那么根据按权展开求和法有：

$D=k_{n-1}*N^{n-1}+...+k_{2}*N^{2}+k_{1}*N^{1}+k_{0}*N^{0}$ （2）

二、贪心法的思路

第一步：找出在十进制数D中包含的其他进制的最大权值 $N^{i}$ ，并算出对应的数位序号 $i$ ；

第二步：用 $D$ 除以 $N^{i}$ ，求出商 $k_{i}$ （也就是第 $i$ 位对应的数字），以及余数 $r_{i}$ ；

第三步：如果 $r_{i}$ 不等于0，令D= $r_{i}$ ，回到第一步继续计算；

第四步：当 $r_{i}$ =0时，转换结束；

第五步：计算出转换结果，把所求出的 $k_{i}$ 都填到相应的第 $i$ 位，没有数字的位上补0。

三、贪心算法的短除形式

1、短除法

用短除法的形式进行贪心算法转换的过程如下图所示：

2、图解说明

先找出当前D包含的最大权值 $N^{i}$ ，D为被除数，放在短除号上侧， $N^{i}$ 为除数，放在短除号左侧，求出的商 $k_{i}$ 放在短除号右侧，余数 $r_{i}$ 放在短除号下侧。如果 $r_{i}$ 不等于0，把 $r_{i}$ 看成D，继续进行计算，直到 $r_{i}$ =0，短除结束。把右侧的一系列商填入对应的数位，没有商的数位补0，转换完成。