《人教高中数学必修算法案例.pptx》由会员分享，可在线阅读，更多相关《人教高中数学必修算法案例.pptx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1人教高中数学必修算法人教高中数学必修算法(sun f)案例案例第一页，共10页。韩信是秦末汉初的著名军事家。据说有一次汉高祖刘邦韩信是秦末汉初的著名军事家。据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法(bnf)，不要逐个报数，说能知道场上士兵的人数。，不要逐个报数，说能知道场上士兵的人数。韩信先令士兵韩信先令士兵(shbng)排成三列纵队进行操练，排成三列纵队进行操练，结果有结果有2人多余人多余;接着他下令将队形改为接着他下令将队形改为5列纵列纵队，这一改，又多出队，这一改，又多出3人；随后他又下令改为人；随后他又下令
2、改为7列纵队，这一次又剩下列纵队，这一次又剩下2人无法成整列。人无法成整列。在场的人都哈哈大笑，以为韩信用无法清点出准确的在场的人都哈哈大笑，以为韩信用无法清点出准确的人数，不料人数，不料(blio)笑声刚落，韩信便高声报告共有笑声刚落，韩信便高声报告共有士兵士兵2333人。人。众人听了一愣，不知韩信用什么办法众人听了一愣，不知韩信用什么办法 这么快就这么快就能得出正确结果。能得出正确结果。你想知道吗？你想知道吗？引入引入第1页/共10页第二页，共10页。问题情境问题情境韩信点兵韩信点兵孙子孙子(sn zi)问题问题第2页/共10页第三页，共10页。士兵排成士兵排成3列纵队进行操练，结果列纵队
3、进行操练，结果(ji gu)有有2人人多余；多余；若排成若排成5列纵队进行操练，结果列纵队进行操练，结果(ji gu)有有3人多人多余；余；若排成若排成7列纵队进行操练，结果列纵队进行操练，结果(ji gu)有有2人多人多余余.韩信点兵韩信点兵问题情境问题情境2333第3页/共10页第四页，共10页。问题情境问题情境今有物不知数，三三数之剩二，今有物不知数，三三数之剩二，五五数之剩三，七七数之剩二，五五数之剩三，七七数之剩二，问物几何问物几何(j h)？孙子孙子(sn(sn zi)zi)算经算经 孙子孙子(sn zi)问题问题（“物不知数物不知数”）答曰：答曰：二十三二十三.第4页/共10页第
4、五页，共10页。学生活动学生活动韩信点兵、孙子韩信点兵、孙子(sn zi)问题相当于问题相当于的正整数解的正整数解.求关于求关于(guny)x,y,z的不定方程组：的不定方程组：中国中国(zhn u)剩余定理剩余定理“鬼谷算鬼谷算”、“隔墙算隔墙算”、“剪管术剪管术”、“秦王暗点兵秦王暗点兵”等等等等第5页/共10页第六页，共10页。首先首先,让让m=2开始检验开始检验(jinyn)条件条件,若三个条件中有一个不满若三个条件中有一个不满足足,如如m=8，被，被3除余除余2，5除余除余3，7除余除余1，不符，不符(bf)；如如m=9，被，被3除余除余0，不符，不符(bf)；如如m=10，被，被3
5、除余除余1，不符，不符(bf)；可验证得：可验证得：m=23算法设计算法设计(shj)思想：思想：满足条件的满足条件的m还有其它的解吗？还有其它的解吗？23+105 23+2105 23+3105都是本问题的解都是本问题的解.韩信何以很快知道队伍的人数？韩信何以很快知道队伍的人数？2333=23+22105建构数学建构数学则则m递增递增1,一直到同时满足三个条件为止一直到同时满足三个条件为止.何种结构能依次检索正整数何种结构能依次检索正整数？循环结构何时结束循环结构何时结束？第6页/共10页第七页，共10页。研探新知研探新知(xn zh)1.辗转(zhnzhun)相除法:例1 求两个(lin)
6、正数8251和6105的最大公约数。解：8251610512146;6105214621813;214618131333;18133335148;333148237;1483740.则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。第7页/共10页第八页，共10页。练习：利用辗转练习：利用辗转(zhnzhun)(zhnzhun)相除法求下列两数的最大公约相除法求下列两数的最大公约数数.(2)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.(2
7、)4081(2)4081与与2072320723(1)225(1)225与与135135解解:(1)225=1351+90135=901+4590=452显然显然(xinrn)45是是90和和45的最大公约数的最大公约数，也就是，也就是225和和135的最大公约数的最大公约数 显然显然(xinrn)53是是90和和45的的最大公约数，也就是最大公约数，也就是225和和135的最大公约数的最大公约数 第8页/共10页第九页，共10页。开始开始输入：输入：m,n输出：输出：m结束结束r=0?m=nNYr=m MOD nn=r程序程序(chngx)(chngx)：INPUT“mINPUT“m，n=”
8、;m,nn=”;m,nDODO r=m MOD n r=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDENDINPUT m,nr=1WHILE r0 r=m MOD n m=n n=rWENDPRINT mEND你能根据辗转相除法的算法步骤你能根据辗转相除法的算法步骤(bzhu)(bzhu)画画出它的程序框图以及相应的程序语句吗出它的程序框图以及相应的程序语句吗?辗转相除法求两个数的最大公约数，辗转相除法求两个数的最大公约数，其算法可以描述如下：其算法可以描述如下：如此循环，直到得到结果。如此循环，直到得到结果。输入两个正整数输入两个正整数m和和n；求余数求余数r：计算：计算m除以除以n，将所得余数存放到变量，将所得余数存放到变量r中；中；更新被除数和余数：更新被除数和余数：m=nm=n，n=rn=r。判断余数判断余数r r是否为是否为0：若余数为：若余数为0则输出结果，否则转则输出结果，否则转向第向第步继续循环执行。步继续循环执行。第9页/共10页第十页，共10页。