1、1.1.1 算法的概念,普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書 人教A版數(shù)學(xué)必修3第一章 算法初步,在中央電視臺幸運(yùn)52節(jié)目中,有一個猜商品價格的環(huán)節(jié),竟猜者如在規(guī)定的時間內(nèi)大體猜出某種商品的價格,就可獲得該件商品.現(xiàn)有一商品,價格在0-8000元之間,采取怎樣的策略才能在短的時間內(nèi)說出正確(大體上)的答案呢?,第一步:報(bào)“4000”；,第二步:若主持人說高了(說明答案在04000之間),就報(bào)“2000”,否則(答數(shù)在40008000之間)報(bào)“6000”；,第三步:重復(fù)第二步的報(bào)數(shù)方法取中間數(shù),直至得到正確結(jié)果.,先去括號,再乘除,后加減,1、,什么是算法呢？,2 兩個男孩和兩個女孩一起渡河，渡口只有一條

2、小船每次只能渡1 個男孩或兩個女孩，他們四人都會劃 船，但都不會游泳試問他們怎樣渡過河去？請寫出一個渡河方案。,S1 兩個女孩同船過河去；,S2 一個女孩劃船回來；,S3 一個男孩劃船過河去；,S4 對岸的女孩劃船回來；,S5 兩個女孩同船渡過河去；,S6 一個女孩劃船回來；,S7 余下的一個男孩獨(dú)自劃船渡過河去； 對岸的女孩劃船回來；,S8 兩個女孩再同時劃船渡過河去。,智力大比拼,什么是算法呢？,討論,第一步：,第二步：,第三步：,（消元）,（解一元一次方程）,+2，得 ,解得,（帶入求解）,將 代入,得,寫一寫,寫出解第二個方程組的算法：,第一步：,第二步：,第三步：,解，得 ,將帶入得

3、,變一變,第一步：,第二步：,第三步：,解，得 ,將帶入得,解得,-,一：兩腿并攏，挺胸抬頭,三：先邁前腿,四：再邁后腿,下面的步驟表述明確嗎？,你對以下的“算法”如何理解？,要把大象裝冰箱，分幾步？,答：分三步：,第一步：打開冰箱門,第二步：把大象裝冰箱,第三步：關(guān)上冰箱門,問：,顯然有個問題：大像可以裝進(jìn)冰箱里嗎？這個算法有效嗎？,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？,解: 1.把銀元分成3組，每組3枚。,2先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。,3取出含假銀元

4、的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。,演示,有人對歌德巴赫猜想“任何大于4的偶數(shù)都能寫成兩個奇質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：,第一步：檢驗(yàn)6=3+3,第二步：檢驗(yàn)8=3+5,。,利用計(jì)算機(jī)無窮地進(jìn)行下去！,請問，利用這種程序能夠證明猜想的正確性嗎？,第三步：檢驗(yàn)10=5+5,這是一種算法嗎？,狹義而言,算法是專指用計(jì)算機(jī)解決某一問題的方法和步驟.著名計(jì)算機(jī)科學(xué)家D.E.Knuth在其計(jì)算機(jī)程序設(shè)計(jì)技巧一書中為算法所下的定義是：“一個算法,就是一個有窮規(guī)則的集合,其中之規(guī)則規(guī)定了一個解決某一特定類型問題的運(yùn)算系

5、列”.,一般地, 按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法(algorithm)。,1. 算法的概念,有限性： 一個算法的步驟序列是有限的，它應(yīng)在有限步操作之后停止，而不能是無限地執(zhí)行下去。,確定性： 算法中的每一步應(yīng)該是確定的并且能有效地執(zhí)行且得到確定的結(jié)果，而不應(yīng)當(dāng)是模棱兩可的。,不唯一性： 求解某一個問題的算法不一定只有唯一的一個，可以有不同的算法。,2.算法的特征：確定性、有限性、有效性 、不唯一性,有效性：必須能解決一類問題(例如解任意一個二元一次方程組),并且能重復(fù)使用。,3.算法的要求,(1)寫出的算法,必須能解決一類問題(例如解任意一個二元一次方程組),并且能重復(fù)使

6、用;,(2) 算法過程要能一步一步執(zhí)行,每一步執(zhí)行的操作,必須確切,不能含混不清,而且在有限步之內(nèi)完成后能得出結(jié)果.,例1 （1）設(shè)計(jì)一個算法，判斷7是否為質(zhì)數(shù)。 第一步，用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.因此，7是質(zhì)數(shù).,（2）設(shè)計(jì)一個算法，判斷35是否為質(zhì)數(shù)。 第一步，用2除35，得到余數(shù)1.因?yàn)橛鄶?shù)不為0，

7、所以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ù).,任意給定一個大于1的整數(shù)n，試設(shè)計(jì) 一個程序或步驟對n是否為質(zhì)數(shù)作出判斷。,第一步：給定大于2的整數(shù)n,第二步:,第三步:,第四步:,第五步:,例題,例2.用二分法設(shè)計(jì)一個求方程 x2-2=0 的近似根的算法.,算法分析:回顧二分法解方程的過程,并假設(shè)所求近似根與精確解的差的絕對值不超過0.005,則不難設(shè)計(jì)出以下步驟：,1二分法的概念 對于在區(qū)間a

8、，b上連續(xù)不斷且_的函數(shù)yf(x)，通過不斷地把函數(shù)f(x)的零點(diǎn)所在的區(qū)間_，使區(qū)間的兩個端點(diǎn)_，進(jìn)而得到零點(diǎn)近似值的方法叫做二分法 由函數(shù)的零點(diǎn)與相應(yīng)方程根的關(guān)系，我們可用二分法來求方程的_,f(a)f(b)0,一分為二,逐步逼近零點(diǎn),近似解,2給定精確度，用二分法求函數(shù)f(x)零點(diǎn)近似值的步驟 (1)確定區(qū)間a，b，驗(yàn)證_，給定精確度； (2)求區(qū)間(a，b)的中點(diǎn)c，c_； (3)計(jì)算f(c)： 若f(c)0，則c就是函數(shù)的零點(diǎn)；,f(a)f(b)0,若f(a)f(c)0，則令bc(此時零點(diǎn)x0_)； 若f(c)f(b)0，則令ac(此時零點(diǎn)x0_)； (4)判斷是否達(dá)到精確度：即若_，則得到零點(diǎn)近似值a(或b)；否則重復(fù)(2)(4),(a，c),(c，b),|ab|,例2.用二分法設(shè)計(jì)一個求方程 x2-2=0 的近似根的算法.,算法分析:回顧二分法解方程的過程,并假設(shè)所求近似根與精確解的差的絕對值不超過0.005,則不難設(shè)計(jì)出以下步驟：,解,解,評析:實(shí)際上,上述步驟就是在求 的近似值.,任意給定一個正實(shí)數(shù)a，試設(shè)計(jì)一個算法求以a為直徑的圓的面積.,第一步：輸入a