2024-2025學(xué)年高中數(shù)學(xué)第二章算法初步2.1算法的基本思想學(xué)案北師大版必修3

PAGE1-2.1算法的基本思想[航向標(biāo)·學(xué)習(xí)目標(biāo)]1．理解算法的概念與特點(diǎn)．2．學(xué)會(huì)用自然語(yǔ)言描述算法．3．通過(guò)解決詳細(xì)問(wèn)題的實(shí)例感受理解算法的特點(diǎn)，體會(huì)算法的基本思想，學(xué)會(huì)借助已有數(shù)學(xué)問(wèn)題的解決方法和步驟設(shè)計(jì)算法．[讀教材·自主學(xué)習(xí)]1．算法的概念：算法是指依據(jù)肯定規(guī)則解決某一類問(wèn)題的明確的過(guò)程和有限的eq\o(□,\s\up1(01))步驟，算法具有如下特點(diǎn)：(1)eq\o(□,\s\up1(02))明確性：即每一個(gè)算法都有明確的目的．(2)eq\o(□,\s\up1(03))有效性：即我們所設(shè)計(jì)的算法必需是有效的，并在有限步的操作后解決問(wèn)題．(3)eq\o(□,\s\up1(04))邏輯性：即我們?cè)O(shè)計(jì)的算法要符合邏輯規(guī)律，能從頭到尾運(yùn)行下去．(4)eq\o(□,\s\up1(05))普遍性：我們所設(shè)計(jì)的算法必需能夠解決一類問(wèn)題，而不是某一個(gè)問(wèn)題．(5)eq\o(□,\s\up1(06))不唯一性：算法不是唯一的，可有另外不同的設(shè)計(jì)方法．2．排序：為了便于查詢和檢索，我們經(jīng)常依據(jù)某種要求把被查詢的對(duì)象用數(shù)字(或者符號(hào))表示出來(lái)，并把數(shù)字按大小eq\o(□,\s\up1(07))排列，是信息處理中一項(xiàng)基本的工作，通常稱為排序．3．有序列：按eq\o(□,\s\up1(08))依次排列的數(shù)據(jù)列為有序列．[看名師·疑難剖析]1．對(duì)算法含義的理解(1)算法是機(jī)械的算法的設(shè)計(jì)要“四平八穩(wěn)”不能省略任何一個(gè)小小的步驟，有時(shí)可能要進(jìn)行大量重復(fù)計(jì)算，但只要按步驟一步一步地執(zhí)行，總能得到結(jié)果．算法的這種機(jī)械化的特點(diǎn)，在設(shè)計(jì)出算法后，便于把詳細(xì)過(guò)程交給計(jì)算機(jī)去完成．(2)算法是普遍存在的事實(shí)上處理任何問(wèn)題都須要算法，如國(guó)際象棋的棋譜、走法、輸贏的評(píng)判標(biāo)準(zhǔn)，郵寄物品的相關(guān)手續(xù)，求一個(gè)二元一次方程組的解等等．(3)求解某個(gè)詳細(xì)問(wèn)題的算法一般是不唯一的算法事實(shí)上是解決問(wèn)題的步驟和方法，求解問(wèn)題的動(dòng)身點(diǎn)不同，就會(huì)得到不同的算法．如求二元一次方程組的解有代入消元法和加減消元法，但不同的算法可能會(huì)有“優(yōu)劣”之分．2．算法與數(shù)學(xué)問(wèn)題解法的區(qū)分與聯(lián)系(1)聯(lián)系算法與解法是一般與特別的關(guān)系，也是抽象與詳細(xì)的關(guān)系．如，由詳細(xì)的二元一次方程組的求解過(guò)程(解法)動(dòng)身，歸納出了二元一次方程組求解的步驟；同時(shí)指出，這樣的求解步驟也適合有限制條件的二元一次方程組，這些步驟就構(gòu)成了二元一次方程組的算法．算法的獲得要借助一般意義上詳細(xì)問(wèn)題的求解方法，而任何一個(gè)詳細(xì)問(wèn)題都可利用這類問(wèn)題的一般算法解決．(2)區(qū)分算法是解決某一類問(wèn)題所須要的程序和步驟的統(tǒng)稱，也可理解為數(shù)學(xué)中的“通法通解”；而解法是解決某一個(gè)詳細(xì)問(wèn)題的過(guò)程和步驟，是詳細(xì)的解題過(guò)程．考點(diǎn)一算法的概念例1下列關(guān)于算法的描述正確的是()A．算法與求解一個(gè)問(wèn)題的方法相同B．算法只能解決一個(gè)問(wèn)題，不能重復(fù)運(yùn)用C．算法過(guò)程要一步一步執(zhí)行，每步執(zhí)行的操作必需準(zhǔn)確D．有的算法執(zhí)行完后，可能無(wú)結(jié)果[分析]由題目可獲得以下主要信息：①給出的四個(gè)選項(xiàng)均與算法含義和特點(diǎn)有關(guān)；②對(duì)各選項(xiàng)要做正誤推斷．解答本題要先弄清晰算法的含義和特點(diǎn)，然后逐一判定選項(xiàng)命題的真假即可．[解析]算法與求解一個(gè)問(wèn)題的方法既有區(qū)分又有聯(lián)系，故A不對(duì)；算法能重復(fù)運(yùn)用，故B不對(duì)；每個(gè)算法執(zhí)行后必需有結(jié)果，故D不對(duì)；由算法的有序性和確定性可知C正確．[答案]C類題通法算法事實(shí)上是解決問(wèn)題的一種程序性方法，它通常指向某一個(gè)或一類問(wèn)題，而解決的過(guò)程是程序性和構(gòu)造性的.算法也可以看成解決問(wèn)題的特別的、有效的方法.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練1])下列關(guān)于算法的說(shuō)法，正確的有()①求解某一類問(wèn)題的算法是唯一的；②算法必需在有限步操作之后停止；③算法的每一步操作必需是明確的，不能有歧義和模糊；④算法執(zhí)行后肯定產(chǎn)生確定的結(jié)果．A．1個(gè)B．2個(gè)C．3個(gè)D．4個(gè)答案C解析本題是在嫻熟駕馭算法概念的基礎(chǔ)上的一個(gè)躍升，即對(duì)算法概念進(jìn)行進(jìn)一步的挖掘，理解其內(nèi)涵．從而借助概念分析、解決問(wèn)題．由于算法具有有窮性、確定性和可執(zhí)行性，因而②③④正確．解決問(wèn)題的算法不肯定是唯一的，從而①錯(cuò)，故選C.考點(diǎn)二數(shù)值計(jì)算問(wèn)題的算法設(shè)計(jì)例2寫出一個(gè)算法，求二元一次方程組eq\b\lc\{\rc\(\a\vs4\al\co1(a1x＋b1y＝c1，①,a2x＋b2y＝c2'②))的解．[分析]聯(lián)系該方程組的實(shí)際解法過(guò)程，但要留意對(duì)待定系數(shù)的分類探討．因?yàn)槭嵌淮畏匠探M，所以a1、a2不能同時(shí)為0，b1，b2也不能同時(shí)為0.[解]算法如下：1.若a1≠0，由①×eq\b\lc\(\rc\)(\a\vs4\al\co1(－\f(a2,a1)))＋②，得到eq\b\lc\(\rc\)(\a\vs4\al\co1(b2－\f(a2b1,a1)))y＝c2－eq\f(a2c1,a1).即方程組化為eq\b\lc\{\rc\(\a\vs4\al\co1(a1x＋b1y＝c1，①,a1b2－a2b1y＝a1c2－a2c1.③))2．若a1b2－a2b2≠0，解③得y＝eq\f(a1c2－a2c1,a1b2－a2b1).④3.將④代入①，整理得x＝eq\f(b2c1－b1c2,a1b2－a2b1).4.輸出結(jié)果x，y.5.假如a1b2－a2b1＝0，從③可以看出，方程組無(wú)解或有無(wú)窮多組解．6.假如a1＝0，則b1≠0，所以y＝eq\f(c1,b1).⑤7.將⑤代入②，得x＝eq\f(b1c2－b2c1,a2b1).8.輸出結(jié)果x，y.類題通法對(duì)于設(shè)計(jì)數(shù)值計(jì)算問(wèn)題的算法，可以借助數(shù)學(xué)的常規(guī)解法或數(shù)學(xué)公式，將過(guò)程分解成清晰的步驟，使之條理化，但應(yīng)留意多個(gè)數(shù)進(jìn)行四則運(yùn)算時(shí)應(yīng)分步計(jì)算，依次進(jìn)行，直到算出結(jié)果.本題中，把解方程組的過(guò)程轉(zhuǎn)化為算法的步驟，應(yīng)用了數(shù)學(xué)的轉(zhuǎn)化思想.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練2])寫出解方程x2－2x－3＝0的一個(gè)算法．解解法一：第一步，移項(xiàng)，得x2－2x＝3.①其次步，①兩邊同加1并配方，得(x－1)2＝4.②第三步，②式兩邊開方，得x－1＝±2.③第四步，解③，得x＝3或x＝－1.解法二：第一步，計(jì)算方程的判別式并推斷其符號(hào)：Δ＝22＋4×3＝16>0.其次步，將a＝1，b＝－2，c＝－3代入求根公式x＝eq\f(－b±\r(b2－4ac),2a)，得x1＝3，x2＝－1.考點(diǎn)三推斷性問(wèn)題的算法設(shè)計(jì)例3設(shè)計(jì)一個(gè)算法，推斷7是否為質(zhì)數(shù)．[分析]只能被1和自身整除的大于1的整數(shù)叫質(zhì)數(shù)．因而要推斷一個(gè)數(shù)是否為質(zhì)數(shù)，只需用比這個(gè)數(shù)小的任一個(gè)大于1的整數(shù)來(lái)除該數(shù)，然后利用余數(shù)是否為0來(lái)推斷．[解]算法步驟如下：(1)用2除7，得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以2不能整除7.(2)用3除7，得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以3不能整除7.(3)用4除7，得到余數(shù)3.因?yàn)橛鄶?shù)不為0，所以4不能整除7.(4)用5除7，得到余數(shù)2.因?yàn)橛鄶?shù)不為0，所以5不能整除7.(5)用6除7，得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以6不能整除7.(6)推斷7是否為質(zhì)數(shù)：7是質(zhì)數(shù)．類題通法從本例可以看出，本類問(wèn)題的算法具有很強(qiáng)的機(jī)械重復(fù)性，因而對(duì)于隨意給定一個(gè)大于2的整數(shù)n，我們推斷它是否為質(zhì)數(shù)的算法為：第一步：令i＝2.其次步，用i除n，得余數(shù)r.第三步，推斷“r＝0”是否成立，若是，則n不是質(zhì)數(shù)，結(jié)束算法；否則，將i的值增加1，仍用i表示.第四步，推斷“i>n－1”是否成立，若是，則n是質(zhì)數(shù)，結(jié)束算法；否則，返回其次步.分步處理是本類問(wèn)題的特色，也是算法思想的重要體現(xiàn).eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練3])設(shè)計(jì)算法，將1260分解成素因數(shù)的乘積．解算法步驟如下：(1)推斷1260是否為素?cái)?shù)：否．(2)確定1260的最小素因數(shù)：2.1260＝2×630.(3)推斷630是否為素?cái)?shù)：否．(4)確定630的最小素因數(shù)：2.630＝2×315.(5)推斷315足否為素?cái)?shù)：否．(6)確定315的最小素因數(shù)：3.315＝3×105.(7)推斷105是否為素?cái)?shù)：否．(8)確定105的最小素因數(shù)：3.105＝3×35.(9)推斷35是否為素?cái)?shù)：否．(10)確定35的最小素因數(shù)：5.35＝5×7.(11)推斷7是否為素?cái)?shù)：7是素?cái)?shù)，所以分解結(jié)束．分解結(jié)果是：1260＝2×2×3×3×5×7.考點(diǎn)四關(guān)于整除性問(wèn)題的算法設(shè)計(jì)例4設(shè)計(jì)一個(gè)算法，求1764與840的最大公約數(shù)．[分析]首先，將兩個(gè)數(shù)分別進(jìn)行素因數(shù)分解，1764＝22×32×72,840＝23×3×5×7.其次，確定兩個(gè)數(shù)的公共素因數(shù)2,3,7.接著，確定公共素因數(shù)的指數(shù)：對(duì)于公共素因數(shù)2,22是1764的因數(shù)，23是840的因數(shù)，因此22是這兩個(gè)數(shù)的公因數(shù)，同樣可以確定公因數(shù)3和7的指數(shù)均為1.這樣就確定了1764與840的最大公因數(shù)為22×3×7＝84.[解]算法步驟如下：(1)將1764進(jìn)行素因數(shù)分解，1764＝22×32×72.(2)將840進(jìn)行素因數(shù)分解，840＝23×3×5×7.(3)確定它們的公共素因數(shù)為2,3,7.(4)確定公共素因數(shù)的指數(shù)．公共素因數(shù)2,3,7的指數(shù)分別為2,1,1.(5)最大公因數(shù)為22×31×71＝84.類題通法1正確理解算法的概念，一個(gè)程序的算法要本著便利簡(jiǎn)捷的原則，還要講求科學(xué)性，算法的步驟是依據(jù)肯定依次進(jìn)行的，不具有可逆性.,2在設(shè)計(jì)算法的過(guò)程當(dāng)中要堅(jiān)固把握住它的五個(gè)特性：有限性、確定性、可行性、輸入、輸出.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練4])求8251與6105的最大公因數(shù)．解算法步驟如下：(1)先將8251進(jìn)行素因數(shù)分解：8251＝37×223；(2)然后將6105進(jìn)行素因數(shù)分解：6105＝3×5×11×37；(3)確定它們的公共素因數(shù)：37；(4)確定公共素因數(shù)的指數(shù)：1；(5)最大公因數(shù)為37.考點(diǎn)五排序問(wèn)題的算法設(shè)計(jì)例5對(duì)于有序列{32,36,50,56,81}，現(xiàn)在要將數(shù)據(jù)51插入到有序列中．請(qǐng)?jiān)O(shè)計(jì)算法確定數(shù)據(jù)51在有序列中的位置，并用自然語(yǔ)言描述算法．[分析]我們可以將51與有序列中的數(shù)據(jù)從右到左依次進(jìn)行比較，來(lái)確定51在有序列中的位置，也可以將51與有序列中的數(shù)據(jù)從左向右依次進(jìn)行比較，來(lái)確定51在有序列中的位置．[解]將51與有序列中的數(shù)據(jù)從右向左逐個(gè)進(jìn)行比較，從而確定51在有序列中的位置．其算法如下：1.比較51與81,51<81.2.比較51與56,51<56.3.比較51與50,51>50.4.將51插入到56和50之間，得到一個(gè)新的有序列{32,36,50,51,56,81}．類題通法本例的排序算法是有序列干脆插入排序，解決本類問(wèn)題也可以用折半插入排序法進(jìn)行.eq\a\vs4\al()eq\a\vs4\al([變式訓(xùn)練5])將52插入有序列{13,27,38,39,43,47,48,51,57,66,74,82}中，構(gòu)成一個(gè)新的有序列．解首先選擇有序列中具有中間位置序號(hào)的數(shù)據(jù)47，將52與47進(jìn)行比較，明顯52>47，故52不能插入到47的左邊的任何位置．所以，應(yīng)當(dāng)排在47的右邊，再將余下數(shù)據(jù)的中間位置的數(shù)據(jù)57與52比較，明顯52<57，因此應(yīng)插到57的左邊，又51<52，則52插入到51的右邊，57的左邊，即可得到52的位置.考點(diǎn)六實(shí)際問(wèn)題的算法設(shè)計(jì)例6漢諾塔問(wèn)題：如圖三根柱子，甲柱上從大到小放置了三個(gè)圓環(huán)A、B、C，現(xiàn)在要將這三個(gè)圓環(huán)移至乙柱，也要從大到小放置．要求一次移動(dòng)一個(gè)，移動(dòng)過(guò)程中，大圓環(huán)不能放于小圓環(huán)上，應(yīng)如何移動(dòng)？[分析]這是一個(gè)古典的數(shù)學(xué)問(wèn)題．要把甲柱的n個(gè)環(huán)移到乙柱，必需先把上面的n－1個(gè)環(huán)移到丙柱，然后把第n個(gè)環(huán)移到乙柱，最終再把丙柱的第n－1個(gè)環(huán)移過(guò)來(lái)．解決n個(gè)環(huán)的問(wèn)題，先要解決n－1個(gè)環(huán)的問(wèn)題，而這個(gè)問(wèn)題與前一個(gè)是類似的，可以用相同的方法解決．最終，得到只有一個(gè)環(huán)的狀況，很簡(jiǎn)潔，干脆把環(huán)從甲柱移到乙柱即可．[解]假如移動(dòng)一次算一步，則可按以下步驟進(jìn)行：第一步，將C環(huán)移至乙柱．其次步，將B環(huán)移至丙柱．第三步，將C環(huán)移至丙柱．第四步，將A環(huán)移至乙柱．第五步，將C環(huán)移至甲柱．第六步，將B環(huán)移至乙柱．第七步，將C環(huán)移至乙柱．eq\a\vs4\al([變式訓(xùn)練6])一個(gè)人帶著三只狼和三只羊過(guò)河，只有一條船，該船可容納一個(gè)人和兩只動(dòng)物；沒有人在的時(shí)候，假如狼的數(shù)量不少于羊的數(shù)量，狼就會(huì)吃羊，該人如何能將動(dòng)物轉(zhuǎn)移過(guò)河？請(qǐng)?jiān)O(shè)計(jì)算法．解第一步，人帶兩只狼過(guò)河，并自己返回；其次步，人帶一只狼過(guò)河，自己返回；第三步，人帶兩只羊過(guò)河，并帶兩只狼返回；第四步，人帶一只羊過(guò)河，自己返回；第五步，人帶兩只狼過(guò)河．規(guī)范解答分段函數(shù)的算法設(shè)計(jì)[例](12分)已知分段函數(shù)f(x)＝eq\b\lc\{\rc\(\a\vs4\al\co1(x2－1，－1≤x≤1，,lnx，x>1，))請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，輸入隨意一個(gè)不小于－1的實(shí)數(shù)x0，輸出相應(yīng)的f(x0)的值．(一)精妙思路點(diǎn)撥(二)分層規(guī)范細(xì)解1．輸入x0；3分2.eq\a\vs4\al(若x0<－1)①，則輸出“輸入的數(shù)據(jù)有誤”，結(jié)束算法，否則執(zhí)行第3步；6分3．若－1≤x0≤1，則f(x0)＝xeq\o\al(2,0)－1，否則f(x0)＝lnx0；9分4.eq\a\vs4\al(輸出fx0的值)②，結(jié)束算法.12分(三)來(lái)自一線的報(bào)告通過(guò)閱卷后分析，對(duì)解答本題的失分警示和解題啟示總結(jié)如下：(注：此處的①②見分層規(guī)范細(xì)解過(guò)程)(四)類題練筆駕馭已知函數(shù)f(x)＝eq\b\lc\{\rc\(\a\vs4\al\co1(2x－1，x≤1，,\r(x)，1<x≤4，,x－2，x>4.))解1.輸入x0；2．若x0≤1，則計(jì)算f(x0)＝2x0－1，否則執(zhí)行第3步；3．若x0≤4，則計(jì)算f(x0)＝eq\r(x0)，否則執(zhí)行第4步；4．計(jì)算f(x0)＝x0－2；5．輸出f(x0)的值，結(jié)束算法．(五)解題設(shè)問(wèn)解答本題時(shí)，需對(duì)誰(shuí)進(jìn)行分類探討？________.答案自變量x1.以下給出關(guān)于算法的幾種說(shuō)法，其中正確的是()A．算法就是某一個(gè)問(wèn)題的解題方法B．對(duì)于給定的一個(gè)問(wèn)題，其算法不肯定是唯一的C．一個(gè)算法可以不產(chǎn)生確定的結(jié)果D．算法的步驟可以無(wú)限地執(zhí)行下去不停止答案B解析算法是做某一件事