必修31.11算法的概念課件蘇教版

1.1.1算法的概念課程目標(biāo)講授新課課堂作業(yè)退出課堂練習(xí)課堂小結(jié)題型探究新課引入封底數(shù)學(xué)必修③課程目標(biāo)初步建立算法的概念；讓學(xué)生通過(guò)豐富的實(shí)例體會(huì)算法的思想；讓學(xué)生通過(guò)對(duì)具體問(wèn)題的探究，初步了解算法的含義.算法的含義及應(yīng)用.通過(guò)實(shí)例體會(huì)算法思想，初步了解算法的含義.【教學(xué)重點(diǎn)】【教學(xué)目標(biāo)】【教學(xué)難點(diǎn)】

在中央電視臺(tái)幸運(yùn)52節(jié)目中,有一個(gè)猜商品價(jià)格的環(huán)節(jié),竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出某種商品的價(jià)格,就可獲得該件商品.現(xiàn)有一商品,價(jià)格在0~8000元之間,采取怎樣的策略才能在較短的時(shí)間內(nèi)說(shuō)出正確(大體上)的答案呢?第一步:報(bào)“4000”；第二步:若主持人說(shuō)高了(說(shuō)明答案在0~4000之間),就報(bào)“2000”,否則(答數(shù)在4000~8000之間)報(bào)“6000”；新課引入

一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解過(guò)程稱為算法(algorithm)它是解決某一問(wèn)題的程序或步驟.

按照這樣的理解,我們可以設(shè)計(jì)出很多具體數(shù)學(xué)問(wèn)題的算法.下面看幾個(gè)例子:第三步:重復(fù)第二步的報(bào)數(shù)方法取中間數(shù),直至得到正確結(jié)果.

所謂“算法”就是解題方法的精確描述.從更廣義的角度來(lái)看,并不是只有“計(jì)算”的問(wèn)題才有算法,日常生活中處處都有.如樂(lè)譜是樂(lè)隊(duì)演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤的算法.【1】一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜要過(guò)河,但只有一條小船.乘船時(shí),農(nóng)夫只能帶一樣?xùn)|西.當(dāng)農(nóng)夫在場(chǎng)的時(shí)候,這三樣?xùn)|西相安無(wú)事.一旦農(nóng)夫不在,狼會(huì)吃羊,羊會(huì)吃菜.請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法,使農(nóng)夫能安全地將這三樣?xùn)|西帶過(guò)河.第一步:農(nóng)夫帶羊過(guò)河;第二步:農(nóng)夫獨(dú)自回來(lái);第三步:農(nóng)夫帶狼過(guò)河;第四步:農(nóng)夫帶羊回來(lái);第五步:農(nóng)夫帶蔬菜過(guò)河;第六步:農(nóng)夫獨(dú)自回來(lái);第七步:農(nóng)夫帶羊過(guò)河.【2】給出求1+2+3+4+5+6的一個(gè)算法.解法1.按照逐一相加的程序進(jìn)行.第一步:計(jì)算1+2,得3;第二步:將第一步中的運(yùn)算結(jié)果3與3相加得6;第三步:將第二步中的運(yùn)算結(jié)果6與4相加得10;第四步:將第三步中的運(yùn)算結(jié)果10與5相加得15;第五步:將第四步中的運(yùn)算結(jié)果15與6相加得21.解法2.可以運(yùn)用下面公式直接計(jì)算.第一步:取n=6;第二步:計(jì)算;第三步:輸出計(jì)算結(jié)果.點(diǎn)評(píng):解法1繁瑣,步驟較多;解法2簡(jiǎn)單，步驟較少.找出好的算法是我們的追求目標(biāo).

在數(shù)學(xué)中，現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成.2.算法的要求(1)寫出的算法,必須能解決一類問(wèn)題(例如解任意一個(gè)二元一次方程組),并且能重復(fù)使用;(2)算法過(guò)程要能一步一步執(zhí)行,每一步執(zhí)行的操作,必須確切,不能含混不清,而且在有限步之內(nèi)完成后能得出結(jié)果.1.算法的定義講授新課3.算法的基本特征:明確性:算法對(duì)每一個(gè)步驟都有確切的、非二義性的規(guī)定,即每一步對(duì)于利用算法解決問(wèn)題的人或計(jì)算機(jī)來(lái)說(shuō)都是可讀的、可執(zhí)行的,而不需要計(jì)算者臨時(shí)動(dòng)腦筋.有效性:算法的每一個(gè)步驟都能夠通過(guò)基本運(yùn)算有效地進(jìn)行,并得到確定的結(jié)果；對(duì)于相同的輸入,無(wú)論誰(shuí)執(zhí)行算法,都能夠得到相同的最終結(jié)果．講授新課有限性:算法應(yīng)由有限步組成,至少對(duì)某些輸入,算法應(yīng)在有限多步內(nèi)結(jié)束,并給出計(jì)算結(jié)果．3.算法的基本特征:信息輸出:一個(gè)算法至少要有一個(gè)有效的信息輸出,這就是問(wèn)題求解的結(jié)果.不唯一性:求解某一個(gè)題的解法不一定是唯一的,對(duì)于一個(gè)問(wèn)題可以有不同的算法.講授新課4.算法的描述:

描述算法可以有不同的方式,常用的有自然語(yǔ)言、程序框圖、程序設(shè)計(jì)語(yǔ)言、偽代碼等.數(shù)據(jù)輸入:算法一定要根據(jù)輸入的初始數(shù)據(jù)或給定的初值才能正確執(zhí)行它的每一步驟.

自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言,可以是漢語(yǔ)、英語(yǔ)或數(shù)學(xué)語(yǔ)言等.用自然語(yǔ)言描述算法的優(yōu)點(diǎn)是通俗易懂,當(dāng)算法中的操作步驟都是順序執(zhí)行時(shí)比較容易理解.缺點(diǎn)是如果算法中包含判斷和轉(zhuǎn)向,并且操作步驟較多時(shí),就不那么直觀清晰了.(1)自然語(yǔ)言(2)程序框圖(3)程序設(shè)計(jì)語(yǔ)言1.1.2程序框圖中講解1.2基本算法語(yǔ)句中講解例1.任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.第一步：判斷n是否等于2.若n=2，則n是質(zhì)數(shù)；若n>2，則執(zhí)行第二步.第二步:依次從2～（n－1）檢驗(yàn)是不是n的因數(shù)，即整除n的數(shù),若有這樣的數(shù)，則n不是質(zhì)數(shù)；若沒(méi)有這樣的數(shù)，則n是質(zhì)數(shù).評(píng)析:這是判斷一個(gè)大于1的整數(shù)n是否為質(zhì)數(shù)的最基本算法.講授新課例2.用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近似根的算法.第一步：令f(x)=x2-2，因?yàn)閒(1)<0，f(2)>0,所以設(shè)a=1,b=2.第二步：令m=,判斷f(m)是否為0.若是，則m為所求；若否，則繼續(xù)判斷f(a)·f(m)大于0還是小于0.算法分析:回顧二分法解方程的過(guò)程,并假設(shè)所求近似根與精確解的差的絕對(duì)值不超過(guò)0.005,則不難設(shè)計(jì)出以下步驟：講授新課第三步：若f(a)·f(m)>0，則令a=m；否則，令b=m.第四步:判斷|a-b|<0.005是否成立？若是，則a或b(或任意值)為滿足條件的近似根；若否，則返回第二步.評(píng)析:實(shí)際上,上述步驟就是在求的近似值.講授新課于是開區(qū)間中的實(shí)數(shù)都是滿足假設(shè)條件的原方程的近似根.

1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.第一步:輸入任意一個(gè)正實(shí)數(shù)r；第二步:計(jì)算圓的面積:S=πr2;第三步:輸出圓的面積S.課堂練習(xí)2.任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).第一步：依次以2~(n-1)為除數(shù)去除n,檢查余數(shù)是否為0,若是,則是n的因數(shù);若不是,則不是n的因數(shù).第二步：在n的因數(shù)中加入1和n.第三步：輸出n的所有因數(shù).課堂練習(xí)(P4練習(xí)2)3.你要乘火車去外地辦一件急事,請(qǐng)你寫出從自己房間出發(fā)到坐在車廂內(nèi)的三步主要算法.第一步:去車站；第二步:買車票;第三步:憑票上車對(duì)號(hào)入座.課堂練習(xí)【1】用自然語(yǔ)言描述求一元二次方程ax2+bx+c=0的根的算法.第一步:計(jì)算Δ=b2-4ac;第二步:如果Δ<0,則原方程無(wú)實(shí)數(shù)解;否則(Δ≥0)時(shí)，第三步:輸出x1,x2或無(wú)實(shí)數(shù)解的信息.1.解方程(方程組)不等式的算法題型探究【2】寫出解x2-4x+3<0的算法.第一步:求出對(duì)應(yīng)方程的根1,3;第二步:確定根的大小1<3;第三步:寫出解集{x|1<x<3}.題型探究【3】已知攝氏溫度C與華氏溫度的關(guān)系是,寫出由攝氏溫度求華氏溫度的算法.第一步：輸入攝氏溫度C;第二步：計(jì)算;第三步：輸出華氏溫度F.2.套用公式求值的算法題型探究第四步:計(jì)算;【4】試描述判斷圓(x-a)2+(y-b)2=r2和直線Ax+By+C=0位置關(guān)系的算法.第一步:輸入a,b,r,A,B,C;第二步:計(jì)算Z1=Aa+Bb+C;第三步:計(jì)算Z2=A2+B2;第五步:如果d>r,則相離;如果d=r,則相切;如果d<r,則相交.3.判斷性質(zhì)型問(wèn)題的算法題型探究【5】用自然語(yǔ)言描述求解mul=1×2×3×4×5×6問(wèn)題的算法.第一步:計(jì)算1×2,得2;第二步:將第一步中的運(yùn)算結(jié)果2與3相乘得6;第三步:將第二步中的運(yùn)算結(jié)果6與4相乘得24;第四步:將第三步中的運(yùn)算結(jié)果24與5相乘得120;第五步:將第四步中的運(yùn)算結(jié)果120與6相乘得720.4.累加、累乘問(wèn)題的算法題型探究第一步:設(shè)i=1,mul

=1;第二步:如果i≤6執(zhí)行第三步,否則執(zhí)行第五步;第三步:計(jì)算mul×i并將結(jié)果代替mul;第四步:將i+1代替i,轉(zhuǎn)去執(zhí)行第二步;第五步:輸出mul.規(guī)律技巧總結(jié):i稱作計(jì)數(shù)變量,每一次循環(huán)它的值增加1,從由1變到6.mul稱作累乘變量,每一次循環(huán)得到一個(gè)新的結(jié)果,然后新的結(jié)果代替原值.解2.用數(shù)學(xué)語(yǔ)言描述題型探究【6】寫出一個(gè)能找出在a,b,c,d四個(gè)數(shù)中最大的數(shù)的算法.第一步:輸入a,b,c,d四個(gè)數(shù);第二步:max=a;第三步:如果b>max,則max=b;第四步:如果c>max,則max=c;第五步:如果d>max,則max=d;第六步:輸出max.題型探究點(diǎn)評(píng):算法要求“按部就班”地做,每做一步都有唯一的結(jié)果,且有限步之后總能得到結(jié)果.1.知識(shí)結(jié)構(gòu)算法的概念算法的步驟算法的特點(diǎn)算法課堂小結(jié)2.算法的特點(diǎn):思路簡(jiǎn)單清晰,敘述復(fù)雜,步驟繁瑣,計(jì)算量大,完全依靠人力難以完成.而這些恰恰就是計(jì)算機(jī)的特長(zhǎng),它能不厭其煩地完成枯燥的、重復(fù)的繁瑣的工作.正因?yàn)檫@些,現(xiàn)代算法的作用之一就是使計(jì)算機(jī)代替人完成某些工作,這也是我們學(xué)習(xí)算法的重要原因之一.課堂小結(jié)3.設(shè)計(jì)算法的注意事項(xiàng):(1)認(rèn)真分析問(wèn)題,聯(lián)系解決此問(wèn)題的一般數(shù)學(xué)方法;(2)綜合考慮此類問(wèn)題中可能涉及的各種情況;(3)借助有關(guān)的變量或參數(shù)對(duì)算法加以表達(dá);(4)將解決問(wèn)題的過(guò)程劃分為若干個(gè)步驟;(5)然后用簡(jiǎn)練的語(yǔ)言將各個(gè)步驟表示出來(lái).課堂作業(yè)課本P.22預(yù)習(xí)1.1.2程序框圖1.算法的優(yōu)化:對(duì)于同一個(gè)問(wèn)題,有時(shí)可以有不同的解題方法和步驟.有的方法只需要較少的步驟,而有些方法則可能需要較多的步驟.一般情況下,盡可能采用簡(jiǎn)單省時(shí)的和步驟少的方法去解決問(wèn)題.因此,為了有效地解決問(wèn)題,不僅需要保證算法正確,還要考慮算法的質(zhì)量,這就要求人們?cè)O(shè)計(jì)或選擇合適的算法.備課資料

我國(guó)著名數(shù)學(xué)家華羅庚在數(shù)學(xué)普及讀物《統(tǒng)籌方法平話及補(bǔ)充》中,以“泡茶”為例,闡述了設(shè)計(jì)和選擇合適的、優(yōu)化的算法的重要性.

開水沒(méi)有,水壺要洗,茶壺和茶杯要洗;火已生了,茶葉也有了,要想泡茶喝,怎么辦？甲:洗水壺,灌涼水,燒開水的過(guò)程中,洗茶壺、洗茶杯、拿茶葉,等水開了,泡茶喝.乙:洗水壺,洗茶壺和茶杯、拿茶葉,一切就緒,再灌水燒水,等水開了,泡茶喝.丙:洗水壺,灌涼水,燒水,等水開了,急急忙忙找茶葉,洗茶壺,洗茶杯,泡茶喝.洗開水壺洗茶壺洗茶杯拿茶葉泡茶喝燒開水燒開水洗茶壺洗茶杯拿茶葉洗開水壺灌涼水泡茶喝燒開水洗開水壺灌涼水泡茶喝洗茶壺洗茶杯拿茶葉灌涼水

三種方法所用時(shí)間的比較,顯然是方法甲最省時(shí)間.水壺不洗,不能燒開水,因而洗水壺是燒開水的先決條件.沒(méi)開水、不取茶葉、不洗茶壺和茶杯,不能泡茶,因而這些又是泡茶的先決條件.要提高效率,就要充分利用“等水開”的這段時(shí)間并行地進(jìn)行其它工作,如洗茶杯、拿茶葉.甲乙丙2.算法的分類:(1)對(duì)于數(shù)值性問(wèn)題,(如解方程,不等式,套用公式,累加,累乘等)可以建立數(shù)學(xué)模型,通過(guò)數(shù)學(xué)語(yǔ)言來(lái)描述問(wèn)題;設(shè)計(jì)算法時(shí),可以采用數(shù)學(xué)分析的方法進(jìn)行處理,直接運(yùn)用其中的現(xiàn)成的固定算法,也可以根據(jù)實(shí)際問(wèn)題情景設(shè)計(jì)算法.(2)對(duì)于非數(shù)值性問(wèn)題,應(yīng)建立過(guò)程模型,通過(guò)過(guò)程模型來(lái)描述算法;在設(shè)計(jì)算法時(shí),可以根據(jù)過(guò)程模型分析進(jìn)行處理,也可以選擇一些成熟的辦法進(jìn)行處理(例如排序、資料檢索、事務(wù)管理、數(shù)據(jù)處理等).【1】在9枚外觀完全一樣的金幣中,有一枚是假的,并且已知它比真金幣稍輕.現(xiàn)有一個(gè)沒(méi)有砝碼的天平,你能設(shè)計(jì)一個(gè)算法把假金幣找出來(lái)嗎?第一步:將9枚金幣平均分成三組,將其中兩組放在天平的兩邊.如果天平平衡,則假的金幣必定在另外一組;如果天平不平衡,則假的金幣必定在較輕的一組;第二步:將有假金幣的一組金幣中,取出兩枚金幣,分別放在天平的兩邊.如果天平平衡,則假的金幣必定是剩余的;如果天平不平衡,則假的金幣必定在較輕的一邊.【2】“雞兔同籠”是我國(guó)隋朝時(shí)期的數(shù)學(xué)著作《孫子算經(jīng)》中的一個(gè)有趣而具有深遠(yuǎn)影響的題目:“今有雉兔同籠,上有三十五頭,下有九十四足,問(wèn)雉兔各幾何.用方程組的思想不難解決這一問(wèn)題,請(qǐng)你設(shè)計(jì)一個(gè)這類問(wèn)題的通用算法.第一步:輸入總頭數(shù)H，總腳數(shù)F；第二步:計(jì)算雞的個(gè)數(shù)x=(4*H－F)/2；第三步:計(jì)算兔的個(gè)數(shù)y=(F－2*H)/2；第四步:輸出x,y