算法初步課件1.1算法的概念

1、x為什么要學(xué)習(xí)算法為什么要學(xué)習(xí)算法? ? 計(jì)算機(jī)與算法:在現(xiàn)代社會里，計(jì)算機(jī)已經(jīng)成為人們?nèi)粘Ｉ詈凸ぷ鞑豢扇鄙俚墓ぞ呗犚魳?、看電影、玩游戲、畫卡通畫、處理?shù)據(jù)計(jì)算機(jī)幾乎可以是一個(gè)全能的助手，你可以用它來做你想做的任何事情那么，計(jì)算機(jī)是怎樣工作呢？要想弄清楚這個(gè)問題，就需要學(xué)習(xí)算法 二元一次方程組二元一次方程組 12 12yxyx的求解過程的求解過程.歸納它的步驟歸納它的步驟:第一步第一步: -2，得，得 5y=3 第三步第三步:5153xy，得代入將第二步第二步: 解解得得 y= 53第二步第二步: 解解得得 y= 53思考？0 1221222111babacybxacybxa其中一般的二元一

2、次方程組第二步：解第二步：解，得，得12211221babacacay第一步：第一步： - - ，得，得 1a2a12211221)(cacaybaba第三步：將第三步：將 代入代入，得，得12211221babacacay12212112babacbcbx1、算法的概念：、算法的概念：在數(shù)學(xué)中在數(shù)學(xué)中“算法算法”通常是指按照一定的規(guī)則來通常是指按照一定的規(guī)則來解決的某一類問題的解決的某一類問題的明確和有限的步驟明確和有限的步驟，這些，這些步驟必須是步驟必須是明確明確和和有效有效的，而且能夠在的，而且能夠在有限步有限步之內(nèi)完成。之內(nèi)完成。3.算法的基本思想與特征算法的基本思想與特征:2.算法的

3、表示方法：算法的表示方法：自然語言、程序框圖、程序自然語言、程序框圖、程序(1)解決某一類問題解決某一類問題(2)在在有限步有限步之內(nèi)完成之內(nèi)完成(3)每一步的明確性和有效性每一步的明確性和有效性(4)每一步具有順序性每一步具有順序性(一般性一般性)(有限性有限性)(確定與可行性確定與可行性)(順序性順序性) 一般書上歸納算法的基本性質(zhì)有四條： a.有窮性；b. 唯一的初始動作； c.每個(gè)動作都有唯一的后繼動作；d.動作序列終止時(shí)，表示問題得到解答或沒有解答練習(xí)練習(xí)判斷下列關(guān)于算法的說法是否確：判斷下列關(guān)于算法的說法是否確：1、求解某一類問題的算法是唯一的；、求解某一類問題的算法是唯一的；2、

4、算法必須在有限步操作之后停止：、算法必須在有限步操作之后停止：3、算法的每一步必須是明確的，不能有歧、算法的每一步必須是明確的，不能有歧義或模糊：義或模糊：4、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果：、算法執(zhí)行后一定產(chǎn)生確定的結(jié)果：例題例題1 思考：任意給定一個(gè)大于思考：任意給定一個(gè)大于2的整數(shù)的整數(shù)n，試設(shè)計(jì)，試設(shè)計(jì)一個(gè)算法對一個(gè)算法對n是否為質(zhì)數(shù)做出判定是否為質(zhì)數(shù)做出判定. .(2).設(shè)計(jì)一個(gè)算法，判斷設(shè)計(jì)一個(gè)算法，判斷35是否為質(zhì)數(shù)？是否為質(zhì)數(shù)？(1).設(shè)計(jì)一個(gè)算法，判斷設(shè)計(jì)一個(gè)算法，判斷7是否為質(zhì)數(shù)？是否為質(zhì)數(shù)？ 分析：1二分法求方程近似解是通過求對應(yīng)函數(shù)的近似零點(diǎn)得到的，所以首先要建立函數(shù)，而

5、且要有具體精確度要求，因此第一步應(yīng)該怎么做？ 2二分法分的是什么？ 3如何確定新區(qū)間的端點(diǎn)？ 4如何表達(dá)出反復(fù)二分區(qū)間的過程？ 例例2、用二分法設(shè)計(jì)一個(gè)求方程、用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近的近似根的算法（精確度為似根的算法（精確度為0.005）. .例例2、用二分法設(shè)計(jì)一個(gè)求方程、用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近的近似根的算法（精確度為似根的算法（精確度為0.005）. .第一步：令f(x)=x2-2，給定精確度d. ,0f af b第二步：確定區(qū)間 a,b 滿足；;a+b第三步：取區(qū)間中點(diǎn)m=2 0,.f af m第四步：若，則含零點(diǎn)的區(qū)間為 a,m否則為 m，b 將新得到的

6、區(qū)間仍記為 a,b df m第五步：判斷區(qū)間 a,b 的長度是否小于 或是否等于0；若是，則m即為所求方程的近似解，不是，則返回第三步。課堂練習(xí)課堂練習(xí)1、任意給定一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半、任意給定一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積。徑的圓的面積。算法步驟：第一步：輸入任意一個(gè)正實(shí)數(shù)r。第二步：計(jì)算以r為半徑的圓的面積 。2sr第三步：輸出圓的面積s。2、任意給定一個(gè)大于、任意給定一個(gè)大于1的正整數(shù)的正整數(shù)n，設(shè)計(jì)一個(gè)算法，設(shè)計(jì)一個(gè)算法求出求出n的所有因數(shù)。的所有因數(shù)。算法步驟：第一步：依次以2（n-1）為除數(shù)去除n，判定余數(shù)是否為0，若是，則n是因數(shù)；若不是，則