_111算法與程序框圖_

1、問題的提出問題的提出 有一個農夫帶一條狼狗、一只羊和有一個農夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農夫看管，則一筐白菜過河。如果沒有農夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只夠農夫帶一樣東西過河。問農夫該如只夠農夫帶一樣東西過河。問農夫該如何解此難題？何解此難題？ 方法和過程方法和過程：1、帶羊到對岸，返回；帶羊到對岸，返回；2、帶菜到對岸，并把羊帶回；帶菜到對岸，并把羊帶回；3、帶狼狗到對岸，返回；帶狼狗到對岸，返回；4、帶羊到對岸。帶羊到對岸。1.1.1 算法的概念算法的概念問題問題請你寫出解二元一次方程組的詳細求解過請你寫出解二元一次方程

2、組的詳細求解過程程. 2121xyxy 第一步第一步: +2得得: 5x=1 第二步第二步: 解解得得:15x 第三步第三步: - 2，得，得 5y=3 第四步：解第四步：解 ，得，得 53y第五步：得方程組的解第五步：得方程組的解5351yx 你能你能寫出解一般的二元一次方程組的步寫出解一般的二元一次方程組的步 驟嗎？驟嗎？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 思考思考這這 兩個解方程組的兩個解方程組的算法算法的適用范圍有何不同？的適用范圍有何不同？2 11 22 11 2()a babya ca c第一步：第一步：第二步：第二步：第三步：第三步：第二步第二步：計算：計算第三步第三步：給出運算結果。：給出運算結果。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)在你對算法有了新現(xiàn)在你對算法有

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

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

7、泛地談算法是沒有意義的。義的。說明說明 例題例題1.(1).(1)設計一個算法判斷設計一個算法判斷7 7是否為質數(shù)是否為質數(shù). .第一步第一步, 用用2除除7,得到余數(shù)得到余數(shù)1.因為余數(shù)不為因為余數(shù)不為0，所以，所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余數(shù)得到余數(shù)1.因為余數(shù)不為因為余數(shù)不為0，所以，所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余數(shù)得到余數(shù)3.因為余數(shù)不為因為余數(shù)不為0，所以，所以4不能整除不能整除7.第五步第五步, 用用6除除7,得到余數(shù)得到余數(shù)1.因為余數(shù)不為因為余數(shù)不為0，所以，所以6不能整除不能整除7. 因此，因此，7是質數(shù)是質數(shù).

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

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

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

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

12、a,b.第五步第五步,判斷判斷f(m)是否等于或者是否等于或者a,b的長的長度是否小于度是否小于d，若是，則，若是，則m是方程的近似解是方程的近似解;否否則，返回第三步則，返回第三步當當d d=0.005=0.005時，按照以上算法，可得下面表和圖時，按照以上算法，可得下面表和圖. .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 于是，開區(qū)間于是，開區(qū)間（1.4140625,1.41796875）中）中的實數(shù)都是當精確度為的實數(shù)都是當精確度為0.005時的原方程的近時的原方程的近似解似解.算法的

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

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