_111算法與程序框圖_

1、問(wèn)題的提出問(wèn)題的提出 有一個(gè)農(nóng)夫帶一條狼狗、一只羊和有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過(guò)河。如果沒(méi)有農(nóng)夫看管，則一筐白菜過(guò)河。如果沒(méi)有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過(guò)河。問(wèn)農(nóng)夫該如只夠農(nóng)夫帶一樣?xùn)|西過(guò)河。問(wèn)農(nóng)夫該如何解此難題？何解此難題？ 方法和過(guò)程方法和過(guò)程：1、帶羊到對(duì)岸，返回；帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。帶羊到對(duì)岸。1.1.1 算法的概念算法的概念問(wèn)題問(wèn)題請(qǐng)你寫(xiě)出解二元一次方程組的詳細(xì)求解過(guò)請(qǐng)你寫(xiě)出解二元一次方程

2、組的詳細(xì)求解過(guò)程程. 2121xyxy 第一步第一步: +2得得: 5x=1 第二步第二步: 解解得得:15x 第三步第三步: - 2，得，得 5y=3 第四步：解第四步：解 ，得，得 53y第五步：得方程組的解第五步：得方程組的解5351yx 你能你能寫(xiě)出解一般的二元一次方程組的步寫(xiě)出解一般的二元一次方程組的步 驟嗎？驟嗎？1111 22 1222(1)0(2)a xb ycaba ba xb yc第一步第一步,21(1)(2)bb得 ：12211221.a ba bxc bc b（ 3） 第二步第二步,解（解（3）得）得 12211221.c bc bxa ba b思考2 11 22 11

3、 2.ac acyab ab 第四步第四步,解（解（4）得）得 21(1)(2)aa得：第三步第三步,2 11 22 11 2.a bab ya cac（4） 第五步第五步,得到方程組的解為得到方程組的解為 1221122121122112,.c bc bxa ba ba ca cya ba b解解，得，得 21122112a ca cya ba b將將帶入帶入得得2a1a 得得111222a xb yca xb yc122 12 112b cb cxa ba b解解 得得51.x 第一步第一步：第二步：第二步：第三步：第三步：+ +2 2，得，得1.5x 21,21xyxy15x 將將 代入

4、代入, ,得得3.5y 思考思考這這 兩個(gè)解方程組的兩個(gè)解方程組的算法算法的適用范圍有何不同？的適用范圍有何不同？2 11 22 11 2()a babya ca c第一步：第一步：第二步：第二步：第三步：第三步：第二步第二步：計(jì)算：計(jì)算第三步第三步：給出運(yùn)算結(jié)果。：給出運(yùn)算結(jié)果。2 11 22 11 2a ca cya bab1 22 12 11 2bcb cxa bab1113,2,3abc 第一步第一步: : 取取2222,1,4abc12212112b cb cxa ba b21122112a ca cya ba b32324xyx y 解方程組解方程組現(xiàn)在你對(duì)算法有了新現(xiàn)在你對(duì)算法有

5、了新的認(rèn)識(shí)了嗎？的認(rèn)識(shí)了嗎？這些步驟就構(gòu)成了解二元一次方程組的這些步驟就構(gòu)成了解二元一次方程組的算法算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來(lái)解二元一次方程組讓計(jì)算機(jī)來(lái)解二元一次方程組.算法的概念與特征算法的概念與特征算法算法(algorithm)這個(gè)詞出現(xiàn)于這個(gè)詞出現(xiàn)于12世紀(jì)世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程.在數(shù)學(xué)上在數(shù)學(xué)上,現(xiàn)代意義上的現(xiàn)代意義上的“算法算法”通常是指可通常是指可以用計(jì)算機(jī)按照一定規(guī)則解決某一類(lèi)問(wèn)題的以用計(jì)算機(jī)按照一定規(guī)則解決某一類(lèi)問(wèn)題的明確和有限的程序或步驟明確和有限的程序或步驟,

6、算法的概念算法的概念: 算法是指解決給定問(wèn)題的算法是指解決給定問(wèn)題的有窮有窮操作步驟操作步驟的描述，簡(jiǎn)單的說(shuō)，算法的描述，簡(jiǎn)單的說(shuō)，算法就是解決問(wèn)題的步驟和方法。就是解決問(wèn)題的步驟和方法。(1)事實(shí)上算法并沒(méi)有精確化的定義事實(shí)上算法并沒(méi)有精確化的定義.(2)算法雖然沒(méi)有一個(gè)明確的定義算法雖然沒(méi)有一個(gè)明確的定義,但其特點(diǎn)但其特點(diǎn)是鮮明的是鮮明的,不僅要注意不僅要注意算法的程序性、有限算法的程序性、有限性、構(gòu)造性、精確性的特點(diǎn)，還應(yīng)該充分性、構(gòu)造性、精確性的特點(diǎn)，還應(yīng)該充分理解算法問(wèn)題的指向性，即算法往往指向理解算法問(wèn)題的指向性，即算法往往指向解決某一類(lèi)問(wèn)題，泛泛地談算法是沒(méi)有意解決某一類(lèi)問(wèn)題，泛

7、泛地談算法是沒(méi)有意義的。義的。說(shuō)明說(shuō)明 例題例題1.(1).(1)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷7 7是否為質(zhì)數(shù)是否為質(zhì)數(shù). .第一步第一步, 用用2除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余數(shù)得到余數(shù)3.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以4不能整除不能整除7.第五步第五步, 用用6除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以6不能整除不能整除7. 因此，因此，7是質(zhì)數(shù)是質(zhì)數(shù).

8、算法分析：算法分析：根據(jù)質(zhì)數(shù)的定義，可以這樣判斷：依次用根據(jù)質(zhì)數(shù)的定義，可以這樣判斷：依次用2-6除除7，如果他們中有一個(gè)能整除如果他們中有一個(gè)能整除7，則，則7不是質(zhì)數(shù)，否則不是質(zhì)數(shù)，否則7是質(zhì)數(shù)。具體是質(zhì)數(shù)。具體算法如下算法如下;第四步第四步, 用用5除除7,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以5不能整除不能整除7.例題解析例題解析例題例題. .(2)(2)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷3535是否為質(zhì)數(shù)是否為質(zhì)數(shù). .算法分析：算法分析： 第一步第一步, 用用2除除35,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以2不能整除不能整除35.第二步第二步

9、, 用用3除除35,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以3不能整除不能整除35.第三步第三步, 用用4除除35,得到余數(shù)得到余數(shù)3.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以4不能整除不能整除7.第四步第四步, 用用5除除35,得到余數(shù)得到余數(shù)0.因?yàn)橛鄶?shù)為因?yàn)橛鄶?shù)為0，所以，所以5能整除能整除35. 因因 此，此，35不是質(zhì)數(shù)不是質(zhì)數(shù).題后小結(jié)：題后小結(jié)：用語(yǔ)言描述一個(gè)算法用語(yǔ)言描述一個(gè)算法,最便捷的最便捷的方式就是按解決問(wèn)題的步驟進(jìn)行描述方式就是按解決問(wèn)題的步驟進(jìn)行描述.每一步每一步做一件事情做一件事情.第一步，給定大于第一步，給定大于2 2的整數(shù)的整數(shù)n。第二步，令第二

10、步，令i=2=2探究探究第三步，用第三步，用i除除n, ,得到余數(shù)得到余數(shù)r. .第四步，判斷第四步，判斷“r=0”=0”是否成立，若是，是否成立，若是，則則n不是質(zhì)數(shù)，結(jié)束算法；否則，將不是質(zhì)數(shù)，結(jié)束算法；否則，將i的的值增加值增加1 1，仍用，仍用i表示。表示。第五步，判斷第五步，判斷“i(n-1)”-1)”是否成立，是否成立，若是，則若是，則n是質(zhì)數(shù)，結(jié)束算法；否則，是質(zhì)數(shù)，結(jié)束算法；否則，返回第三步。返回第三步。例例2. .用二分法設(shè)計(jì)一個(gè)求方程用二分法設(shè)計(jì)一個(gè)求方程220 x 的近似根的算法的近似根的算法. .(0)x 二分法 對(duì)于區(qū)間對(duì)于區(qū)間a,b 上連續(xù)不斷、且上連續(xù)不斷、且f(

11、a)f(b)0的函數(shù)的函數(shù)y=f(x),通過(guò)不斷地通過(guò)不斷地把函數(shù)把函數(shù)f(x)的零點(diǎn)所在的區(qū)間一分的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)或其近似值的零點(diǎn)，進(jìn)而得到零點(diǎn)或其近似值的方法叫做方法叫做二分法二分法.第二步第二步, 給定區(qū)間給定區(qū)間a,b,滿(mǎn)足滿(mǎn)足f(a) f(b)0算法步驟：算法步驟：第一步第一步, 令令 ,給定精確度給定精確度d.2( )2f xx第四步第四步, 若若f(a) f(m) 0,則含零點(diǎn)的區(qū)間為則含零點(diǎn)的區(qū)間為a,m；第三步第三步, 取中間點(diǎn)取中間點(diǎn)2abm將新得到的含零點(diǎn)的仍然記為將新得到的含零點(diǎn)的仍然記為

12、a,b.第五步第五步,判斷判斷f(m)是否等于或者是否等于或者a,b的長(zhǎng)的長(zhǎng)度是否小于度是否小于d，若是，則，若是，則m是方程的近似解是方程的近似解;否否則，返回第三步則，返回第三步當(dāng)當(dāng)d d=0.005=0.005時(shí)，按照以上算法，可得下面表和圖時(shí)，按照以上算法，可得下面表和圖. .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.3751.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 50.

13、031 250.031 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 6251.414 6251.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 75 0.003 906 250.003 906 25y=x2-2121.51.3751.25 于是，開(kāi)區(qū)間于是，開(kāi)區(qū)間（1.4140625,1.41796875）中）中的實(shí)數(shù)都是當(dāng)精確度為的實(shí)數(shù)都是當(dāng)精確度為0.005時(shí)的原方程的近時(shí)的原方程的近似解似解.算法的

14、基本特點(diǎn)算法的基本特點(diǎn)1、有窮性、有窮性 一個(gè)算法應(yīng)包括有限的操作步驟，一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。能在執(zhí)行有窮的操作步驟之后結(jié)束。2、確定性、確定性 算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能含糊其詞，必須是唯一確定的，既不能含糊其詞，也不能有二義性。也不能有二義性。3、可行性、可行性 算法中的每一個(gè)步驟都是可以在有算法中的每一個(gè)步驟都是可以在有限的時(shí)間內(nèi)完成的基本操作，并能得限的時(shí)間內(nèi)完成的基本操作，并能得到確定的結(jié)果到確定的結(jié)果 。注注:與一般的解決問(wèn)題的過(guò)程比較與一般的解決問(wèn)題的過(guò)程比較,算法有以下算法有以下特

15、征特征:設(shè)計(jì)一個(gè)具體問(wèn)題的算法時(shí)設(shè)計(jì)一個(gè)具體問(wèn)題的算法時(shí),與過(guò)去熟悉地與過(guò)去熟悉地解數(shù)學(xué)題的過(guò)程有直接的聯(lián)系解數(shù)學(xué)題的過(guò)程有直接的聯(lián)系,但這個(gè)過(guò)程必但這個(gè)過(guò)程必須被分解成若干個(gè)明確的步驟須被分解成若干個(gè)明確的步驟,而且這些步驟而且這些步驟必須是有效的必須是有效的.算法要算法要“面面俱到面面俱到”,不能省略任何一個(gè)細(xì)不能省略任何一個(gè)細(xì)小的步驟小的步驟,只有這樣只有這樣,才能在人設(shè)計(jì)出算法后才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成.計(jì)算機(jī)解決任何問(wèn)題都要依計(jì)算機(jī)解決任何問(wèn)題都要依賴(lài)于算法賴(lài)于算法.只有將解決問(wèn)題的過(guò)程只有將解決問(wèn)題的過(guò)程分解為若干個(gè)明確的步驟分解為若干個(gè)明確的步驟,即算法即算法,并用計(jì)算機(jī)能夠接受的并用計(jì)算機(jī)能夠接受的“語(yǔ)言語(yǔ)言”準(zhǔn)確地描述出來(lái)準(zhǔn)確地描述出來(lái),計(jì)算機(jī)才能夠解計(jì)算機(jī)才能夠解決問(wèn)題決問(wèn)題.練習(xí)一練習(xí)一:任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積算法求以這個(gè)數(shù)為半徑的圓的面積.算法分析算法分析:第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r;第二步第二步:計(jì)算以計(jì)算以r為半徑的圓的面積為半徑的圓的面積S=r2;第三步第三步:輸出圓的面積輸出圓的面積.練習(xí)二練習(xí)二