算法的概念課件

20世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明是計(jì)算機(jī).沒(méi)有軟件的支持，計(jì)算機(jī)只是一堆廢鐵而已.軟件的核心就是算法！20世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明是計(jì)算機(jī).沒(méi)有軟件的支算法的含義算法的含義【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ò)河.創(chuàng)設(shè)情境【1】一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一筐蔬菜要過(guò)河,但只有一一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解過(guò)程稱為算法(algorithm)它是解決某一問(wèn)題的程序或步驟.按照這樣的理解,我們可以設(shè)計(jì)出很多具體數(shù)學(xué)問(wèn)題的算法.下面看幾個(gè)例子:所謂“算法”就是解題方法的精確描述.從更廣義的角度來(lái)看,并不是只有“計(jì)算”的問(wèn)題才有算法,日常生活中處處都有.如歌譜是一首歌曲的算法;菜譜是做菜的算法;珠算口訣是使用算盤(pán)的算法;空調(diào)說(shuō)明書(shū)是空調(diào)使用的算法等.一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解：第一步:①+②×2,得第二步:解③,得機(jī)械的統(tǒng)一的方法5x=1.③第三步:②-①×2,得5y=3.④第四步:解④,得第五步:得到方程組的解為新知建構(gòu)例1.寫(xiě)出解二元一次方程組的一個(gè)算法.解：第一步:①+②×2,得第二步:解③,得機(jī)械的統(tǒng)一的算法1算法2問(wèn):ax

+b

=

0

?算法1算法2問(wèn):ax+b=0?練2.寫(xiě)出求1+2+3+4+5的一個(gè)算法.算法1：S1:計(jì)算1+2得到3；S2:將第一步中的運(yùn)算結(jié)果3與3相加得到6；S3:將第二步中的運(yùn)算結(jié)果6與4相加得到10；S4:將第三步中的運(yùn)算結(jié)果10與5相加得到15.算法2:S1：取n=5.S2：計(jì)算S3：輸出運(yùn)算結(jié)果.同一問(wèn)題的解決算法一般是不唯一的練2.寫(xiě)出求1+2+3+4+5的一個(gè)算法.算法1：S1:計(jì)算第一步:計(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.練3.求1×2×3×4×5×6的值，寫(xiě)出其算法.第一步:計(jì)算1×2,得2;第二步:將第一步中的運(yùn)算結(jié)果2與3在數(shù)學(xué)中,算法通常是指按照一定規(guī)則解決某一類問(wèn)題的明確的有限的步驟.現(xiàn)在,算法通?？梢跃幊捎?jì)算機(jī)程序,讓計(jì)算機(jī)執(zhí)行并解決問(wèn)題.1.算法的定義新知建構(gòu)?算法:廣義上講，做任何事情都有一定的步驟,為解決一個(gè)問(wèn)題而采取的方法和步驟就是算法.總結(jié)?算法過(guò)程:要能一步一步執(zhí)行，每一步執(zhí)行的操作,必須確切，不能含混不清楚，而且經(jīng)過(guò)有限步后能得出結(jié)果.在數(shù)學(xué)中,算法通常是指按照一定規(guī)則解決某一類小結(jié)通過(guò)練習(xí)說(shuō)明算法有三個(gè)主要特點(diǎn)：（3）確定性算法的每一個(gè)步驟和次序應(yīng)當(dāng)是確定的（2）有限性一個(gè)算法在執(zhí)行有限個(gè)步驟后必須結(jié)束；（1）可行性一個(gè)算法必須一步步可執(zhí)行小結(jié)通過(guò)練習(xí)說(shuō)明算法有三個(gè)主要特點(diǎn)：（3）確定性算法的想一想【1】有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫(xiě)成兩個(gè)奇質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：第一步：檢驗(yàn)6=3+3第二步：檢驗(yàn)8=3+5利用計(jì)算機(jī)無(wú)窮地進(jìn)行下去！利用這種程序能夠證明猜想的正確性嗎？第三步：檢驗(yàn)10=5+5想一想【1】有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫(xiě)成兩個(gè)【2】問(wèn)要把大象裝冰箱，分幾步？答：分三步：第一步：打開(kāi)冰箱門(mén).第二步：把大象裝冰箱.第三步：關(guān)上冰箱門(mén).想一想對(duì)算法你有新的認(rèn)識(shí)了嗎？【2】問(wèn)要把大象裝冰箱，分幾步？答：分三步：第一步：打開(kāi)冰箱例題講解第一步:用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以2不能整除7.第二步:用3除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以3不能整除7.第三步:用4除7,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除7.第四步:用5除7,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以5不能整除7.第五步:用6除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以6不能整除7.例2.(1)設(shè)計(jì)一個(gè)算法,判斷7是否為質(zhì)數(shù).例題講解第一步:用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,例2.例2.(2)設(shè)計(jì)一個(gè)算法,判斷35是否為質(zhì)數(shù).第一步:用2除35,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以2不能整除35.第二步:用3除35,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以3不能整除35.第三步:用4除35,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除35.第四步:用5除35,得到余數(shù)0.因?yàn)橛鄶?shù)為0,所以5能整除35.因此,35不是質(zhì)數(shù).例2.(2)設(shè)計(jì)一個(gè)算法,判斷35是否為質(zhì)數(shù).第一步:用2除例2.任意給定一個(gè)大于2的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.第二步:令i=2.第一步：給定一個(gè)大于2的整數(shù)n.

第三步:用i除n,得到余數(shù)r.解析:n是否為質(zhì)數(shù)?2～(n-1)這是判斷一個(gè)大于1的整數(shù)的最基本算法.例題講解第四步:判斷“r=0”是否成立.若是,則n不是質(zhì)數(shù),結(jié)束算法;否則,將i的值增加1,仍i用表示.第五步:判斷“i>(n-1)”是否成立.若是,則n是質(zhì)數(shù),結(jié)束算法;否則返回第三步.例2.任意給定一個(gè)大于2的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是第五步:判斷[a,b]的長(zhǎng)度是否小于d或f(m)是否等于0.若是，則m是方程的近似解；否則，返回第三步.例3.用二分法設(shè)計(jì)一個(gè)求方程x2-2=0(x>0)

的近似根的算法.第一步：令f(x)=x2-2，給定精確度d.第二步：確定區(qū)間[a,b],滿足f(a)·f(b)<0.例題講解第三步：取區(qū)間中點(diǎn)m=第四步：若f(a)·f(m)<0，則含零點(diǎn)的區(qū)間為[a,m];否則,含零點(diǎn)的區(qū)間為[m,b],將新得到的含零點(diǎn)的區(qū)間仍記為[a,b].第五步:判斷[a,b]的長(zhǎng)度是否小于d或f(m)是否等于ab|a-b|12111.50.51.251.50.251.3751.50.1251.3751.43750.06251.406251.43750.031251.406251.4218750.0156251.41406251.4218750.00781251.41406251.417968750.00390625當(dāng)d=0.005時(shí),開(kāi)區(qū)間(1.4140625,1.41796875)中的實(shí)數(shù)都是原方程的近似解.ab|a-b|12111.50.51.251.50.251.1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.(P5練習(xí)2)S1:輸入任意一個(gè)正實(shí)數(shù)r.S2:計(jì)算圓的面積:S=πr2.S3:輸出圓的面積S.鞏固練習(xí)開(kāi)始輸出S結(jié)束S=πr2輸入r1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面2.任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).(P5練習(xí)2)第一步：給定一個(gè)大于1的正整數(shù)n.第三步：在n的因數(shù)中加入1和n.第四步：得到n的所有因數(shù).鞏固練習(xí)第二步：依次以2~(n-1)的整數(shù)d為除數(shù)去除n,檢查余數(shù)是否為0.若是,則d是n的因數(shù);若不是,則d不是n的因數(shù).2.任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有例4.寫(xiě)出一個(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é)果.例4.寫(xiě)出一個(gè)能找出在a,b,c,d四個(gè)數(shù)中最大的數(shù)的算法.例5.寫(xiě)出一個(gè)求有限整數(shù)列中的最大值的算法.S1:先假定序列中的第一個(gè)整數(shù)為“最大值”.S2:將序列中的下一個(gè)整數(shù)值與“最大值”比較,如果它大于此“最大值”，這時(shí)你就假定“最大值”是這個(gè)整數(shù).S3:如果序列中還有其他整數(shù).重復(fù)S2.S4:在序列中一直到?jīng)]有可比的數(shù)為止,這時(shí)假定的“最大值”就是這個(gè)序列中的最大值.例5.寫(xiě)出一個(gè)求有限整數(shù)列中的最大值的算法.S1:先假定序列1.知識(shí)結(jié)構(gòu)算法的概念算法的步驟算法的特點(diǎn)算法2.算法的特點(diǎn):思路簡(jiǎn)單清晰,敘述復(fù)雜,步驟繁瑣,計(jì)算量大,完全依靠人力難以完成.而這些恰恰就是計(jì)算機(jī)的特長(zhǎng),它能不厭其煩地完成枯燥的、重復(fù)的繁瑣的工作.正因?yàn)檫@些,現(xiàn)代算法的作用之一就是使計(jì)算機(jī)代替人完成某些工作,這也是我們學(xué)習(xí)算法的重要原因之一.課堂小結(jié)1.知識(shí)結(jié)構(gòu)算法的概念算法的步驟算法的特點(diǎn)算法2.算法的特小結(jié)通過(guò)例題說(shuō)明算法有兩個(gè)主要特點(diǎn)：（1）有限性一個(gè)算法在執(zhí)行有限個(gè)步驟后必須結(jié)束；（2）確定性算法的每一個(gè)步驟和次序應(yīng)當(dāng)是確定的小結(jié)通過(guò)例題說(shuō)明算法有兩個(gè)主要特點(diǎn)：（1）有限性一個(gè)算學(xué)案:刪第1頁(yè)例1，第2頁(yè)3，拓展提高2完成:學(xué)案P.1-2

——華羅庚

天才在于積累。聰明在于勤奮，布置作業(yè)學(xué)案:刪第1頁(yè)例1，第2頁(yè)3，完成:學(xué)案P20世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明是計(jì)算機(jī).沒(méi)有軟件的支持，計(jì)算機(jī)只是一堆廢鐵而已.軟件的核心就是算法！20世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明是計(jì)算機(jī).沒(méi)有軟件的支算法的含義算法的含義【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ò)河.創(chuàng)設(shè)情境【1】一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一筐蔬菜要過(guò)河,但只有一一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解過(guò)程稱為算法(algorithm)它是解決某一問(wèn)題的程序或步驟.按照這樣的理解,我們可以設(shè)計(jì)出很多具體數(shù)學(xué)問(wèn)題的算法.下面看幾個(gè)例子:所謂“算法”就是解題方法的精確描述.從更廣義的角度來(lái)看,并不是只有“計(jì)算”的問(wèn)題才有算法,日常生活中處處都有.如歌譜是一首歌曲的算法;菜譜是做菜的算法;珠算口訣是使用算盤(pán)的算法;空調(diào)說(shuō)明書(shū)是空調(diào)使用的算法等.一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解：第一步:①+②×2,得第二步:解③,得機(jī)械的統(tǒng)一的方法5x=1.③第三步:②-①×2,得5y=3.④第四步:解④,得第五步:得到方程組的解為新知建構(gòu)例1.寫(xiě)出解二元一次方程組的一個(gè)算法.解：第一步:①+②×2,得第二步:解③,得機(jī)械的統(tǒng)一的算法1算法2問(wèn):ax

+b

=

0

?算法1算法2問(wèn):ax+b=0?練2.寫(xiě)出求1+2+3+4+5的一個(gè)算法.算法1：S1:計(jì)算1+2得到3；S2:將第一步中的運(yùn)算結(jié)果3與3相加得到6；S3:將第二步中的運(yùn)算結(jié)果6與4相加得到10；S4:將第三步中的運(yùn)算結(jié)果10與5相加得到15.算法2:S1：取n=5.S2：計(jì)算S3：輸出運(yùn)算結(jié)果.同一問(wèn)題的解決算法一般是不唯一的練2.寫(xiě)出求1+2+3+4+5的一個(gè)算法.算法1：S1:計(jì)算第一步:計(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.練3.求1×2×3×4×5×6的值，寫(xiě)出其算法.第一步:計(jì)算1×2,得2;第二步:將第一步中的運(yùn)算結(jié)果2與3在數(shù)學(xué)中,算法通常是指按照一定規(guī)則解決某一類問(wèn)題的明確的有限的步驟.現(xiàn)在,算法通?？梢跃幊捎?jì)算機(jī)程序,讓計(jì)算機(jī)執(zhí)行并解決問(wèn)題.1.算法的定義新知建構(gòu)?算法:廣義上講，做任何事情都有一定的步驟,為解決一個(gè)問(wèn)題而采取的方法和步驟就是算法.總結(jié)?算法過(guò)程:要能一步一步執(zhí)行，每一步執(zhí)行的操作,必須確切，不能含混不清楚，而且經(jīng)過(guò)有限步后能得出結(jié)果.在數(shù)學(xué)中,算法通常是指按照一定規(guī)則解決某一類小結(jié)通過(guò)練習(xí)說(shuō)明算法有三個(gè)主要特點(diǎn)：（3）確定性算法的每一個(gè)步驟和次序應(yīng)當(dāng)是確定的（2）有限性一個(gè)算法在執(zhí)行有限個(gè)步驟后必須結(jié)束；（1）可行性一個(gè)算法必須一步步可執(zhí)行小結(jié)通過(guò)練習(xí)說(shuō)明算法有三個(gè)主要特點(diǎn)：（3）確定性算法的想一想【1】有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫(xiě)成兩個(gè)奇質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：第一步：檢驗(yàn)6=3+3第二步：檢驗(yàn)8=3+5利用計(jì)算機(jī)無(wú)窮地進(jìn)行下去！利用這種程序能夠證明猜想的正確性嗎？第三步：檢驗(yàn)10=5+5想一想【1】有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫(xiě)成兩個(gè)【2】問(wèn)要把大象裝冰箱，分幾步？答：分三步：第一步：打開(kāi)冰箱門(mén).第二步：把大象裝冰箱.第三步：關(guān)上冰箱門(mén).想一想對(duì)算法你有新的認(rèn)識(shí)了嗎？【2】問(wèn)要把大象裝冰箱，分幾步？答：分三步：第一步：打開(kāi)冰箱例題講解第一步:用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以2不能整除7.第二步:用3除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以3不能整除7.第三步:用4除7,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除7.第四步:用5除7,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以5不能整除7.第五步:用6除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以6不能整除7.例2.(1)設(shè)計(jì)一個(gè)算法,判斷7是否為質(zhì)數(shù).例題講解第一步:用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,例2.例2.(2)設(shè)計(jì)一個(gè)算法,判斷35是否為質(zhì)數(shù).第一步:用2除35,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以2不能整除35.第二步:用3除35,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以3不能整除35.第三步:用4除35,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除35.第四步:用5除35,得到余數(shù)0.因?yàn)橛鄶?shù)為0,所以5能整除35.因此,35不是質(zhì)數(shù).例2.(2)設(shè)計(jì)一個(gè)算法,判斷35是否為質(zhì)數(shù).第一步:用2除例2.任意給定一個(gè)大于2的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.第二步:令i=2.第一步：給定一個(gè)大于2的整數(shù)n.

第三步:用i除n,得到余數(shù)r.解析:n是否為質(zhì)數(shù)?2～(n-1)這是判斷一個(gè)大于1的整數(shù)的最基本算法.例題講解第四步:判斷“r=0”是否成立.若是,則n不是質(zhì)數(shù),結(jié)束算法;否則,將i的值增加1,仍i用表示.第五步:判斷“i>(n-1)”是否成立.若是,則n是質(zhì)數(shù),結(jié)束算法;否則返回第三步.例2.任意給定一個(gè)大于2的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是第五步:判斷[a,b]的長(zhǎng)度是否小于d或f(m)是否等于0.若是，則m是方程的近似解；否則，返回第三步.例3.用二分法設(shè)計(jì)一個(gè)求方程x2-2=0(x>0)

的近似根的算法.第一步：令f(x)=x2-2，給定精確度d.第二步：確定區(qū)間[a,b],滿足f(a)·f(b)<0.例題講解第三步：取區(qū)間中點(diǎn)m=第四步：若f(a)·f(m)<0，則含零點(diǎn)的區(qū)間為[a,m];否則,含零點(diǎn)的區(qū)間為[m,b],將新得到的含零點(diǎn)的區(qū)間仍記為[a,b].第五步:判斷[a,b]的長(zhǎng)度是否小于d或f(m)是否等于ab|a-b|12111.50.51.251.50.251.3751.50.1251.3751.43750.06251.406251.43750.031251.406251.4218750.0156251.41406251.4218750.00781251.41406251.417968750.00390625當(dāng)d=0.005時(shí),開(kāi)區(qū)間(1.4140625,1.41796875)中的實(shí)數(shù)都是原方程的近似解.ab|a-b|12111.50.51.251.50.251.1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.(P5練習(xí)2)S1:輸入任意一個(gè)正實(shí)數(shù)r.S2:計(jì)算圓的面積:S=πr2.S3:輸出圓的面積S.鞏固練習(xí)開(kāi)始輸出S結(jié)束S=πr2輸入r1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面2.任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).(P5練習(xí)2)第一步：給定一個(gè)大于1的正整數(shù)n.第三步：在n的因數(shù)中加入1和n.第四步：得到n的所有因數(shù).鞏固練習(xí)第二步：依次以2~(n-1)的整數(shù)d為除數(shù)去除n,檢查余數(shù)是否為0.若是,則d是n的因數(shù);若不是,則d不是n的因數(shù).2.任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出