算法案例学习——进位制

陈忠

日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.今天我们来学习一下进位制.

【探究】

1. 你都了解哪些进位制？

2. 举出常见的进位制.

3. 思考非十进制数转换为十进制数的转化方法.

4. 思考十进制数转换成非十进制数及非十进制之间的转换方法.

【结论】

1. 进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制等等.也就是说：“满几进一”就是几进制，几进制的基数（都是大于1的整数）就是几.

2. 在日常生活中，我们最熟悉、最常用的是十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.

3. 十进制使用0～9十个数字.计数时，几个数字排成一行，从右起，第一位是个位，个位上的数字是几，就表示几个一；第二位是十位，十位上的数字是几，就表示几个十；接着依次是百位、千位、万位……

例如：十进制数4528中的4表示4个千，5表示5个百，2表示2个十，8表示8个一. 于是，我们得到下面的式子：[4528=4×103+5×102+2×101+8×100].

与十进制类似，其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同，所用的数字个数也不同.如二进制用0和1两个数字，七进制用0～6七个数字.

一般地，若[k]是一个大于1的整数，那么以[k]为基数的[k]进制数可以表示为一串数字连写在一起的形式 [anan-1…a1a0（k）]（[0

其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式，如：

[110011（2）=1×25+1×24+0×23+0×22+1×21+1×20，]

[7342（8）=7×83+3×82+4×81+2×80]，

非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：

[anan-1…a1a0（k）=an×kn+an-1×kn-1+…+a1×k1+a0×k0.]

第一步：从左到右依次取出[k]进制数[anan-1…a1a0（k）]各位上的数字，乘以相应的[k]的幂，[k]的幂从[n]开始取值，每次递减1，递减到0，即[an×kn，an-1×kn-1，…，a1×k1，a0×k0]；

第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数.

4. 关于进位制的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和其他进制之间的转换.这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出.

（1）十进制数转换成非十进制数

把十进制数转换为二进制数，教科书上提供了“除2取余法”，我们可以类比得到十进制数转换成[k]进制数的算法“除[k]取余法”.

（2）非十进制之间的转换

一个自然的想法是利用十进制作为桥梁. 教科书上提供了一个二进制数据与16进制数据之间的互化的方法，也就是先由二进制数转化为十进制数，再由十进制数转化成为16进制数.

【应用示例】

例1 将8进制数[314706（8）]化为十进制数.

解析 [314706（8）=3×85+1×84+4×83+7×82][+0×81+6×80=104902.]

所以，化为十进制数是[104902].

点拨 利用把[k]进制数转化为十进制数的一般方法就可以把8进制数[314706（8）]化为十进制数.

变式 设计一个算法，把[k]进制数[a]（共有[n]位）化为十进制数[b].

分析 从例1的计算过程可以看出，计算[k]进制数[a]的右数第[i]位数字[ai]与[ki-1]的乘积[ai?ki-1]，再将其累加，这是一个重复操作的步骤.所以，可以用循环结构来构造算法.

算法步骤如下：

第一步，输入[a]，[k]和[n]的值.

第二步，将[b]的值初始化为0，[i]的值初始化为1.

第三步，[b=b+ai?ki-1，i=i+1].

第四步，判断[i>n]是否成立.若是，则执行第五步；否则，返回第三步.

第五步，输出[b]的值.

解 程序框图如下图：

例2 把89化为二进制数.

解析 根据二进制数“满二进一”的原则，可以用2连续去除89或所得商，然后取余数.具体计算如下：

因为89=2×44+1，

44=2×22+0，

22=2×11+0，

11=2×5+1，

5=2×2+1，

2=2×1+0，

1=2×0+1，

所以89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1

=2×（2×（2×（2×（22+1）+1）+0）+0）+1

…

=1×26+0×25+1×24+1×23+0×22+0×21+1×20

=1011001（2）.

这种算法叫做除2取余法，还可以用下面的除法算式表示：

将上式中各步所得的余数从下到上排列，得到89=1011001（2）.

上述方法也可以推广为把十进制数化为[k]进制数的算法，称为除[k]取余法.

变式 设计一个程序，实现“除[k]取余法”.

分析 从例2的计算过程可以看出如下的规律：

若十制数[a]除以[k]所得商是[q0]，余数是[r0]，即[a=k?q0+r0]，则[r0]是[a]的[k]进制数的右数第1位数.

若[q0]除以[k]所得的商是[q1]，余数是[r1]，即[q0=k?q1+r1]，则[r1]是[a]的[k]进制数的右数第2位数.

…

若[qn-1]除以[k]所得的商是0，余数是[rn]，即[qn-1=rn]，则[rn]是[a]的[k]进制数的左数第1位数.

这样，我们可以得到算法步骤如下：

第一步，给定十进制正整数[a]和转化后的数的基数[k].

第二步，求出[a]除以[k]所得的商[q]，余数[r].

第三步，把得到的余数依次从右到左排列.

第四步，若[q≠0]，则[a=q]，返回第二步；

否则，输出全部余数[r]排列得到的[k]进制数.

解 程序框图如下图：

程序：

计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时，计算机又把运算结果由二进制数转换成十进制数输出.因此学好进位制是非常必要的.