算法的概念上課實(shí)用教案

1、我國(guó)古代的計(jì)算我國(guó)古代的計(jì)算(j sun)工具工具第1頁(yè)/共29頁(yè)第一頁(yè)，共29頁(yè)。世界世界(shji)上第一臺(tái)電子計(jì)上第一臺(tái)電子計(jì)算機(jī)算機(jī)第2頁(yè)/共29頁(yè)第二頁(yè)，共29頁(yè)。我國(guó)第一臺(tái)電子計(jì)算機(jī)我國(guó)第一臺(tái)電子計(jì)算機(jī)第3頁(yè)/共29頁(yè)第三頁(yè)，共29頁(yè)。 算籌、算盤、計(jì)算機(jī)等從古到今的計(jì)算工具的算籌、算盤、計(jì)算機(jī)等從古到今的計(jì)算工具的基礎(chǔ)都是基礎(chǔ)都是“算法算法”.算法對(duì)我們而言并不陌生，其實(shí)我算法對(duì)我們而言并不陌生，其實(shí)我們從小學(xué)就開(kāi)始接觸算法，例如，做四則運(yùn)算們從小學(xué)就開(kāi)始接觸算法，例如，做四則運(yùn)算(s z yn sun)要先乘除后加減、從里往外去括號(hào)要先乘除后加減、從里往外去括號(hào) 、豎式筆算等都

2、是算法，至于乘法口訣、珠算口訣更豎式筆算等都是算法，至于乘法口訣、珠算口訣更是算法的具體體現(xiàn)是算法的具體體現(xiàn). 在現(xiàn)代社會(huì)里，計(jì)算機(jī)已經(jīng)成為人們?nèi)粘Ｉ钤诂F(xiàn)代社會(huì)里，計(jì)算機(jī)已經(jīng)成為人們?nèi)粘Ｉ詈凸ぷ鞑豢扇鄙俚墓ぞ呗?tīng)音樂(lè)、看電影、玩游和工作不可缺少的工具聽(tīng)音樂(lè)、看電影、玩游戲、畫卡通畫、處理數(shù)據(jù)戲、畫卡通畫、處理數(shù)據(jù)計(jì)算機(jī)幾乎可以是一計(jì)算機(jī)幾乎可以是一個(gè)全能個(gè)全能(qunnng)(qunnng)的助手，你可以用它來(lái)做你想的助手，你可以用它來(lái)做你想做的任何事情那么，計(jì)算機(jī)是怎樣工作呢？要做的任何事情那么，計(jì)算機(jī)是怎樣工作呢？要想弄清楚這個(gè)問(wèn)題，就需要學(xué)習(xí)算法想弄清楚這個(gè)問(wèn)題，就需要學(xué)習(xí)算法 第4頁(yè)

3、/共29頁(yè)第四頁(yè)，共29頁(yè)。l第一步：把冰箱門打開(kāi)(d ki)l第二步：把大象放進(jìn)去l第三步：把冰箱門帶上第5頁(yè)/共29頁(yè)第五頁(yè)，共29頁(yè)。情境情境(qngjng)2：農(nóng)夫過(guò)河問(wèn)題：農(nóng)夫過(guò)河問(wèn)題 有一個(gè)農(nóng)夫帶三只狼和三只羚羊過(guò)河，只有一條有一個(gè)農(nóng)夫帶三只狼和三只羚羊過(guò)河，只有一條船，船，同船可以容納一個(gè)人和兩只動(dòng)物。沒(méi)有人在的時(shí)候，同船可以容納一個(gè)人和兩只動(dòng)物。沒(méi)有人在的時(shí)候，如果如果狼的數(shù)量不少狼的數(shù)量不少(b sho)(b sho)于羚羊的數(shù)量，狼就會(huì)吃掉羚于羚羊的數(shù)量，狼就會(huì)吃掉羚羊。農(nóng)夫應(yīng)羊。農(nóng)夫應(yīng)該如何渡河？該如何渡河？河河 流流第6頁(yè)/共29頁(yè)第六頁(yè)，共29頁(yè)。第7頁(yè)/共29頁(yè)第七

4、頁(yè)，共29頁(yè)。如何如何(rh)求解二元一次方程組？求解二元一次方程組？ 回顧回顧(hug)第8頁(yè)/共29頁(yè)第八頁(yè)，共29頁(yè)。二元一次方程組二元一次方程組 12 12yxyx的求解過(guò)程的求解過(guò)程.歸納歸納(gun)它的步驟它的步驟:第一步第一步: -2，得，得 5y=3 第三步第三步:5153xy，得代入將第二步第二步: 解得解得 y= 53第二步第二步: 解得解得 y= 53第9頁(yè)/共29頁(yè)第九頁(yè)，共29頁(yè)。思考(sko)？0 1221222111babacybxacybxa其中一般的二元一次方程組第二步：解，得第二步：解，得12211221babacacay第一步：第一步： - - ，得，得

5、 1a2a12211221)(cacaybaba第三步：將第三步：將 代入代入，得12211221babacacay12212112babacbcbx第10頁(yè)/共29頁(yè)第十頁(yè)，共29頁(yè)。 我們我們(w men)做每件事情都需要設(shè)計(jì)出做每件事情都需要設(shè)計(jì)出“行動(dòng)步行動(dòng)步驟驟”. 上述步驟構(gòu)成了解二元一次方程組的算法，我們上述步驟構(gòu)成了解二元一次方程組的算法，我們(w men)可以進(jìn)一步根據(jù)這一算法編制計(jì)算機(jī)程序，可以進(jìn)一步根據(jù)這一算法編制計(jì)算機(jī)程序，讓計(jì)算機(jī)來(lái)解二元一次方程組讓計(jì)算機(jī)來(lái)解二元一次方程組.第11頁(yè)/共29頁(yè)第十一頁(yè)，共29頁(yè)。1.1.算法算法(sun f)(sun f)的概念：的概

6、念：在數(shù)學(xué)在數(shù)學(xué)(shxu)(shxu)中中“算法算法”通常是指按照一定通常是指按照一定的規(guī)則來(lái)解決的某一類問(wèn)題的明確和有限的步驟。的規(guī)則來(lái)解決的某一類問(wèn)題的明確和有限的步驟。3.3.算法的基本算法的基本(jbn)(jbn)思想與特征思想與特征: :2.2.算法的表示方法：算法的表示方法： 自然語(yǔ)言、程序框圖、程序語(yǔ)言自然語(yǔ)言、程序框圖、程序語(yǔ)言(1)解決某一類問(wèn)題解決某一類問(wèn)題(2)在在有限步有限步之內(nèi)完成之內(nèi)完成(3)每一步都是明確的，有確定的結(jié)果和有效性每一步都是明確的，有確定的結(jié)果和有效性(4)每一步具有順序每一步具有順序(5)解決問(wèn)題的算法不唯一解決問(wèn)題的算法不唯一(普遍性普遍性)(

7、有限性有限性)(確定性與可行性確定性與可行性)(有有序性序性)(不唯不唯一一性性)第12頁(yè)/共29頁(yè)第十二頁(yè)，共29頁(yè)。練習(xí)練習(xí)(linx)判斷下列判斷下列(xili)關(guān)于算法的說(shuō)法是關(guān)于算法的說(shuō)法是否確：否確：1、求解、求解(qi ji)某一類問(wèn)題的算法是唯一某一類問(wèn)題的算法是唯一的；的；2、算法必須在有限步操作之后停止；、算法必須在有限步操作之后停止；3、算法的每一步必須是明確的，不能有歧義、算法的每一步必須是明確的，不能有歧義或模糊；或模糊；4、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果.第13頁(yè)/共29頁(yè)第十三頁(yè)，共29頁(yè)。練習(xí)練習(xí)(linx)判斷下列關(guān)于判斷下列關(guān)于(

8、guny)算法的說(shuō)法算法的說(shuō)法是否確：是否確：1、求解某一類問(wèn)題、求解某一類問(wèn)題(wnt)的算法是唯的算法是唯一的；一的；2、算法必須在有限步操作之后停止；、算法必須在有限步操作之后停止；3、算法的每一步必須是明確的，不能有歧、算法的每一步必須是明確的，不能有歧義或模糊；義或模糊；4、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果.第14頁(yè)/共29頁(yè)第十四頁(yè)，共29頁(yè)。例題例題(lt)1(2).設(shè)計(jì)一個(gè)(y )算法，判斷35是否為質(zhì)數(shù)？(1).設(shè)計(jì)一個(gè)算法(sun f)，判斷7是否為質(zhì)數(shù)？只能被只能被1 1和自身整除的大于和自身整除的大于1 1的整數(shù)叫質(zhì)數(shù)的整數(shù)叫質(zhì)數(shù). .第15頁(yè)

9、/共29頁(yè)第十五頁(yè)，共29頁(yè)。例題例題(lt)1(1).設(shè)計(jì)一個(gè)(y )算法，判斷7是否為質(zhì)數(shù)？解：解： 算法算法(sun f)分析：由質(zhì)數(shù)的定義，可以這樣判斷分析：由質(zhì)數(shù)的定義，可以這樣判斷:依次用依次用26除除7,若它們中有一個(gè)能整除若它們中有一個(gè)能整除7，則，則7不是質(zhì)數(shù)，否則不是質(zhì)數(shù)，否則7是質(zhì)數(shù)是質(zhì)數(shù).根據(jù)以上分析，可以寫出如下的算法：根據(jù)以上分析，可以寫出如下的算法：第一步第一步,用用2除除7,余數(shù)不為余數(shù)不為0, 第二步第二步,用用3除除7,余數(shù)不為余數(shù)不為0, 得到余數(shù)得到余數(shù)1.2不能整除不能整除7.得到余數(shù)得到余數(shù)1.3不能整除不能整除7.第三步第三步,用用4除除7,余數(shù)不

10、為余數(shù)不為0, 得到余數(shù)得到余數(shù)3.4不能整除不能整除7.第四步第四步,用用5除除7,余數(shù)不為余數(shù)不為0, 得到余數(shù)得到余數(shù)2.5不能整除不能整除7.第五步第五步,用用6除除7,余數(shù)不為余數(shù)不為0, 得到余數(shù)得到余數(shù)1.6不能整除不能整除7.故故7是質(zhì)數(shù)是質(zhì)數(shù).第16頁(yè)/共29頁(yè)第十六頁(yè)，共29頁(yè)。例題例題(lt)1(2).設(shè)計(jì)一個(gè)算法，判斷(pndun)35是否為質(zhì)數(shù)？解：解：根據(jù)以上分析，可以根據(jù)以上分析，可以(ky)寫出如下的算法：寫出如下的算法：第一步第一步,用用2除除35,余數(shù)不為余數(shù)不為0, 第二步第二步,用用3除除35,余數(shù)不為余數(shù)不為0, 得到余數(shù)得到余數(shù)1.2不能整除不能整除

11、35.得到余數(shù)得到余數(shù)2.3不能整除不能整除35.第三步第三步,用用4除除35,余數(shù)不為余數(shù)不為0, 得到余數(shù)得到余數(shù)3.4不能整除不能整除35.第四步第四步,用用5除除35,余數(shù)為余數(shù)為0, 得到余數(shù)得到余數(shù)0.5能整除能整除35.故故35不是質(zhì)數(shù)不是質(zhì)數(shù).探究：探究：你能寫出你能寫出“判斷整數(shù)判斷整數(shù)n(n2)是否為質(zhì)數(shù)是否為質(zhì)數(shù)”的算法嗎？的算法嗎？第17頁(yè)/共29頁(yè)第十七頁(yè)，共29頁(yè)。 【算法分析】【算法分析】對(duì)于任意的整數(shù)對(duì)于任意的整數(shù)n(n2)，若用，若用i表示表示2(n-1)中的任意整數(shù)，則中的任意整數(shù)，則“判斷判斷n是否為是否為質(zhì)數(shù)質(zhì)數(shù)”的算法包含的算法包含(bohn)下面的重

12、復(fù)操作：下面的重復(fù)操作：用用i除除n，得到余數(shù)，得到余數(shù)r，判斷余數(shù)，判斷余數(shù)r是否為是否為0，若為若為0，則，則n不是質(zhì)數(shù)，否則將不是質(zhì)數(shù)，否則將i 的值增加的值增加1，再執(zhí)行同樣的操作，一直到再執(zhí)行同樣的操作，一直到i的值等于的值等于n-1為止為止.寫出寫出“判斷整數(shù)判斷整數(shù)n(n2)是否為質(zhì)數(shù)是否為質(zhì)數(shù)(zhsh)”的算法。的算法。第18頁(yè)/共29頁(yè)第十八頁(yè)，共29頁(yè)。 解：解：第一步：給定大于第一步：給定大于2的整數(shù)的整數(shù)n；第二步：令第二步：令i=2；第三步：用第三步：用i除除n，得到余數(shù)，得到余數(shù)r；第四步：判斷第四步：判斷“r=0”是否是否(sh fu)成立，若是，則成立，若是，

13、則n不是質(zhì)數(shù)，不是質(zhì)數(shù)，結(jié)束算法；否則，將結(jié)束算法；否則，將i的值增加的值增加1，仍用，仍用i表示；表示；第五步，判斷第五步，判斷“in-1”是否是否(sh fu)成立，若成立，則成立，若成立，則n是質(zhì)是質(zhì)數(shù)，結(jié)束算法；否則，返回第三步數(shù)，結(jié)束算法；否則，返回第三步.寫出寫出“判斷整數(shù)判斷整數(shù)n(n2)是否為質(zhì)數(shù)是否為質(zhì)數(shù)(zhsh)”的算法。的算法。第19頁(yè)/共29頁(yè)第十九頁(yè)，共29頁(yè)。 分析： 1二分(r fn)法求方程近似解是通過(guò)求對(duì)應(yīng)函數(shù)的近似零點(diǎn)得到的，所以首先要建立函數(shù)，而且要有具體精確度要求，因此第一步應(yīng)該怎么做？ 2二分(r fn)法分的是什么？ 3如何確定新區(qū)間的端點(diǎn)？ 4如

14、何表達(dá)出反復(fù)二分(r fn)區(qū)間的過(guò)程？ 例例2、用二分法設(shè)計(jì)一個(gè)求方程、用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近的近似似(jn s)解的算法（精確度為解的算法（精確度為0.005）.第20頁(yè)/共29頁(yè)第二十頁(yè)，共29頁(yè)。什么是二分法？什么是二分法？對(duì)于區(qū)間對(duì)于區(qū)間a,b a,b 上連續(xù)不斷、且上連續(xù)不斷、且f(a)f(b)0f(a)f(b)0) f(x)=x2-2(x0)x第21頁(yè)/共29頁(yè)第二十一頁(yè)，共29頁(yè)。a ab b|a-b|a-b|1 12 21 11 11.51.50.50.51.251.251.51.50.250.251.3751.3751.51.50.1250.1251.375

15、1.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 50.031 250.031 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 062 51.414 062 51.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 750.003 906 250.003 906 25對(duì)于對(duì)于(duy)(duy)方程方程x2-2=0(x0),x2-2=0(x

16、0),給定給定d=0.005.d=0.005.此步驟也是求的近似值的一個(gè)算法此步驟也是求的近似值的一個(gè)算法. .2第22頁(yè)/共29頁(yè)第二十二頁(yè)，共29頁(yè)。例例2、用二分法設(shè)計(jì)一個(gè)求方程、用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的的近似近似(jn s)根的算法（精確度為根的算法（精確度為0.005）.第一步：令第一步：令f(x)=x2-2，給定，給定(i dn)精確度精確度d. ,0a bf af b第第二二步步：確確定定區(qū)區(qū)間間滿滿足足；;2abm 第第三三步步：取取區(qū)區(qū)間間中中點(diǎn)點(diǎn) 0,.f af ma mmba b 第第四四步步：若若，則則含含零零點(diǎn)點(diǎn)的的區(qū)區(qū)間間為為否否則則為為，將將新新得得到

17、到的的區(qū)區(qū)間間仍仍記記為為 ,0a bdf mm第第五五步步：判判斷斷區(qū)區(qū)間間的的長(zhǎng)長(zhǎng)度度是是否否小小于于 或或是是否否等等于于 ；若若是是，則則 即即為為所所求求方方程程的的近近似似解解，不不是是，則則返返回回第第三三步步。根據(jù)以上根據(jù)以上(yshng)分析，可以寫出如下的算法：分析，可以寫出如下的算法：第23頁(yè)/共29頁(yè)第二十三頁(yè)，共29頁(yè)。 1、任意給定、任意給定(i dn)一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積。算法求以這個(gè)數(shù)為半徑的圓的面積。算法步驟：算法步驟：第一步：給定一個(gè)第一步：給定一個(gè)(y )正實(shí)數(shù)正實(shí)數(shù) r.第二步：計(jì)算以第二步：計(jì)算以r為半

18、徑為半徑(bnjng)的圓的面的圓的面積積 .2Sr 第三步：得到圓的面積第三步：得到圓的面積S.P5練習(xí)練習(xí)第24頁(yè)/共29頁(yè)第二十四頁(yè)，共29頁(yè)。 2、任意給定一個(gè)大于、任意給定一個(gè)大于1的正整數(shù)的正整數(shù)n，設(shè)計(jì)一個(gè)算法求出，設(shè)計(jì)一個(gè)算法求出n的所有的所有(suyu)因數(shù)。因數(shù)。算法步驟：算法步驟：第一步：給定第一步：給定(i dn)一個(gè)大于一個(gè)大于1的正整數(shù)的正整數(shù)n. 第二步：令第二步：令i=1. （i表示表示(biosh)1n中的任意整數(shù)）中的任意整數(shù)）.第三步：用第三步：用i除除n，得到余數(shù)，得到余數(shù)r.第四步：判斷第四步：判斷“r=0”是否成立，若是，則是否成立，若是，則i是是n的因數(shù)；否則的因數(shù)；否則i不是不是n的因數(shù)的因數(shù).第五步：將i的值增加1，仍用i表示.第六步，判斷“i n”是否成立，若是，則結(jié)束算法；否則，返回第三步.第25頁(yè)/共29頁(yè)第二十五頁(yè)，共29頁(yè)。必修必修3 1.1.1 算法算法(sun f)的概念的概念課后作業(yè)課后作業(yè)第26頁(yè)/共29頁(yè)