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

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

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

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

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

目录

一、按权展开求和法

二、贪心法的思路

三、贪心算法的短除形式

1、短除法

2、图解说明

四、实例

---

一、按权展开求和法

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

                                                      (1)

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

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

                 （2）

二、贪心法的思路

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

第二步：用除以，求出商（也就是第位对应的数字），以及余数；

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

第四步：当=0时，转换结束；

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

三、贪心算法的短除形式

1、短除法

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

图1 贪心算法的短除形式

2、图解说明

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

四、实例

下边用3个例子，分别演示一下如何用短除形式的贪心算法把十进制整数转换为二进制、八进制、十六进制数。

例1：把十进制数(35)D转换为二进制数。

计算过程如图2所示：

图2  十进制转二进制

计算说明如下：

第一步：(35)D中包含的2进制的最大权值为=32，对应数位为第5位；

第二步：35/32=1余3，第5位对应的数字为1；

第三步：D=3，继续计算，3中包含的最大权值为=2，对应数位为第1位；

第四步：3/2=1余1，第1位对应的数字为1；

第五步：D=1，继续计算，1中包含的最大权值为=1，对应数位为第0位；

第六步：1/1=1余0，第0位对应的数字为1，余数为0，计算结束。

第七步：序号为第5、第1和第0的数位，商都为1，其他位没有商，对应数字为0，所以转换的结果为(100011)B。

例2：把十进制数(168)D转换为八进制数。

求解过程如图3所示：

图3  十进制转八进制

例3：把十进制数(951)D转换为十六进制数。

求解过程如图4所示：

图4  十进制转十六进制

(全文结束)