1、1.3 算 法 案 例,第 一 章 算 法 初 步,人 教 A 版 數(shù) 學 必 修 3,普通高中課程標準試驗教科書,算法案例,數(shù)學組,韓信是秦末漢初的著名軍事家。據(jù)說有一次漢高祖劉邦在衛(wèi)士的簇擁下來到練兵場，劉邦問韓信有什么辦法，不要逐個報數(shù)，說能知道場上士兵的人數(shù)。,韓信先令士兵排成三列縱隊進行操練，結(jié)果有2人多余;接著他下令將隊形改為5列縱隊，這一改，又多出3人；隨后他又下令改為7列縱隊，這一次又剩下2人無法成整列。,在場的人都哈哈大笑，以為韓信用無法清點出準確的人數(shù)，不料笑聲剛落，韓信便高聲報告共有士兵2333人。,眾人聽了一愣，不知韓信用什么辦法 這么快就能得出正確結(jié)果。你想知道嗎？,

2、韓信點兵,孫子問題,士兵排成3列縱隊進行操練，結(jié)果有2人多余； 若排成5列縱隊進行操練，結(jié)果有3人多余； 若排成7列縱隊進行操練，結(jié)果有2人多余.,韓信點兵,2333,今有物不知數(shù)，三三數(shù)之剩二， 五五數(shù)之剩三，七七數(shù)之剩二， 問物幾何？,孫子算經(jīng),孫子問題,（“物不知數(shù)”）,答曰：二十三.,韓信點兵、孫子問題相當于,的正整數(shù)解.,求關于x,y,z的不定方程組：,中國剩余定理,“鬼谷算”、“隔墻算”、“剪管術(shù)”、“秦王暗點兵”等等,首先,讓m=2開始檢驗條件, 若三個條件中有一個不滿足,如m=8，被3除余2，5除余3，7除余1，不符； 如m=9，被3除余0，不符； 如m=10，被3除余1，不符

3、； 可驗證得：m=23,算法設計思想：,滿足條件的m還有其它的解嗎？,23+105 23+2105 23+3105都是本問題的解.,韓信何以很快知道隊伍的人數(shù)？,2333=23+22105,則m遞增1,一直到同時滿足三個條件為止.,何種結(jié)構(gòu)能依次檢索正整數(shù)？,循環(huán)結(jié)構(gòu)何時結(jié)束？,研探新知,1.輾轉(zhuǎn)相除法:,例1 求兩個正數(shù)8251和6105的最大公約數(shù)。,解：8251610512146;,6105214621813; 214618131333; 333148237; 1483740.,則37為8251與6105的最大公約數(shù)。,以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。

4、也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。,練習：利用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù).,(2)20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,(2)4081與20723,(1)225與135,解:(1)225=1351+90,135=901+45,90=452,顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),顯然53是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),程序：INPUT “m，n=”;m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND,你能用當型循環(huán)結(jié)構(gòu)來設計算法嗎?,INPUT m,n r=1 WHILE r0 r=m MOD n m=n n=r WEND PRINT m