數(shù)學(xué)教材梳理算法案例

學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精庖丁巧解牛知識(shí)·巧學(xué)1．幾個(gè)常用函數(shù)符號(hào)求余函數(shù)Mod（m,n)：Mod（m，n）表示取m除以n的余數(shù)。如：m被3除余2，可表示為Mod（m,3)=2。取整函數(shù)Int（x)：表示取不大于x的最大整數(shù)。如：Int(2）=2，Int(2。3)=2,Int(2。6)=2.誤區(qū)警示不要與四舍五入相混淆Int(-2。3）=—3。可用mInt(m/n）*n表示m除以n的余數(shù),如m被3除余2,可表示為mInt（m/3）＊3=2。2．算法典型案例案例1：韓信點(diǎn)兵——孫子問(wèn)題《孫子算經(jīng)》中載有“物不知數(shù)"這個(gè)問(wèn)題：今有物不知其數(shù)，三三數(shù)之剩二;五五數(shù)之剩三；七七數(shù)之剩二，問(wèn)物幾何？答曰“二十三”。這就是著名的孫子問(wèn)題（記載于中國(guó)古代約公元3世紀(jì)成書(shū)的《孫子算經(jīng)》,是原書(shū)卷下第26題）。這個(gè)問(wèn)題可以簡(jiǎn)單地用一句話描述，即“一個(gè)正整數(shù)，被3，5,7除,余數(shù)分別為2，3，2”.設(shè)這個(gè)數(shù)為m，則可列關(guān)于x,y,z的方程組表示：聯(lián)想發(fā)散這一類問(wèn)題的解法可以推廣成解一次同余式組的一般方法．秦九韶給出了理論上的證明，并將它定名為“大衍求一術(shù)”。這個(gè)問(wèn)題的通用解法稱為“中國(guó)剩余定理"。秦九韶（公元1202—1261年），南宋數(shù)學(xué)家，著《數(shù)書(shū)九章》十八卷．全書(shū)共81道題，分為九大類：大衍類、天時(shí)類、田域類、測(cè)望類、賦役類、錢谷類、營(yíng)建類、軍旅類、市易類。其中對(duì)“大衍求一術(shù)"（一次同余組解法）和“正負(fù)開(kāi)方術(shù)"（高次方程的數(shù)值解法)等有十分深入的研究.“大衍求一術(shù)”，在世界數(shù)學(xué)史上占有崇高的地位。計(jì)算機(jī)解決:從2開(kāi)始，讓m依次去除，直到滿足要求為止.這樣，只要使用循環(huán)，由小到大依次搜索,直到找出滿足條件的數(shù)即可.流程圖如圖1-4—1:圖1-4-1案例2：輾轉(zhuǎn)相除法求最大公約數(shù)輾轉(zhuǎn)相除法又稱歐幾里得算法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù),若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成一對(duì)新數(shù)，繼續(xù)上面的除法,直到余數(shù)為零，此時(shí)的除數(shù)就是所求兩數(shù)的最大公約數(shù)。誤區(qū)警示這是一個(gè)反復(fù)執(zhí)行的步驟,要用循環(huán)結(jié)構(gòu)實(shí)現(xiàn).注意循環(huán)條件的設(shè)置，此處可用直到型循環(huán),條件為r=0，對(duì)于循環(huán)體部分，需要反復(fù)執(zhí)行的是r=mMODn。要實(shí)現(xiàn)上述算法，在重復(fù)執(zhí)行之前,要對(duì)m,n的兩個(gè)變量重新賦值（m=n，n=r)，注意體會(huì)理解該遞歸思想。（1）算法步驟:以求正整數(shù)m,n(m＞n）的最大公約數(shù)為例。第一步:輸入兩個(gè)正整數(shù)m，n(m＞n）;第二步：判斷m,n的大小,讓m表示較大的數(shù)，n表示較小的數(shù)；第三步：計(jì)算m/n的余數(shù)r；第四步：如果r≠0，那么把n賦值給m，把r賦值給n，返回第二步；否則，執(zhí)行下一步;第五步：輸出最大公約數(shù)m。（2)流程圖如圖1-4-2圖1—4-2偽代碼如下：m←2WhileMod（m,3)≠2或Mod（m，5)≠3或Mod(m,7)≠2m←m+1EndWhilePrintm更相減損術(shù)更相減損術(shù)是中國(guó)古代算書(shū)《九章算術(shù)》中的一個(gè)優(yōu)秀算法;更相減損術(shù)可以求最大公約數(shù)：對(duì)于給定的兩個(gè)數(shù)，以其中較大的數(shù)減去較小的數(shù),然后將差和較小的數(shù)構(gòu)成一對(duì)新數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行以上步驟直到差數(shù)與較小的數(shù)相等，此時(shí)相等的兩數(shù)即為所求的最大公約數(shù)，最后該最大公約數(shù)再乘以2即為所求。學(xué)法一得所求兩數(shù)都是偶數(shù)時(shí)，可先除以2,再求除以2后兩數(shù)的最大公約數(shù).（1）算法步驟：以求正整數(shù)m，n的最大公約數(shù)為例，第一步:輸入兩個(gè)正整數(shù)m，n（m＞n)；第二步:r←m-n；第三步：如果r<n,那么m←n，n←r，否則，m←r；第四步：如果m≠n，則返回第二步，否則執(zhí)行下一步；第五步：輸出m。(2)程序框圖如圖1—4—3圖1-4-3案例3：二分法求方程近似解二分法是方程求根的一種常用方法,其過(guò)程體現(xiàn)的就是算法思想.理論依據(jù)：我們知道，若函數(shù)f（x）在區(qū)間［x1，x2]兩端點(diǎn)的函數(shù)值異號(hào)，即f(x1)f（x2）<0，則在區(qū)間[x1，x2］內(nèi)方程f(x）=0至少有一個(gè)根。二分法是說(shuō)：如果在區(qū)間［x1,x2］內(nèi)f（x)=0僅有一個(gè)根x，則可以取x1與x2的中點(diǎn)x3=（x1+x2）/2進(jìn)行判斷，若f(x3)與f(x1)異號(hào)，說(shuō)明有一個(gè)根在區(qū)間[x1，x3］中,否則在區(qū)間［x2,x3］中。然后按上述方法逐漸縮小有根區(qū)間,從而逼近方程f（x)=0的根.當(dāng)有根區(qū)間小到一定程度時(shí),把這個(gè)區(qū)間的中點(diǎn)的x值當(dāng)作方程的近似根.用二分法設(shè)計(jì)求方程f(x)=0的近似根算法的基本步驟：（1）確定近似根所在的基礎(chǔ)區(qū)間[a，b］和近似根的精確度c；(2）求有根區(qū)間的中點(diǎn),判斷是否滿足精度要求；（3）求區(qū)間端點(diǎn)的函數(shù)值f（a），f(b）；（4）判斷f（a)f(b）的符號(hào)，改變有根區(qū)間的下限或上限;（5）循環(huán)求近似根；（6）輸出根的近似值.進(jìn)位制進(jìn)位制是一種記數(shù)方式,用有限的數(shù)字在不同的位置表示不同的數(shù)值.可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡(jiǎn)稱n進(jìn)制.現(xiàn)在最常用的是十進(jìn)制，通常使用10個(gè)阿拉伯?dāng)?shù)字0-9進(jìn)行記數(shù)。對(duì)于任何一個(gè)數(shù)，我們可以用不同的進(jìn)位制來(lái)表示。一般地,若k是一個(gè)大于一的整數(shù)，那么以k為基數(shù)的k進(jìn)制可以表示為：anan—1…a1a0(k)（0<an<k,0≤an-1，…，a1,a0anan-1…a2a1a0（k）=an×kn+an—1×kn—1+…+a2×k2+a1而表示各種進(jìn)位制數(shù)時(shí)一般在數(shù)字右下腳加注來(lái)表示，如111001（2）表示二進(jìn)制數(shù),34（5）表示5進(jìn)制數(shù)。把二進(jìn)制數(shù)110011（2）化為十進(jìn)制數(shù)：110011（2)=1*25+1*24+0*23+0*22+1＊21+1＊20=32+16+2+1=51。把八進(jìn)制數(shù)7348（8）化為十進(jìn)制數(shù)：7348（8）=7*83+3＊82+4*81+8＊80=3584+192+32+8=3816.十進(jìn)制數(shù)57，可以用二進(jìn)制表示為111001，也可以用八進(jìn)制表示為71、用十六進(jìn)制表示為39，它們所代表的數(shù)值都是一樣的。典題·熱題知識(shí)點(diǎn)一利用輾轉(zhuǎn)相除法和更相減損術(shù)解題例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求下列兩數(shù)的最大公約數(shù):261，319。思路分析:使用輾轉(zhuǎn)相除法可依據(jù)m=nq+r，反復(fù)執(zhí)行,直到r=0為止，亦可用如下的方法，直到余數(shù)為0；用更相減損術(shù)就是根據(jù)m—n=r，反復(fù)執(zhí)行，直到n=r為止。解:（1）輾轉(zhuǎn)相除法：319÷261=1（余58）；261÷58=4（余29);58÷29=2（余0)?！?19與261的最大公約數(shù)是29.更相減損術(shù):319-261=58；261—58=203；203—58=145；145—58=87；87—58=29；58-29=29.∴319與261的最大公約數(shù)是29.深化升華通過(guò)上例可以發(fā)現(xiàn)用輾轉(zhuǎn)相除法和更相減損術(shù)求得的最大公約數(shù)是相同的，但用輾轉(zhuǎn)相除法的步驟較少，而用更相減損術(shù)運(yùn)算簡(jiǎn)易，卻步驟較多，在解題時(shí)應(yīng)靈活運(yùn)用.知識(shí)點(diǎn)二利用函數(shù)與方程思想——二分法解題例2已知x5+x4+2x3—5x2+3x—1=0在區(qū)間［0，1］上有唯一的實(shí)數(shù)根。試求出根的近似值。要求：(1)用偽代碼表示算法；(2)根的誤差的絕對(duì)值要小于0。005。思路分析：回顧二分法解方程的過(guò)程，并假設(shè)所求近似值與精確解的差的絕對(duì)值不超過(guò)0。005.這就是循環(huán)語(yǔ)句的終止條件。解:S1S2b←1；S3S4x0←(a+b)/2;S5f（a)←a5+a4+2a3—5a2S6f（x0）←x05+x04+2x03-5x02S7Iff（x0）=0ThenGoTo140；S8Iff（a）f（x0）<0Then；S9b←x0;S10Else;S11aS12EndIf;S13If|a—b|≥cThenGoTo4;S14Printx0。方法歸納對(duì)于給定的一元方程f（x)=0，要求精確度為ε的近似解的算法如下：1。確定有解區(qū)間［a,b］（f(a）·f(b)<0)。2。取[a，b］的中點(diǎn).3.計(jì)算函數(shù)f(x)在中點(diǎn)處的函數(shù)值f(）。4。判斷函數(shù)值f（）是否為0.(1）如果為0,x=就是方程的解，問(wèn)題就得到了解決。(2)如果函數(shù)值f（)不為0,則分下列兩種情況:①若f(a)·f(）<0,則確定新的有解區(qū)間為(a,）;②若f（a）·f(）＞0，則確定新的有解區(qū)間為(，b）。5.判斷新的有解區(qū)間的長(zhǎng)度是否小于誤差ε:（1)如果新的有解區(qū)間長(zhǎng)度大于誤差ε,則在新的有解區(qū)間的基礎(chǔ)上重復(fù)上述步驟；(2)如果新的有解區(qū)間長(zhǎng)度小于或等于誤差ε，則取新的有解區(qū)間的中點(diǎn)為方程的近似解.深化升華（1）循環(huán)變量和初始條件設(shè)兩個(gè)變量a，b，分別表示有解區(qū)間的左端點(diǎn)和右端點(diǎn),初始值分別為0和1。（2）循環(huán)體算法中反復(fù)執(zhí)行的部分是判斷函數(shù)值f（）是否為0:①如果f（)=0,輸出。②如果f（)不為0，則判斷f(a）·f()的符號(hào)：（ⅰ）如果f(a)·f（)<0,b←；(ⅱ)如果f（a)·f()＞0，a←.(3)終止條件①f(）=0；②b-a〈ε.誤區(qū)警示將終止條件b-a〈ε當(dāng)成循環(huán)體是錯(cuò)誤的.問(wèn)題·探究交流討論探究問(wèn)題如何求兩個(gè)數(shù)的最大公約數(shù)，有幾種方法？探究過(guò)程：同學(xué)甲：可用輾轉(zhuǎn)相除法與更相減損術(shù)。輾轉(zhuǎn)相除法的理論根據(jù)是：由m=nq+r可以看出，m,n和n，r有相同的公約數(shù)。更相減損術(shù)的理論依據(jù)為:由m-n=r，得m=n+r,可以看出，m,n與n，r有相同的公約數(shù)，即二者的“算理"相似.同學(xué)乙:輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：（1）都是求最大公約數(shù)的方法,計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減