补充奥数从数的二进制谈起.doc

精品文档，仅供学习与交流，如有侵权请联系网站删除从数的二进制谈起在即将进入21世纪的今天，电子（数字）计算机内部数的存贮和计算采用二进制已是众所周知的事了.据学者考证，中国在公元前2000多年的伏羲氏发明的八卦，即用和-两种符号拼出来的。如果把看成1，把-看成0，那么上述八卦可以翻译成二进制数（列于下面）。但是人类历史进程表明，二进制大约被人类冷落了近四千年（在此期间一直重视和使用十进制），直到20世纪40年代，科学技术的整体水平（有了无线电通讯、雷达技术和真空管、继电器等电子元器件）进一步提高，再加上反法西斯战争需要发明原子弹（原子弹许多设计数据不能事先在实验室测出，而必须靠理论计算，而计算量超过人类有史以来全部算术运算），著名数学家冯·诺伊曼（J.von Neumann）和另一些年轻数学家发明制成了称之为ENIAC的通用电子数字计算机（用18000支真空管，1500个继电器，几十万电阻电容，自重30吨，耗电200千瓦）.直至今日，电子计算机主要还是冯·诺伊曼体系.告诉大家这一些历史，主要说明我们不能停留在为祖先最早发明了二进制而自豪这一步，还要看到数学大有用武之地，但要与经济建设和科学技术广泛结合才能起大的或巨大的（如电子计算机）作用.下面看二进制本质到底是什么？人类天生双手十指.“搬着手指头”计数，是每个人幼时必经之路.十进制数有两大内涵.一是有十个不同数符：0，1，29；二是“逢十进一”的进位法则，有个、十、百、千等自右向左的数位.倘若人类双手八指，也许地球上今日该流行八进制了.所以二进制也有两大内涵.一是有两个不同数符：0，1；二是“逢二进一”.其实，我们已见过非十进制的事物，一年十二个月，十二进制；一周七天，七进制；一小时六十分，一分六十秒，六十进制；一英尺等于十二英寸（电视机常说20英寸，21英寸），十二进制；一副三角尺含2块，一双鞋含2只，一双袜子含2只，一双筷子含2根，这些都可看成二进制.一个十进制数1993可表述为：19931000+900+90+3=1×103+9×102+9×10+3a3×103+a2×102+a1×10+a0其中0ai9，而i是0到n中的一个整数。再回到二进制.大家知道：数是计算物体的个数而引进的，0代表什么也没有，有一个，记为“1”；再多一个，记为“10”（在十进制下记为2）；比“10”再多一个，记为“11”.依次类推，我们很容易接受（或自己发明）二进制下，从小到大的数列，不妨列表：为了不引起混淆，我们把二进制数右下角标一个2，如：（10）2=（2）10，或省略括号，省略十进制标记，略为：102=2，或（10）2=2，11112=15和十进制对数位有一省略名字一样，二进制的数位也可称呼：例如：199310245122561286481，写成二进制为：0×40×20×1（88）10因而二进制的数化为十进制，只要读出二进制各数位累加即可，如N（bnbn-1bn-2b2b1b0）2则有N=（bn×2nbn-1×2n-1bn-2×2n-2+b2×22b1×21+b0）10难度大的是怎样较快地把一个十进制数化为二进制数.还以1993为例，前面的方法是先找出二进制的高位数字，记熟了2的各种幂次（a的n次幂表示n个a相乘，记为an），找到不超过1993的最大的2的幂，是210=1024，得b10=1，再找不超过（1993-210）的最大的2的幂，是29=512，得b9=1，依次类推得b8，b7b2，b1，b0.这是由高位到低位逐渐推得的方法。现在设法自低位到高位，先找b0.显然，十进制偶数，b0=0，十进制奇数b0=1，所以b0是N除以2的余数.再说b1，因为N=bn×2nb2×22以后的余数，余数为0，b1就为0；余数为1，b1就为1；这样的想法可逐渐向高位推，得出一般性方法.还以1993为例，写出竖式：N=1993，b0为1993÷2的余数，(1993)10=(11111001001)2以后熟悉了这一算法，我们可很快地化十进制数为二进制数。例 如化（19）10，（101）10，（81）10为二进制的竖式为：（19）10（10011）2；（101）10（1100101）2；（81）10（1010001）2顺便说一句，现在使用电子计算机，直接输入十进制数即可，因为机器内部已专门编有（十）化（二）程序，可以自动转换.下面讲一下二进制数的加减乘除四则运算：加法“口诀”特别简单，000，10011，11=10.表述成运算时的竖式（用十进制和二进制比较）读者不难体会竖式中进位及累进等与十进制相似的规则.关键之处会“逢二进一”.减法的关键在于够减就减；不够减时，向高位借，而“借一还二”.（高位借一，相当于低的为二）.例如：1 不够减，向高位借，不够减； 不够减，借1还1 能借，再向更高位借；第三个竖式和十进制中1007的思想是一样的。二进制的乘法口诀只有三句，1×0=0，0×0=0，1×1=1.看竖式：二进制除法是乘法逆运算，除法也就是连减.看竖式：十进制中： 二进制中：又如，1993÷8822余57，二进制除法，在试找商时，较省力，要么0，要么1。二进制数有被电子计算机采用的好处，但人们有时还觉得它表达一个数时，数位太长，如（1023）10，表成二进制为十位：（1111111111）2，为读写和观察方便，要缩短数位又便于机器使用，科学家们偏爱于八进制和十六进制.大家可以自己扩充八进制的数的概念和运算：八进制有0，1，27共八个数符，由低位向高位是“逢八进一”，如：N=（cnc3c2c1c0）8cn×8n+cn-1×8n-1+ c2×82+c1×8+c0其中0ci7，i取0，1，2n。十进制化八进制：（1993）10=（3711）8；（88）10=（130）8（4041）84×5124×8+120811993+88=2081加法关键在于“逢八进一”。减法：2081-199388（4041）8-（3711）8（130）8，减法关键在于不够减时，“退一还八”乘法：八进制乘法口诀表重新制定如下：八进制乘法：（7535）8=7×512+5×64+3×8+5=（3933）10这些口诀读起来不顺口，如读成“七七得六一”，当然是八进制的六个8加上一个1.同样做除法时，也挺费神，看着“七七乘法表”做可省心些，并不是说除法有什么难度，主要是脑中的十进制“九九表”干扰了“七七表”的记忆。（7535）8÷（23）8（317）8现在再讲十六进制。大家自然会想到16个数符要设想一套简明的表达符号，国际上通用为0，1，2，8，9，A，B，C，D，E，F.这里特别请大家记住六个字母：A，B，C，D，E，F.A代表10，（十六进制中比9多一的数），同理B代表11，C代表12，D代表13，E代表14，F代表15.这样：N=（dndn-1d2d1d0）16dn×16n+dn-1×16n-1+d2×162+d1×16+d0其中di取自0，19，A，B，C，D，E，F.i可取0，1n。例如 N（20A）16=2×16210=（522）10（AB）1610×1611=（171）10如把十进制直接化为十六进制：十六进制中的加法其关键在于“逢十六进一”，减法的关键则在于“退一还十六”。（821）16=8×162+2×16+1=8×256+32+1=2081=1993+88注意：十六进制的乘法和除法很费神，要构造“十六十六表”.利用这表做乘法及除法：（10AD）16=163+10×16+13=4096+16013=4269（F3）16=15×16+3=2434269×2431037367（FD437）16=15×164+13×163+4×1623×16+7=（15×16+13）×164）×16+3）×16+7=1037367当然这十六进制的乘除法是很不习惯的.下面谈一下二进制和八进制、十六进制之间的较密切的相互关系。把一个二进制的数自右向左3位一组，立刻可以翻译成八进制数.其间对应规律为：同样，把一个二进制数自右向左4位一组，立刻可以翻译为十六进制数.其间对应规律为：如（1993）10（11111001001）2（011111001001）2=（3711）8（011111001001）2=（7C9）16前面在十六进制下很不顺手的除法FD437÷10AD=F3可以重新用二进制检验：（FD437）16=（1111 1101 0100 0011 0111）2（10AD）16（10000 1010 1101）排成除法竖式：最后，关于三进制数、五进制数、七进制数，以及一般的g进制数，读者一定可以自己推出一套记数、转化及加减乘除的法则来。例如：（1993）10=（5545）7=（30433）5=（2201211）3等.只要看竖式：这样，将一个七进制的数化成三进制数时，可以先将此数化成十进制数作中介而求得，例如：（1046）71×734×76=343286=（377）10（1046）7=（111222）3最后介绍几个问题.研究表明，要保存数码最经济的进位制是三进制.可惜现在物理器件较成熟的还是支持两种状态的二进制。不久前刚逝世的本世纪杰出的科普作家阿西莫夫（IsaacAsimov）曾喜悦地谈到自己年轻时独立解决了一个看似与二进制无关的有趣问题.问题是这样的：如何制造个数最少的一些单位砝码，如1克、2克、3克、4克等，能称出1克到1千克的任何整克数的物体？答案是：1克、2克、4克、8克、16克、32克、64克、128克、256克、512克，共十个砝码.实际上这些砝码一直可称出1到1023克之间任何整克数的物体.这在我们学完二进制数以后就不难理解了.如：x=a9a8a7a6a5a4a3a2a1a0，每个ai或0或1表示2克砝码或不用或用上.如把问题再简化一些，如只许用3个砝码，就制成1克、2克、4克.可称1、2、7克的任何整克数物体，或说要称1、2、7克之间任一物体，3个砝码是最少的了。因为1克必然要的.2克，如不要，再造一个1克砝码，这样用二个1克砝码，仅能称1克、2克共2种物体，效率不高.所以造一个1克，一个2克，这样可以称1、2、3克三种物体了.下一个不必造3克的砝码，而造了一个4克的砝码，所以1克、2克、4克是最省个数的体系了.十个砝码最省的推理也相似.在结束本讲之时，希望读者注重于理解各种进制的思想，不必去死记硬背八进制乘法表、十六进制乘法表.并请思考类似于十进制的分数、小数、循环小数等内容在二进制或八进制等体系下，如何进行？习题 1.（518）10（ ）2（ ）8（ ）16=（ ）3=（ ）5（ ）72.（AF01）16=（ ）73.12481632641285161024 用二进制计算后，能很快得到十进制答案吗？（提示：类比于990+9009991000-1）4.请用二进制运算、三进制运算实现下面式子：5.用竖式做十六进制除法：（FD 437）16÷（F3）166.请你造一个三进制乘法表，造一个七进制乘法表。7.一个g进制的数，N=a5·g5a4·g4a3·g3a2·g2a1·ga0.要计算它的十进制数值时，有一个简便算法：N（a5·ga4）·g+a3）· g+a2）·ga1）g+a0.这样共进行5次乘法5次加法，如死板地按a5·g5+a1 ·ga0，需进行（5+4+32+1）15次乘法5次加法，显然浪费时间.而另有一个聪明学生想：我在纸上先把g，g2、g3、g4、g5记下来这样做了4次乘法，再把这5个g相应与ai作乘法，又做5次，总共做了9次乘法，5次加法，中间还要耗费空白纸记下gi，他仔细一想觉得不合算了，就接受了题目中的简便算法.现在请你用简便算法求出3进制的N。N（210122）3（ ）108.在二进制下，一个数扩大2倍，就在右边添一个0，扩大4倍，右添二个0扩大2倍，右添i个0.这个规则对吗？类似规律在八进制下怎样叙述？十六进制下呢？请你自己想一下，如何“自圆其说”地把二进制数推广到分数、小数，以及二进制循环小数？10.如果天平两边都可以放砝码，即可以调用两砝码的数值差，要称物体而制造尽可能少的砝码，借用多少进位制？习题十四解答1.（518）10=（1006）8（1000000110）2=（206）16（201012）3（4033）0（1340）72.（AF01）16=10×163+15×162+1=44801=（244421）73.12481610245.十六进制除法：6.三进制乘法：七进制乘法：7.N=（210122）3=2×35+1×34+0×331×32+2×31+2（2×3+1）×3+0）×3+1）×3+2）×32584。8.规律对的.（N）8，八进制数扩大8倍相当于右边添一个0；（N）16，十六进制数扩大16倍相当于右边添一个0。9.二进制小于1大于0的数也叫纯小数，整数部分记为0，后加小数二进制分数：分数线上面写二进制整数，分数线下面写二进制整数，值等于分子除以分母。二进制循环小数，但是并非每个十进制循环小数都可化成别的进制循环小数的。此处含义：十进制循环小数但在七进制下，显然不是一个循环小数10.天平两边均可放砝码，调用三进制合适.因为：（1）10=（1）3，（2）10=（3-1）10=（10-1）3右边放3克，左边放1克，相当于右边放一个2克。（3）10（10）3，（4）10（10+1）3所以，制造一个1克、一个3克的砝码就可以称出1、2、3、4共4种物体了。再扩大：1克、3克、9克，共3个砝码可称出1克到13克之间所有整数克物体了.请读者自己补证。例如（13）10=（100101）3 （12）10=（10010）3（11）10（100+10-1）3 （10）10（100+1）3（9）10（100）3 （8）10（100-1）3（7）10=（100+1-10）3（6）10（100-10）3 （5）10=（100-10-1）3结论：制造1、31、32、333K共K1个砝码，天平左右两边都允许放砝码，可称出1、2（3K+1-1）/2种整克数物体.【精品文档】第 9 页