2022年2022年进制转换及应用 .pdf

《2022年2022年进制转换及应用 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年进制转换及应用 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 进制转换及应用一、引言计算机的一个重要理论基础就是二进制思想。任何信息最终都是以二进制数的形式存储在计算机中的，在计算机中有时还用到十六进制和八进制。所以，在实际应用中，经常需要将一个十进制数转换成二进制、八进制或十六进制的数，有时又需逆向转换，将二进制、八进制或十六进制的数转换成十进制数，有时还需要在二进制、八进制和十六进制数之间进行相互转换（2， 8，10， 16 等一般称为“基” ） 。不同进制数之间转换的基本算法是：（1） 十进制整数转换成n 进制数的方法：将十进制整数不断除以n 取余，最后反序输出即可。（2） n 进制数（整数、实数都可以）转换成十进制数方法：按“权n”展开，即

2、表示成若干项形如ai*ni的累加和即可。（3） 二进制、八进制、十六进制之间的转换方法：利用3 位二进制表示1 位八进制数， 4 位二进制数表示 1 位十六进制数的基本思想，3 位一段（或4 位一段）分别转换即可。注：一般 2n16，十进制以上、十六进制以下的数制除了09 十个字符外，还用到A、B、C、D、E、F 几个字符，分别表示1015。对于十进制，我们称它的基数为10，而二进制的基数就是2，十六进制的基数就是16。对于十进制数1234.56 ，我们可以表示成1*103+2*102+3*101+4*100+5*10-1+6*10-2，我们把10i称之为十进制各个位的“权 ” 。对于二进制数

3、11001.01001 ，我们也可以类似地表示成1*24+1*23+1*20+1*2-2+1*2-5，即二进制各个位的权为2i。这一方法（按权展开）同样可以用在任意n 进制中。二、不同进制数之间的相互转换1、十进制正整数转换成任意n 进制数 方法介绍 就是模拟小学学过的除法运算，比如要把十进制整数39 转换成二进制数，则转换方法如下左图，即不断除以 2，直到商为0，再倒序输出即可，结果一般表示为（39）10 =（100111）2 。而要把十进制整数245 转换成八进制数，方法一样，只要不断地除以8 即可，如下右图所示，结果可以表示为：（245）10 = （ 365）8。一定要注意的是“倒序输出

4、 ” 。图 1 十进制整数转换成n 进制方法示意图 算法描述 设十进制数为， 要转换成 n 进制，用数组 a 存放最后的转换结果，i 为数组下标， 则算法描述如下：i:=0 ；重复做：i: i 1；ai:=mod n := div n 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2 直到为止。依次输出最高位ai到最低位 a1 。 参考程序 将十进制整数Y转换成任意n 进制数（设n10） 。Program ex1(input

5、,output); var a: array 1.100 of integer; n,y,i,j:longint; begin write(input number y: ); readln(y); write(input number n: ); readln(n); write(,y,)10=,(); i:=0; repeat i:=i+1; ai:=y mod n; y:=y div n; until y=0; for j:=i downto 1 do write (aj); writeln(),n); readln end. 程序样例 输入： 245 8 输出： (245)10=(36

6、5)8 思考练习 如果 n 超过了 10，比如要转换成十六进制数，可以用字符A、B、 C、D、E、F 分别表示数1015，转换方法一样，只要在输出时把余数转换为字符（A F）即可 。这个程序请大家完成。2、任意 n 进制数（整数、实数）转换成十进制数 方法介绍 我们知道一个十进制数1234.56 ， 按权展开可以表示成1*103+2*102+3*101+4*100+5*10-1+6*10-2， 同样，对于任意 n 进制数，按权展开的方法是：（1101.01 ） = 1*2+1*2+0*21+1*20+0*2-1 +1*2-2= 8+4+0+1+0+0.25 = 13.25 （165）8 = 1

7、*82 + 6*81 + 5*80 = 64+48+5 = 117 这儿计算出来的13.25 和 117 就是（ 1101.01 ）和（165）8所对应的十进制数。 参考程序 将任意 n 进制整数 X转换成十进制数（设n n then 判断输入的数是否合法 begin writeln(input error! ); exit; end; weight:=weight*n; 累乘计算出每一位的权 total:=total+ai*weight; 按权展开每一位，累加求和 end; writeln(total,)10); readln end. 程序样例 输入： 2 100110 输出： (1001

8、10)2=(38)10 思考练习 如果 n 超过了十进制，则程序怎么修改呢？这个方法也适用于把任意n 进制小数转换成十进制小数，方法基本一样。因此，我们对一个n 进制的实数，就可以把整数和小数部分截取出来后，分别进行转换，最后再加起来输出即可。请大家完成。3、将十进制小数转换为其它进制的小数 方法介绍 将十进制小数转换为其它进制的数，其基本算法是：将小数乘以待转换的进制数，正向取整。例如把（ 0.325 ）10转换成二进制小数的过程如下图2 所示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

9、- - 第 3 页，共 11 页 - - - - - - - - - 4 图 2 十进制小数转换成其它进制小数方法示意图所以，运算结果是： （0.325 ）10 （0. 0101 ）2大家发现，这种转换有时是一个近似值。思考：为什么？ 参考程序 程序请大家完成。对于一个十进制的实数，我们就可以把整数和小数分解出来，分别转换成其它进制的整数和小数，最后再加起来输出结果。4、二进制和十六进制之间的转换如要把二进制数（1111011001.01111 ）2转换成十六进制数，则我们以小数点为准，向前4 位一段转换整数部分，不足则高位补0；再向后 4 位一段转换小数部分，不足则低位补0。如下图，最后相加

10、输出即可得到答案： （3D9.78）16。图 3 二进制数转换成十六进制数的方法示意图反之也一样，如要把十六进制数（A1F5.2）16二进制数，则结果为（1010 0001 1111 0101.0010）2。注意：一定要补齐4 位，为什么？ 参考程序 程序请大家完成。三、进制转换原理的应用在有些实际问题中，巧妙地应用“进制转换”思想，可以起到很好的效果，下面举例说明。例 1、用质量为1，3，9，27 和 81 的五种砝码各1 个（假如单位为克）称物体的质量，最大可称121，在实验室我们一般要求“物左砝右”。如果砝码允许放在天平的两边，编程输出称不同质量（1121）物体时，砝码应该怎样安排？例如

11、要称一个m=14克的物体，我们知道14=27-9-3-1 ，即 14+9+3+1=27。所以我们可以把天平一端名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 放置该和 9、3、 1 的砝码，而另一端放27 的砝码，这样即可称出。 问题分析 被称物体的质量计算的数学原理：设被称物体m放在天平左边，根据天平平衡原理，左边质量应等于右边质量。 问题关键在于算法中如何体现砝码放在天平左边、右边或没有参加称量。这里可以用 -1 、1、0

12、 表示砝码放在天平左、右和没有参加称量，再没有其它数，所以称为三进制数，每个砝码都有这样的三种状态。被称物体质量计算为： = a*81 + b*27 + c*9 + d*3 + e。这里 a，b，c，d，e 分别表示81，27，9，3，1 克的砝码是放在天平的左边、右边或是没用。 参考程序 Program ex3(input,output)；var a,b,c,d,e,m:integer；Begin for m:=1 to 121 do for a:= 0 to 1 do for b:= -1 to 1 do for c:= -1 to 1 do for d:= -1 to 1 do for

13、e:= -1 to 1 do if m = a*81+b*27+c*9+d*3+e then begin write(m,=,a*81)； if b0 then write(b*27) else write(+,b*27)； if c0 then write(c*9) else write(+,c*9)； if d0 then write(d*3) else write(+,d*3)； if e0 then writeln(e) else writeln(+,e)； end； readln End. 程序样例 运行程序，得到结果如下（共121 行） ：1=0+0+0+0+1 ,31=0+27+

14、0+3+1 ,121=81+27+9+3+1 例 2、01圈将2n个0和 2n个 1排成一圈。从任意一个位置开始，每次按逆时针的方向以长度为n+1的单位计数二进制数。要求给出一种排法，用上面的方法产生出2n+1个不相同的二进制数。如当n=2时，有 22个0和 22个 1排列如下图 4所示。如果从 a位置开始，逆时针方向取三个数000，然后再从 b位置上开始取三个数001，接着取 010，, ，可以得到8个不同的二进制数。设ni do begin bi:=0; bi+1:=bi+1+1; i:=i+1 end end; writeln end. 程序样例 输入 :4 输出：1 2 3 4 1 2

15、 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 9 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 例 4、已知 x

16、的值和系数 a0，a1, ,an，计算 y=anxn+an-1xn-1+an-2xn-2+,+a1x+a0的值。 问题分析 该问题看似很容易。其实随着n越大，计算量也越大，乘积和累加的次数也愈多，这里的n就是“ 问题的规模”。在此，我们想通过这个例子说明一些“算法复杂度 ”的问题，同时使大家认识到：一些看似简单的问题，其实是可以做很多优化的。 算法设计 算法 1：y=a0; for k:=1 to n do begin s:=ak; for j:=1 to k do s:=s*x y:=y+s; end; writeln (y=， y ); 该运算中用到的存储单元有a0 ，a1 ， , ，an

17、 ，以及固定的几个简单变量，所以其空间复杂性与规模 n成正比，即为 O （n） 。而时间复杂性是内循环乘法计算和外循环的累加计算，计算y共用乘法次数是： 1+2+3+,+n=n(n+1)/2 ， 加法仅 n次，而在计算机内部实现乘法要比加法花费更多的时间，所以该算法的时间复杂性为O （ n(n+1)/2 ） O（n*n/2 ） O（n2） 。算法 2：算法1中的乘法运算有重复计算：xk不需要每次从 1，x， x2，x3， , ，xk乘法去实现，只要在原先 xk-1基础上再做一次乘法就可以得到xk的结果，多用一个b数组存放 1，x， x2，x3， , ，xn，该问题的空间复杂性为O（2n） O(

18、n) 。b0:=1; for k:=1 to n do bk:= nk-1*x; y:=a0; for k:=1 to n do y:=y+ak*bk; writeln( y=， y); 此算法用了两次单循环命令，共用了2n次乘法和 n次加法，时间复杂性为O（2n） O(n) 。算法 3：利用我国古代数学家秦九邵提出的一个公式（秦九邵公式 ） ，将 y 的计算公式改写为：y=( ,(an*x+an-1)*x+an-2) ,+a1)*x+a0a0 ，a1 ，, ，an 存放系数， x为初始数据，则其程序为：y:=an; for k:=n-1 downto 0 do y:=y*x+ak; writ

19、eln( y=， y); 该算法所用的存储空间为n个单元，即空间复杂性为O （n） ，而只用了 n次乘法和 n次加法，所以时间复杂性为 O（n） 。由此，我们可以看到，在以上3 个求多项式值的算法中，算法3 可以获得最好效果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 10 四、作业（ 只要交源程序 ) 1、N进制乘法口诀表（table.pas,table.in,table.out）从 table.in中读入一个自然数N（

20、2N 16） ，打印出N进制乘法口诀表，输出到table.out中。请注意格式（大写字母、右对齐，除了最左列外，每个数据项占4 列） ，以下是 N=16时的结果 : * 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 0 1 2 0 2 4 3 0 3 6 9 4 0 4 8 C 10 5 0 5 A F 14 19 6 0 6 C 12 18 1E 24 7 0 7 E 15 1C 23 2A 31 8 0 8 10 18 20 28 30 38 40 9 0 9 12 1B 24 2D 36 3F 48 51 A 0 A 14 1E 28 32 3C 46 50

21、 5A 64 B 0 B 16 21 2C 37 42 4D 58 63 6E 79 C 0 C 18 24 30 3C 48 54 60 6C 78 84 90 D 0 D 1A 27 34 41 4E 5B 68 75 82 8F 9C A9 E 0 E 1C 2A 38 46 54 62 70 7E 8C 9A A8 B6 C4 F 0 F 1E 2D 3C 4B 5A 69 78 87 96 A5 B4 C3 D2 E1 2 、波浪数（ num.pas,num.in,num.out）波浪数是在一对数字之间交替转换的数，如 1212121，双重波浪数则是指在两种进制下都是波浪数的数，如十

22、进制数191919 是一个十进制下的波浪数，它对应的十一进制数121212 也是一个波浪数，所以十进制数 191919 是一个双重波浪数。类似的可以定义三重波浪数，三重波浪数在三种不同的进制中都是波浪数，甚至还有四重波浪数，如十进制300=606（七进制） =363（九进制） =454（八进制） =1A1（十三进制） 。你的任务就是在指定范围内找出双重、三重、四重波浪数。输入格式：输入文件num.in中仅包含一行，包含五个用空格隔开的十进制整数，前两个数表示进制的范围（ 232） ，第三与第四个数表示指定的范围（11000000） ，第五个数为2,3,4中的一个，表示要找的波浪数的重数。输出格

23、式：输出文件num.out 包括若干行，每行一个数，从小到大，以十进制形式输出指定范围内的指定重数的波浪数。样例输入：10 11 190000 960000 2 样例输出：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 11 191919 383838 575757 767676 959595作业说明：1、请在 3 月 31 日之前提交作业，否则按“未交”处理；2、本次作业只要交两个编程题的源程序，请严格按照题目规定的程序名

24、、输入输出文件名、输入输出格式要求做，只要交源程序即可。3、提交作业时，要把自己的两个源程序放在一个文件夹里（文件夹的名字为“层次 +市+学生姓名”） ，压缩成一个压缩文件后通过JSOI 网站上的“上传作业”提交。如常州市正衡中学的邹晨同学，提交的压缩文件应该是：B 常州邹晨.rar ，解压后得到的文件夹应该是“B 常州邹晨”，里面有num.pas 和table.pas两个文件。4、作业要独立完成， 一旦发现雷同， 则雷同的人全部按0 分处理。可以在 JSOI论坛上讨论、交流，方法思路一样没什么，但程序必须要自己独立完成。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -