算法的概念田佩

1.1.1算法的概念第一章算法初步

1一、情景引入：引例2：把大象關進冰箱里的過程1。把冰箱打開2。把大象放進冰箱3。關上冰箱門引例3：一個獵人帶一條狗，一只雞，一袋米過河，每次只能帶一樣東西過河，如果雞狗被剩在一起，狗就會吃雞;如果雞米被剩在一起，雞就會吃米。求獵人帶這三樣東西過河的順序1/13/20232先帶雞過河，再帶狗，回來的路上把雞帶回來，再把米帶過河，最后再把雞帶過河1/13/20233假設要喝一杯茶有以下幾個步驟：a.燒水b.洗刷水壺c.找茶葉d.洗刷茶具e.沏茶1/13/20234

①+②×2，得5x=1.③

解③，得.

②-①×2，得5y＝3

.④

解④，得.第一步，第二步，第三步，第四步，第五步，

得到方程組的解為

.

新課引入解二元一次方程組1/13/20235問題2:寫出的求解步驟.②①第一步，①×-②×，得

.③第二步，解③

，得.

第三步，②×-

①×，得

.④第四步，解④

，得.

第五步，得到方程組的解為這五個步驟就是解二元一次方程組的一個算法.1/13/20236算法：廣義地說，算法就是做某一件事的步驟或程序。菜譜是做菜的算法，洗衣機的使用說明書是操作洗衣機的算法，在數(shù)學中，現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟，這些程序和步驟必須是明確和有效的，而且能夠在有限步之內完成。

1/13/20237隨著計算機的出現(xiàn)，人們常把這些“步驟”編寫為“程序”由計算機來解決。在數(shù)學中，主要研究計算機能實現(xiàn)的算法，即按照某種機械程序步驟一定可以得到結果的解決問題的程序。比如解方程的算法、函數(shù)求值的算法、作圖的算法，等等。1/13/20238算法的特點：1.有序性：算法中的每一個步驟都是確切的,能有效的執(zhí)行且得到確定的結果,不能模棱兩可2.明確性：每一步都應該是能有效執(zhí)行且有確定的結果，而不應該是模棱兩可的；3.有限性：應能在有限步內解決問題.4.不唯一性：求解某一個問題的解法不一定是唯一的,對于同一個問題可以有不同的解法,但算法有優(yōu)劣之分,好的算法是我們追求的目標5.普遍性：寫出的算法必須能解決一類問題,并且能重復使用,這是設計算法的一條基本原則,這樣才能使算法更有價值.1/13/20239例題1（1）設計一個算法，判斷7是否為質數(shù)（2）設計一個算法，判斷35是否為質數(shù)

（3）設計一個算法，判斷1997是否為質數(shù)

1/13/202310例題講解例1：設計一個算法,判斷7是否為質數(shù).第一步，用2除7，得到余數(shù)1,所以2不能整除7.第四步，用5除7，得到余數(shù)2,所以5不能整除7.第五步，用6除7，得到余數(shù)1,所以6不能整除7.

第二步，用3除7，得到余數(shù)1,所以3不能整除7.第三步，用4除7，得到余數(shù)3,所以4不能整除7.因此，7是質數(shù).1/13/202311因此，7是質數(shù).第五步，用6除7，得到余數(shù)1,所以6不能整除7.

例題講解例2：設計一個算法,判斷35是否為質數(shù).第一步，用2除7，得到余數(shù)1,所以2不能整除7.第四步，用5除7，得到余數(shù)2,所以5不能整除7.

第二步，用3除7，得到余數(shù)1,所以3不能整除7.第三步，用4除7，得到余數(shù)3,所以4不能整除7.35353523535335350因為余數(shù)為0,所以35不是質數(shù)1/13/202312因此，7是質數(shù).第五步，用6除7，得到余數(shù)1,所以6不能整除7.

第1995步，用1996除1997，得到余數(shù)1,所以1996不能整除1997.所以1997是質數(shù)例題講解例2：設計一個算法,判斷1997是否為質數(shù).第一步，用2除7，得到余數(shù)1,所以2不能整除7.第四步，用5除7，得到余數(shù)2,所以5不能整除7.第二步，用3除7，得到余數(shù)1,所以3不能整除7.第三步，用4除7，得到余數(shù)3,所以4不能整除7.19971997199721997199711997…….1/13/202313…….

因此，7是質數(shù).第五步，用6除7，得到余數(shù)1,所以6不能整除7.

第1995步，用1996除1997，得到余數(shù)1,所以1996不能整除1997.所以1997是質數(shù)例題講解例2：設計一個算法,判斷1997是否為質數(shù).第一步，用2除7，得到余數(shù)1,所以2不能整除7.第二步，用3除7，得到余數(shù)1,所以3不能整除7.第三步，用4除7，得到余數(shù)3,所以4不能整除7.19971997199721997199711997令i=2用i除1997得到余數(shù)r；若r=0，則1997不是質數(shù)，算法結束；否則，給i增加1仍用i來表示；第四步，判斷i>1996,則1997是質數(shù)，否則返回第二步.1/13/202314探究:

一般地，判斷一個大于2的整數(shù)是否為質數(shù)的算法步驟如何設計？第一步，給定一個大于2的整數(shù)n；第二步，令i=2；

第三步，用i除n，得到余數(shù)r；

第四步，判斷“r=0”是否成立.若是，則n不是質數(shù)，結束算法；否則，將i的值增加1，仍用i表示；第五步，判斷“i>(n-1)”是否成立，若是， 則n是質數(shù)，結束算法；否則，返回 第三步.1/13/20231511.521.251.3752+2+1.5+1-ab︱a-b︱11211.50.51.50.251.251.50.1251.375………………12+1.5+1.251.375---2+1.5+1.251--1--例2用二分法設計一個求方程x2–2=0的近似根的算法。舊知識回顧：用二分法求函數(shù)的零點解決問題×第四步,

若f(a)·f(m)<0,則含零點的區(qū)間為［a,m］；第一步,

令.給定精確度d.第二步,

給定區(qū)間［a,b］,滿足f(a)·f(b)＜0．第三步,

取中間點．第五步,

判斷［a,b］的長度是否小于d或者f(m)是否等于０.將新得到的含零點的仍然記為［a,b］

.否則，含零點的區(qū)間為［m,b］.

若是，則m是方程的近似解;否則，返回第三步．4．下面的四種敘述不能稱為算法的是（）（A）廣播的廣播操圖解（B）歌曲的歌譜（C）做飯用米（D）做米飯需要刷鍋、淘米、添水、加熱這些步驟練習題C5．下列關于算法的說法正確的是（）（A）某算法可以無止境地運算下去（B）一個問題的算法步驟可以是可逆的（C）完成一件事情的算法有且只有一種（D）設計算法要本著簡單、方便、可操作的原則D例4.試給出一個判斷一元二次方程ax2+bx+c=0解的個數(shù)的算法。算法：第一步：輸入a、b、c的值.第二步：計算?

=b2-4ac的值.第三步：若?>0，則原方程有兩個不等的實根；若?=0，則原方程只有一個實根；若?<0，則原方程無實根.第四步：輸出結果.1/13/202320小結：1、算法的概念