蘇教版數(shù)學(xué)必修三講義第1章1.4算法案例Word版含答案

1.4算法案例學(xué)習(xí)目標(biāo)核心素養(yǎng)1.通過中國(guó)古代算法案例，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)．2．能綜合運(yùn)用所學(xué)的算法知識(shí)解決實(shí)際問題，會(huì)用自然語言、流程圖和偽代碼表述問題的算法過程．(重點(diǎn)、難點(diǎn))3．拓展視野，進(jìn)一步感受算法的意義和價(jià)值.通過算法案例，培養(yǎng)學(xué)生發(fā)現(xiàn)、探索問題的能力，通過抽象、概括把實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)問題，提升學(xué)生的數(shù)學(xué)抽象、數(shù)學(xué)建模以及邏輯推理的數(shù)學(xué)核心素養(yǎng).1．“孫子問題”是求關(guān)于x，y，z的一次不定方程組eq\b\lc\{\rc\(\a\vs4\al\co1(m＝3x＋2，,m＝5y＋3，,m＝7z＋2))的正整數(shù)解．2．輾轉(zhuǎn)相除法和更相減損術(shù)(1)歐幾里得輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)a，b的最大公約數(shù)的步驟是：計(jì)算出a÷b的余數(shù)r，若r＝0，則b即為a，b的最大公約數(shù)；若r≠0，則把前面的除數(shù)b作為新的被除數(shù)，把余數(shù)r作為新的除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時(shí)的除數(shù)即為a，b的最大公約數(shù)．(2)“更相減損術(shù)”是我國(guó)的《九章算術(shù)》中提到的一種求兩個(gè)正數(shù)最大公約數(shù)的算法，它與“輾轉(zhuǎn)相除法”相似．它的基本思想是：對(duì)于給定的兩個(gè)數(shù)，以兩個(gè)數(shù)中較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)組成一對(duì)新數(shù)，再用兩個(gè)數(shù)中較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到產(chǎn)生一對(duì)相等的數(shù)為止，這個(gè)數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)．3．Int(x)和Mod(x)函數(shù)(1)Int(x)表示不超過x的最大整數(shù)．例如：Int(5)＝5，Inteq\b\lc\(\rc\)(\a\vs4\al\co1(\f(2,3)))＝0，Int(3.6)＝3.(2)Mod(a，b)的意義是a除以b所得的余數(shù)，因此當(dāng)Mod(a，b)＝0時(shí)，表示a能被b整除，當(dāng)0<Mod(a，b)<b時(shí)，a不能被b整除，即b不是a的約數(shù)．4．利用“二分法”求方程f(x)＝0在區(qū)間[a，b]上的近似解的步驟S1取[a，b]的中點(diǎn)x0＝eq\f(1,2)(a＋b)，將區(qū)間一分為二；S2若f(x0)＝0，則x0就是方程的根；否則判斷根x*在x0的左側(cè)還是右側(cè)：若f(a)f(x0)>0，則x*∈(x0，b)，以x0代替a；若f(a)f(x0)<0，則x*∈(a，x0)，以x0代替b；S3若|a－b|<c，計(jì)算終止，此時(shí)x*≈x0，否則轉(zhuǎn)S1.1．兩個(gè)整數(shù)490和910的最大公約數(shù)是________．70[∵910＝490×1＋420,490＝420×1＋70,420＝70×6＋0，∴490和910的最大公約數(shù)是70.]2．Mod(8,3)＝________.2[Mod(8,3)表示8除以3所得的余數(shù)．∵8＝2×3＋2，∴Mod(8,3)＝2.]3．若Int(x)表示不超過x的最大整數(shù)，對(duì)于下列等式：①Int(10.01)＝10；②Int(－1)＝－1；③Int(－5.2)＝－5.其中正確的有________個(gè)．2[①②正確，③錯(cuò)誤．因?yàn)镮nt(x)表示的是不超過x的最大整數(shù)．所以Int(－5.2)＝－6.]4．用二分法求方程的近似解，誤差不超過ε，則循環(huán)結(jié)構(gòu)的終止條件是________．①|(zhì)x1－x2|>ε；②x1＝x2＝ε；③x1<ε<x2；④|x1－x2|<ε.④[依據(jù)用二分法求方程近似解時(shí)誤差限制要求判斷，④對(duì)．]孫子剩余定理的應(yīng)用【例1】有3個(gè)連續(xù)的正整數(shù)，其中最小的能被15整除，中間的能被17整除，最大的能被19整除，畫出求滿足要求的一組三個(gè)連續(xù)正整數(shù)的流程圖，并寫出偽代碼．思路點(diǎn)撥：設(shè)最小的正整數(shù)m，根據(jù)題意，m應(yīng)同時(shí)滿足3個(gè)條件：(1)m被15整除即Mod(m,15)＝0，(2)m＋1被17整除即Mod(m＋1,17)＝0，(3)m＋2被19整除即Mod(m＋2,19)＝0.首先，從m＝2開始檢驗(yàn)條件，若3個(gè)條件中有任何一個(gè)不滿足則m遞增1.直到m同時(shí)滿足3個(gè)條件時(shí)，輸出m，m＋1，m＋2.因?yàn)橐獜膍＝2開始反復(fù)驗(yàn)證，故需要用循環(huán)結(jié)構(gòu)．[解]流程圖：偽代碼：eq\x(\a\al(m←2,WhileMod(m,15)≠0or,Mod(m＋1,17)≠0or,Mod(m＋2,19)≠0,m←m＋1,EndWhile,Printm，m＋1，m＋2))解決此類問題的方法就是從m＝2開始，對(duì)每一個(gè)正整數(shù)逐一檢驗(yàn)，當(dāng)m滿足所有已知條件時(shí)，結(jié)束循環(huán)，輸出m.1．如圖所示的流程圖，輸出的結(jié)果是________．17[m＝10時(shí)，不滿足條件，則m←10＋7，m＝17時(shí)，Mod(m,3)＝2且Mod(m,5)＝2成立，故輸出17.]2．方程組eq\b\lc\{\rc\(\a\vs4\al\co1(3x＋4＝m，,2y＋1＝m))的整數(shù)解有________組．無數(shù)[消去m，得3x－2y＋3＝0，即x＝eq\f(2,3)y－1，只要y取3的整數(shù)倍，所得的解都符合題意．]求兩個(gè)正整數(shù)的最大公約數(shù)【例2】設(shè)計(jì)用輾轉(zhuǎn)相除法求8251與6105的最大公約數(shù)的算法，并畫出流程圖，寫出偽代碼．思路點(diǎn)撥：根據(jù)用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的算法步驟寫出解決此問題的算法，再轉(zhuǎn)換為流程圖和偽代碼．[解]算法如下：S1a←8251；S2b←6105；S3如果Mod(a，b)≠0，那么轉(zhuǎn)S4，否則轉(zhuǎn)S7；S4r←Mod(a，b)；S5a←b；S6b←r，轉(zhuǎn)S3；S7輸出B．流程圖與偽代碼：eq\x(\a\al(a←8251,b←6105,WhileModa，b≠0,r←Moda，b,a←b,b←r,EndWhile,Printb))輾轉(zhuǎn)相除法是用于求兩個(gè)數(shù)的最大公約數(shù)的一種方法，這種方法由歐幾里得在公元前300年左右首先提出，因而又叫“歐幾里得輾轉(zhuǎn)相除法”．輾轉(zhuǎn)相除法的算法步驟(以求兩個(gè)正整數(shù)a，b(a>b)的最大公約數(shù)為例)為：S1輸入兩個(gè)正整數(shù)a，b；S2如果Mod(a，b)≠0，那么轉(zhuǎn)S3，否則，轉(zhuǎn)S6；S3r←Mod(a，b)；S4a←b；S5b←r，轉(zhuǎn)S2；S6輸出B．其流程圖如圖：偽代碼為：eq\x(\a\al(Reada，b,WhileModa，b≠0,r←Moda，b,a←b,b←r,EndWhile,Printb))提醒：求兩個(gè)正整數(shù)的最大公約數(shù)時(shí)，用輾轉(zhuǎn)相除法進(jìn)行設(shè)計(jì)的關(guān)鍵是：將“輾轉(zhuǎn)”的過程用循環(huán)語句表示．為了避免求循環(huán)次數(shù)(對(duì)兩個(gè)具體的正整數(shù)，循環(huán)次數(shù)可以求出，但會(huì)使程序更為復(fù)雜)，最好使用“While”語句．3．用輾轉(zhuǎn)相除法求261和319的最大公約數(shù)．[解]319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319與261的最大公約數(shù)為29.4．運(yùn)行下面?zhèn)未a，當(dāng)輸入168,72時(shí)輸出的結(jié)果是__________．eq\x(\a\al(Readm，n,Do,r←Modm，n,m←n,n←r,Untilr＝0,EndDo,Printm))24[偽代碼是求168與72的最大公約數(shù)．]二分法求方程的近似解【例3】設(shè)計(jì)用二分法求方程x3－2＝0在區(qū)間[1,2]內(nèi)的近似解(誤差不超過0.005)的流程圖，寫出偽代碼．思路點(diǎn)撥：依據(jù)二分法求方程的近似解的步驟設(shè)計(jì)出算法再轉(zhuǎn)換成流程圖和偽代碼，設(shè)f(x)＝x3－2如圖所示．如果估計(jì)出方程f(x)＝0在某區(qū)間[a，b]內(nèi)有一個(gè)根x*，就能用二分法搜索求得符合誤差限制c的近似解．用自然語言表示算法如下：S1取[a，b]的中點(diǎn)x0＝eq\f(1,2)(a＋b)，將區(qū)間一分為二；S2若f(x0)＝0，則x0就是方程的根，否則判斷根x*在x0的左側(cè)還是右側(cè)；若f(a)f(x0)>0，則x*∈(x0，b)，以x0代替a；若f(a)f(x0)<0，則x*∈(a，x0)，以x0代替b；S3若|a－b|<c，計(jì)算終止，此時(shí)x*≈x0，否則轉(zhuǎn)S1.[解]流程圖如圖所示：偽代碼如下：eq\x(\a\al(a←1,b←2,c←0.005,Dox0←a＋b/2,fa←a3－2,fx0←x\o\al(3,0)－2,Iffx0＝0ThenExitDo,Iffa*fx0<0Then,b←x0,Else,a←x0,EndIf,Until|a－b|<c,EndDo,Printx0))1．用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解．2．二分法的過程是一個(gè)多次重復(fù)的過程，故可用循環(huán)結(jié)構(gòu)處理．3．二分法過程中需要對(duì)中點(diǎn)(端點(diǎn))處函數(shù)值的符號(hào)進(jìn)行判定，故實(shí)現(xiàn)算法需用選擇結(jié)構(gòu)，即用條件語句進(jìn)行分支選擇．5．用區(qū)間二分法求出方程3x＝5－x在區(qū)間[1,2]上的近似解(誤差不超過0.001)，并寫出這個(gè)算法的偽代碼，畫出流程圖．[解]設(shè)f(x)＝3x＋x－5.偽代碼如下：eq\x(\a\al(a←1,b←2,c←0.001,Do,x0←a＋b/2,fa←3a＋a－5,fx0←3x0＋x0－5,Iffx0＝0ThenExitDo,Iffafx0＜0Then,b←x0,Else,a←x0,EndIf,Until|a－b|＜c,EndDo,Printx0))其流程圖如圖所示：1．本節(jié)課重點(diǎn)是會(huì)用孫子定理求一次不定方程組的解，會(huì)求兩個(gè)數(shù)的最大公約數(shù)，用二分法求方程的近似解．2．求最大公約數(shù)的兩種方法步驟(1)利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)．(2)利用更相減損術(shù)求兩個(gè)正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個(gè)正整數(shù)是否都是偶數(shù)．若是，用2約簡(jiǎn)，也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果.1．有一堆火柴棒，三根三根地?cái)?shù)，最后余下一根；四根四根地?cái)?shù)，最后余下兩根；五根五根地?cái)?shù)，最后余下四根．那么這堆火柴棒最少根數(shù)為()A．31 B．34C．44 D．54B[由題意知，本題實(shí)際上是求關(guān)于a，b，c的不定方程組的正整數(shù)解，即eq\b\lc\{\rc\(\a\vs4\al\co1(m＝3a＋1，,m＝4b＋2，,m＝5c＋4，))得m的最小值為34.]2．4557與5115的最大公約數(shù)是________．93[因?yàn)?115＝4557×1＋558，4557＝558×8＋93,558＝93×6，所以4557與5115的最大公約數(shù)是93.]3．Mod(100,17)＝________.15[Mod(a，b)＝c表示b除a所得余數(shù)為C．100＝17×5＋15，故余數(shù)為15.]4．根據(jù)如圖所示的流程圖(其中[x]表示不大于x的最大整數(shù))，可知輸出r＝________.eq\f(7,3)[由流程圖的算法原理可知：a＝