我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:神州彩票 > 二进制运算 >

从“韩信点兵”发现余数问题的奥秘

归档日期:04-30       文本归类:二进制运算      文章编辑:爱尚语录

  北京第五中学分校初三年级施彦培从小喜欢数学。在他看来,0到9这10个数字蕴涵着太多的奥秘,让他着迷。一次他和爸爸探讨“数的整除”及“数的余数”问题,爸爸给他讲了“韩信点兵”的故事,并告诉他这个故事里就包含了数学中的余数问题。

  爸爸告诉他,我国早在一千多年前的《孙子算经》中就有关于余数研究的记载,淮安民间流传的一则故事 “韩信点兵”就是关于余数问题的有趣应用。秦朝末年,楚汉相争。有一次,韩信率1500名将士与楚王大将李锋交战。苦战一场,楚军不敌,败退回营,汉军也死伤四五百人,于是,韩信整顿兵马也返回大本营。当行至一山坡,忽有后军来报,说有楚军骑兵追来。只见远方尘土飞扬,杀声震天。汉军本来已十分疲惫,这时队伍大哗,韩信兵马到坡顶,见来敌不足五百骑,便急速点兵迎敌。

  韩信命令士兵3人一排,结果多出2名;接着命令士兵5人一排,结果多出3名;他又命令士兵7人一排,结果又多出2名。韩信马上向将士们宣布:“我军有1073名勇士,敌人不足五百,我们居高临下,以众击寡,一定能打败敌人。”汉军本来就信服自己的统帅,这一来更认为韩信是神仙下凡,会神机妙算,于是士气大振。一时间旌旗摇动,鼓声喧天,汉军步步逼近,楚军乱作一团。交战不久,楚军大败而逃。

  “韩信用什么办法能这么快就算出1073名勇士呢?其实这就是余数问题。”爸爸告诉施彦培。

  施彦培的计算机学得不错,他知道计算机编程用的都是二进制。从“韩信点兵”说到余数,他突然想到一个问题:现在人们已经非常熟悉十进制下的余数规律,那一个二进制数的余数该如何求解呢?他去问老师,老师告诉他,求解一个二进制数的余数,通常要先把二进制数换成十进制数,再求十进制数的余数,就是原二进制数的余数。当然对一个大数来讲,这种计算过程比较繁琐。那么能不能直接在二进制下求得所给二进制数的余数呢?在二进制中,存不存在简单方便的求余数方法呢?施彦培对此产生了兴趣。

  说起二进制人们都感觉很陌生,当“1+1=10”这个式子摆在面前时第一感觉肯定是愕然,其实在二进制下这是正确的等式。由于人有十个手指头的缘故,古人很本能地将十进位作为最方便实用的计数制度,十进制数的特点是用十个数码(0、1、2、3、4、5、6、7、8、9)表示所有的数,基数是10,采用“逢十进一、借一当十”的记数方法,而二进制数的特点是用两个数码(0、1)表示所有的数,基数是2,采用“逢二进一”的记数方法,借位规则是“借一当二”。

  “其实,我们天天和二进制打交道。”施彦培介绍,二进制是由18世纪德国数理哲学大师莱布尼兹发现的,是数学中最先进的进制,用二进制表示的数具有电路实现技术简单、运算规则简化、运算速度快、适合逻辑运算以及数据抗干扰能力强、可靠性高的特点,现在计算机的程序运算、传输都以二进制为基础。

  能不能不把二进制数换成十进制数再求余数,而是直接在二进制下求所给二进制数的余数呢?施彦培一直在琢磨这个问题。在老师的指导下,他分别研究了小于10的各个除数(2至9),尝试了各种分组方法,比如,双位一个分组、三位一个分组、交叉分组等方法,经过多次失败后,他终于根据二进制数的特点,找到先按数位研究,再研究数的思路。经过近一年的演算推导和探索,终于发现一些简便计算二进制数余数的方法。

  施彦培发现,只需对所给的二进制数进行简单的分组,先计算各组上“1”的个数,然后再进行简单运算,就可求出原二进制数的余数。这比通常的做法简便了很多,对工程上常常要进行巨量的大数运算很有用。

  施彦培说,只需按“分组”、“数1、“计算”三部曲,就可很方便地求出一个二进制数的余数。他举例说明这种求二进制数余数的简便方法:

  按照通常做法:将该二进制数转换成十进制数,要进行指数运算(过程略),得到N=8334059。再求解N的余数,得到:8334059除以3的余数是2。显然,这种求解过程很繁琐。

  施彦培介绍说,他发现的方法,不用转换成十进制,只需简单三步即可求解N除以3的余数。

  第一组(带下划线的数)和第二组(不带下划线 1 1 0 1 0 1 1)2

  第三步:计算S1+2S2=26除以3的余数,得2,所以原数N除以3的余数就是2。

  在实际计算中还可以将第一组中1的个数和第二组中1的个数进行“配对”,采用弃“配对”法进一步减少计算(即每组都出现一个 “1”就是一个“配对”,每个“配对”是3的倍数,在计算余数时就可以抛弃)。在上例中,有6个这样的“配对”,弃“配对”后,只剩下第二组中4个“1”,只需计算剩下的2(S2-S1)=8除以3的余数,就可得到原数除以3的余数。进一步简化了计算。

  第三步:计算S1+2S2+4S3=34除以7的余数,得6,所以原数N除以7的余数就是6。

  在实际计算中,也可以采取将三个组中“1”进行“配对”,再抛弃“配对”的方法来进一步减少计算。即各分组都出现一个“1”就构成一个“配对”,这个“配对”是7的倍数,在计算余数时就可以抛弃。在上例中,共有4组“配对”构成7的倍数,可以抛弃。抛弃后,剩下第一组2个“1”和第二组2个“1”,这时只需计算剩下的(S1- S3)+2(S2- S3)=6除以7的余数,这可得到原数N除以7的余数。计算得到进一步简化了。

  从上例可以看出,相比转换为十进制再求余数的方法,计算量大大降低。由于运算是在二进制下进行的,因此也方便计算机实现。

  对于其他除数,也有类似的按数位分组、数“1”、配对、再求余数的规律。其中有些除数的余数只与低次位有关,如除以2的余数只与右边第一位有关;除以4的余数只与右边第一位和第二位有关;除以8的余数只与右边第一位和第二位、第三位有关。对二进制来说,求这些除数的余数更简便。显然这是由于进制特点决定的。

  虽然取得初步成果,酷爱数学的施彦培同学并没有停止探索数学王国的脚步。现在已经是初三的他,紧张的学习之余总爱写写算算或者摆弄着二进制编程。谈到下一步的研究设想,这个满脑子充满猜想而又自信的大男孩侃侃而谈:“我们可以发现二进制余数与数位上的数字有关,十进制只是解读自然数的一种方法,二进制也是解读自然数的一种方法,我们猜想,十进制中是否蕴藏着可以推广到二进制的求余规律?可否在其他进制中讨论余数问题,特别是把二进制中发现的规律推广到十六进制中?对某些大质数除数,是否在二进制中存在比十进制更为简便的求余数规律?……”记者了解到,对这些问题他已经开始了深入的研究。

  谈到未来的梦想,一脸稚气的施彦培认真而肯定地说:“不管未来做什么,肯定离不开数学!”

  研究者:北京市第五中学分校初三年级施彦培指导教师:高凯王适然从“韩信点兵”想到余数问题北京第五中学分校初三年级施彦培从小喜欢数学。在他看来,0到9这10个数字蕴涵着太多的奥秘,让他着迷。一次他和爸爸探讨“数的整除”及“数的余数”问题,爸爸给他讲了“韩信点兵”的故事,并告诉他这个故事里就包含了数学中的余数问题。爸爸告诉他,我国早在一千多年前的《孙子算经》中就有关于余数......

本文链接:http://runhappyplace.com/erjinzhiyunsuan/125.html