孙子算经
●“鸡兔同笼”
《孙子算经》共三卷,完成于公元四-五世纪。卷下第31题,是后世“鸡兔同笼”题的始祖,后来传到日本,变成“鹤龟算”。书中是这样叙述的:
“今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?
这四句话的意思是:有若干只鸡兔同在一个笼子里,从上面数,有35个头;从下面数,有94只脚。求笼中各有几只鸡和兔?
趣题1:
巍巍古寺在山林,不知寺内几多僧。
三百六十四只碗,看看用尽不差争。
三人共食一碗饭,四人共吃一碗羹。
请问先生明算者,算来寺内几多僧?
●“荡杯问题”
“今有妇人河上荡杯。津吏问曰:…杯何以多??妇人曰:…有客。?津吏曰:…客几何??妇人曰:…二人共饭,三人共羹,四人共肉,凡用杯六十五。不知客几何?”
“术曰:置六十五杯,以一十二乘之,得七百八十,以十三除之,即得”。
这里告诉我们这次洗碗事件,要处理的是65个碗共有多少人的问题。其中有能了解客数的信息是2人共碗饭,3人共碗羹,4人共碗肉。通过这几个数值,很自然就能解决客数问题。因为客数是固定值,因此将其列成今式为N/2+N/3+N/4=65,易得客数六十人。
●“孙子定理”(中国剩余定理--一次同余论)
《孙子算经》具有重大意义的是卷下第26题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?答曰:『二十三』”
这个问题也被称为“物不知数”问题。西方数学史将其称为“中国剩余定理”
(Chinese remainder theorem)。
与上面的荡杯问题相比较,可以发现主要区别在于这里出现了余数,而不是整除。
此题相当于求不定方程组N=3x+2, N=5y+3, N=7z+2 ---三个方程式,4个未知数,比较难解。孙子算经给出了算法:
N=70×2+21×3+15×2-2×105=23。
这里105是模数3、5、7的最小公倍数。这里给出的是符合条件的最小正整数。
对于一般余数的情形,只要把上述算法中的余数2、3、2分别换成新的余数就行了。以R1、R2、R3
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示这些余数,那么《孙子算经》相当于给出公式
N=70×R1+21×R2+15×R3-p×105(p是整数)。孙子算法的关键,在于70、21和15这三个数的确定:
这三个数可以从最小公倍数M=3×5×7=105中各约去模数3、5、7后,再分别乘以整数2、1、1而得到。
70是5和7的公倍数,且被3除余1;
21是3和7的公倍数,且被5除余1;
15是3和5的公倍数,且被7除余1.
在这样的条件下,任意一个系数乘以对应余数所得的积,被对应出书除后所得的余数恰好等于对应余数,且该积仍然能被其他两个除数整除,因此三个积相加并不相互影响各自被对应出书除后所得的余数。
即70R1+21R2+15R3是被3除余R1,被5除余R2,被7除余R3的数。
应用上述推理,可以完全类似地把孙子算法推广到一般情形:
设有一数N,分别被两两互素的几个数a1、a2、……an相除得余数R1、R2、……R n,即表示为N≡Ri(mod a i),(i=1、2、……n),只需求出一组数K,使满足1(m od ai)(i=1、2、……n),那么适合已给一次同余组的最小正数解是(P是整数, M=a1×a2×……×an),这就是现代数论中著名的剩余定理。如上所说,它的基本形式已经包含在《孙子算经》“物不知数”题的解法之中。不过《孙子算经》没有明确地表述这个一般的定理。
上述的孙子算法一般情况四年级暂不要求。现在我们掌握的具体的解题思路如下:
先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得。对于很小的数,可以直接死算)。即
15?7=2 (1)
21?5=4 (1)
70÷3=23 (1)
再用找到的三个较小数分别乘以所要求的数(N)被7、5、3除所得的余数的积连加, 15×2+21×3+70×2=233.
最后用和233除以3、5、7三个除数的最小公倍数.
233?105=2 (23)
这个余数23就是合乎条件的最小数.
以上三个步骤适合于解类似"孙子问题"的所有问题.
韩信点兵
相传汉高祖刘邦问大将军韩信统御兵士多少,韩信答曰:每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。刘邦茫然而不知其数。
例题:假设兵不满一万,每5人一列、9人一列、13人一列、17人一列都剩3人,则兵有多少?
首先我们先求5、9、13、17之最小公倍数9945(注:因为5、9、13、17为两两互质的整数,故其最小公倍数为这些数的积),然后再加3,得9948(人)。
习题1. 一个数除以3余2,除以5余3,除以7余4,问满足条件的最小自然数____.
解答:采用"中国剩余定理":
3,5的公倍数3,7的公倍数5,7的公倍数
15 21 35
30 42 70
45 63105
60 84 140
… … …
除以7余4的除以5余3 除以3余2
分别是:60 63 35
可见60+63+35=158满足我们的条件,但不是最小的自然数,处理方法就是减去最小公倍数的若干倍,使结果在最小公倍数之内。所以
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
为:158-105=53。
习题2:
一条长长的阶梯,
如果每步跨2 级,那么最后余1 级;
如果每步跨3 级,那么最后余2 级;
如果每步跨5 级,那么最后余4 级;
如果每步跨6 级,那么最后余5 级;
只有当每步跨7级时,最后才刚好走完.
问这条台阶最少有多少级?
答案:
如果每步跨2 级,那么最后余1 级;
可知是个奇数如果每步跨 3 级,那么最后余2 级;
可知+1就是3的整数倍如果每步跨5 级,那么最后余4 级;
可知尾是4或9.但是是个奇数,所以是9如果每步跨6 级,那么最后余 5 级;
可知+1就是6的整数倍只有当每步跨7级时,最后才刚好走完.
可知是7的整数倍7*7=49 7*17=119 49+1不是3的倍数,排除了.
119+1是3和6的整数倍,所以台阶有119级。
浙公网安备 33021202002483