十进制转化其他进制,原理分析

2022/03/07 Algorithm 共 2365 字,约 7 分钟

LeetCode 的每日一题,今天的题目是“504. 七进制数”jser 看到这道题,简直 so easy,一行代码解决:return num.toString(7)。但是,对于想成为大佬的我们来说,不能局限于 API 工程师,除了灵活使用语言提供的 API 之外,我们也要去思考这背后的逻辑、原理是什么?毕竟,计算机也是由人们创造出来的可以高速运算的 01 工具。

OK,话不多说,让我们看看通过这个十进制转七进制这道题,如何实现,又如何通过理解其背后的逻辑、原理,然后举一反三,实现十进制到其他进制之间的转化!

运行结果

前置知识

面向对进制不熟悉的同学而写,了如指掌的同学可以跳过本段~~ n 进制,在数学中表示为数值从 0 累加到 n-1 后,再加 1,就要向更高位进 1 了。 即在我们熟知的十进制中,有着个位十位百位等等。 那么,个位中,有 0-9 来表示,当从 9 再加 1 时,0-9 中已经没有可以表示的数字了,那么这时候就会向更高位也就是十位进一,即 10。

那么对于 7 进制呢?同样的思想,它也是会有“个位十位百位”,那么它的个位,就用 0-6 来表示了。同样的,在七进制中,6 再加 1 时,就要向更高位进一了,于是,十进制的 7 就是 七进制的 10。

十进制转七进制,背后的逻辑分析

  • 对于十进制中的 0-6,可以不用变化就是七进制中的 0-6 了,为何?在上面提到,对于 n 进制来说,当数值累加到 n-1 之前时,是都不用进位的。
  • 对于十进制中的 7,6+1 即是 7,对于七进制,6 已经是个位能表示的最大值了,那不就是要向高位进一了吗?故十进制中的 7,由 6 + 1 后,向高位进一得到 1-,而 6 加完 1 后,也没有剩余值了,所以个位还是 0,故最终是:10
  • 对于十进制中的 > 7,其实就是前两者情况的复合情况。拿十进制中的 10 来说,可以用十进制的3 + 7来表示吧,那么,3不就是对应情况 1,7不就是对应的情况 2 吗?对于的七进制就是13。而 十进制的20,那就是6 + 7 + 7,其中,6对应的是情况 1,而剩余的两个7就是七进制中的20,咦,两个七是20,那三个呢,四个呢,7 个的时候呢?
    • 七进制中,逢 6 进 1,对于十位上的 6,也是如此,所以,十位上有将要有 7 个时,也是要更高一位进一的,即60 + 10 = 100
    • 故,我们在进行转化时,对于十位上出现的大于 6 的情况,也是要以情况 3 来处理的。唔,循环判断了。

那接下来让我们尝试用代码实现一下吧~

/**
 * @param {number} num
 * @return {string}
 */
var convertToBase7 = function (num) {
    // 符号,考虑到 num 为负值,在这里将其符号存起来,下面取值时将其取正值
    const sign = num < 0 ? '-' : '';
    let str = '',
        lastVal = Math.abs(num);
    // 使用 do while,而不是 while,是因为循环体内的语句至少会执行一次。用 do while 更合适,可以减少一次 lastVal 的取值书写。
    do {
        // 对剩余数值进行求余,这样得到的值就是 情况 1,随后得到的值添加到 结果字符串前方即可。PS:添加到前方是因为更高位。
        str = (lastVal % 7) + str;
        // 随后求出剩余数值中还有多少个 7。
        lastVal = Math.floor(lastVal / 7);
    } while (lastVal > 0);
    // 直到剩余数值为零,结束循环。

    // 将符号添加到结果中。Done!
    return sign + str;

    // 现在我们不是只会用 API 的工程师了~~
    // return num.toString(7);
};

十进制转 n 进制

上面了解到十进制转七进制的背后逻辑后,那么,对于十进制转化为其他进制,是否能做到举一反三呢?

本质上,我们需要知道的有两点:

  1. 对于 n 进制,在其 n-1 时,再加 1,就要向高位进一了。
  2. 对于任意位置(个位十位百位),都可看成一种情况,那就是对于>= n的数值,要进行进位,< n的数值,添加到字符串的最前方即可。

那么,来看看代码怎么实现吧~

/**
 *
 * @param {number} num
 * @param {number?} radix
 * @returns string
 */
// 这里 radix 使用 ES6+ 的参数默认值
var convertToBaseN = function (num, radix = 7) {
    const sign = num < 0 ? '-' : '';
    // 对进制进行最大最小值判断。范围:2~32
    radix = Math.max(2, Math.min(radix, 32));

    // 声明多种进制个位对应的字符表示,如超过十进制的进制中,10 用 A 来表示
    const charIndex = Array(32)
        .fill(0)
        .map((_, i) => (i < 10 ? `${i}` : String.fromCharCode(65 + i - 10)));

    // 取 num 绝对值
    let str = '',
        lastVal = Math.abs(num);
    do {
        str = charIndex[lastVal % radix] + str;
        lastVal = Math.floor(lastVal / radix);
    } while (lastVal > 0);

    return sign + str;
};

最后总结

Q:这题这么简单,有必要吧啦吧啦写这么多吗? A:可能不少人会对这种简单题,嗤之以鼻,但简单题并非一无是处。对于我们了解知识,它其实是从外到内的一个很好的入口,不积跬步,无以至千里。当我们面对简单能够做到平心静气,那么算法中的中等题,困难题,不过是各种方式的排列组合,随之庖丁解牛罢了。

Q:有那么多大佬写了题解,你为啥还要巴拉巴拉的写呢? A:无限的星空中,既有耀眼的恒星发散着它的光芒,也有着小小的星星,一闪一闪的照耀着。我们应当敬佩大佬,向之学习,也应当照耀前方,向前进!

Q: 那么我们应该? A:冲啊,高山就在那里~

文档信息

Search

    Table of Contents