[精品]计算机导论十进制转换为二进制数的注记

[精品]计算机导论十进制转换为二进制数的注记 每一位计算机专业的新生都会被要求学习二进制数，如何将十进制数转换为二进制数将是他们学习、练习甚至考试的一项重要内容。当然，这项练习也并不难，大部份同学都会记得口诀:用2去除那个要转换的十进制数，记下每次的剩余值(remainder)，直到商值(quotient)为0，然后将所得剩余值按时间逆序写出，即得。即使不记得这个规则，也通常会记得这张图片吧: 此图展示了如何将十进制的4转换为二进制100。而且这个计算法可以推广到将十进制数转换为8进制或者16进制。我想知道的是，有没有同学会问，为什么这样计算是正确的,有没有老师试图告诉学生这样计算是正确的,在本注记中，我就试图做这样一个讲解，这样计算的合法性，并且据此引申出分治法和递归等算法概念，以说明计算机科学中算法思想的重要性。 为了方便描述，以下我将使用这样的表示法，A_10将代表10进制数A，而B_2将代表二进制数B。而且也只以十进制转换为二进制为实例进行讲解。 首先，我们注意，0、1这两个十进制数在转换为二进制数时是无需运算的，就是自己本身。这个简单的事实我们待会儿要用到。 其次，我们又发现，对任意十进制数，如果它是偶数，那么转换为二进制之后必然末尾数字为0;否则(为奇数)末尾数字为1 。比如，十进制7的二进制数末尾必然为1，而十进制8的二进制数末尾必然为0 。其实，我们知道得更多，就是对任意十进制数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把上面的步骤不断重复即可，即再判断B的奇偶性，求B除以2的商值......一直到某个十进制无需再转换为止。 至此，我们大致勾勒出了整个的计算步骤，归纳整个计算过程如下(对任意给定的十进制数A): 首先～我们判断A的奇偶性得到所求二进制的最后一位X, 其次～将A除以2～得到商值B,如果B等于0或者1～计算结束 ,结果就是BX,,否则～继续求B值的二进制。 最后输出B_2 X 为结果。 不难发现，我们这里归纳出的计算步骤与第一段(也是课本中)的计算步骤是完全一致的，于是计算方法的合理性得到了证明。 当然了，我们的任务还没完～继续分析下去，注意，在以上求解步骤中，我们的目标是求A的二进制，为了达到目标我们把所求值分成了两部份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。但真心希望得到各位同学的意见，这样的简单内容是否值得讲，大家是否愿意听。特别是，没看懂这个注记的同学一定要告诉我，那里看不懂。我还愿意知道，该如何改进才能使得我们的同学在学习的早期就建立起算法思维。谢谢关注，谢谢意见～