《【2017年整理】计算机导论十进制转换为二进制数的注记》由会员分享，可在线阅读，更多相关《【2017年整理】计算机导论十进制转换为二进制数的注记（3页珍藏版）》请在金锄头文库上搜索。
1、每一位计算机专业的新生都会被要求学习二进制数，如何将十进制数转换为二进制数将是他们学习、练习甚至考试的一项重要内容。当然，这项练习也并不难，大部份同学都会记得口诀：用 2 去除那个要转换的十进制数，记下每次的剩余值（remainder），直到商值（quotient ）为 0，然后将所得剩余值按时间逆序写出，即得。即使不记得这个规则，也通常会记得这张图片吧：此图展示了如何将十进制的 4 转换为二进制 100。而且这个计算法可以推广到将十进制数转换为 8 进制或者 16 进制。我想知道的是，有没有同学会问，为什么这样计算是正确的？有没有老师试图告诉学生这样计算是正确的？在本注记中，我就试图做这样一
2、个讲解，证明这样计算的合法性，并且据此引申出分治法和递归等算法概念，以说明计算机科学中算法思想的重要性。为了方便描述，以下我将使用这样的表示法，A_10 将代表 10 进制数 A，而B_2 将代表二进制数 B。而且也只以十进制转换为二进制为实例进行讲解。首先，我们注意，0、1 这两个十进制数在转换为二进制数时是无需运算的，就是自己本身。这个简单的事实我们待会儿要用到。其次，我们又发现，对任意十进制数，如果它是偶数，那么转换为二进制之后必然末尾数字为 0；否则（为奇数）末尾数字为 1 。比如，十进制 7 的二进制数末尾必然为 1，而十进制 8 的二进制数末尾必然为 0 。其实，我们知道得更多，就
3、是对任意十进制数 A，必然是某个形状为( B_10 X_2)的二进制数，其中B 代表还没有转换的十进制，而 x 代表最末尾的二进制数值。注意，此时，我们只知道 A = B_10 X_2 ，但并不知道 B 等于什么。幸运的是，我们知道了 X 的值，只需要判断 A 的奇偶性。到底 B 等于什么呢？根据所谓的 Positional Natation（位置记数法）的定义，又根据二进制数基底为2 的事实可知 ：A = B 2 +X也就是说，B 等于 A 除以 2 的商值，X 是剩余值。如果你不记得位置记数法也没关系，将二进制数看成是基底为 2 的多项式就好了 。接着，我们只需要针对 B 把上面的步骤不断
4、重复即可，即再判断 B 的奇偶性，求 B 除以 2 的商值.一直到某个十进制无需再转换为止。至此，我们大致勾勒出了整个的计算步骤，归纳整个计算过程如下（对任意给定的十进制数 A）：首先，我们判断 A 的奇偶性得到所求二 进制的最后一位 X；其次，将 A 除以 2，得到商值 B；如果 B 等于 0 或者 1，计算结束 （结果就是 BX）；否则，继续求 B 值的二进 制。最后输出 B_2 X 为结果。不难发现，我们这里归纳出的计算步骤与第一段（也是课本中）的计算步骤是完全一致的，于是计算方法的合理性得到了证明。当然了，我们的任务还没完！继续分析下去，注意，在以上求解步骤中，我们的目标是求 A 的二
5、进制，为了达到目标我们把所求值分成了两部份 BX，其中要求 B 与 X 的二进制值（当然了，在本例子中，X 显得比较特殊，就已经是解了），这样一种把问题分解成多个子问题的求解策略我们称为分治法。尚且更为特殊的是，当我们想求 A 的二进制值，我们发现子问题的求解策略与母问题是相同的，也是求二进制。为了说明这个问题，我们考虑写这样一个算法（函数）Dec_To_Bin，该算法的输入是十进制数，输出是一个二进制数串。binary Dec_To_Bin（int A）如果 A 小于等于 1，则返回 A，结束。否则，X = A mod 2，B = Dec_To_Bin（ A / 2 ），返回 BX，结束。（注，/ 代表整除，mod 2 是求除 2 的余数。）在计算过程中，这种自己调用了自己的属性，我们称之为递归（Recursion），是计算领域中的重要概念、方法，也是一种重要的理论，值得大家在以后的学习中重视。最后强调，本注记并无什么新鲜内容，主要是为了多问一个 Why，解释一个Why。但真心希望得到各位同学的意见，这样的简单内容是否值得讲，大家是否愿意听。特别是，没看懂这个注记的同学一定要告诉我，那里看不懂。我还愿意知道，该如何改进才能使得我们的同学在学习的早期就建立起算法思维。谢谢关注，谢谢意见！
