1）算法的概念

1、12022-4-182引例引例1：填高考報(bào)名表：填高考報(bào)名表拿到準(zhǔn)考證拿到準(zhǔn)考證參加考試參加考試填志愿填志愿得到錄取通知書得到錄取通知書到大學(xué)報(bào)名注冊(cè)到大學(xué)報(bào)名注冊(cè) 一、情景引入：一、情景引入：引例2：把大象關(guān)進(jìn)冰箱里的過程1。把冰箱打開。把冰箱打開2。把大象放進(jìn)冰箱。把大象放進(jìn)冰箱3。關(guān)上冰箱門。關(guān)上冰箱門引例引例3：一個(gè)獵人帶一條狗，一只雞，一袋米過河，：一個(gè)獵人帶一條狗，一只雞，一袋米過河，每次只能帶一樣?xùn)|西過河，如果雞狗被剩在一起，每次只能帶一樣?xùn)|西過河，如果雞狗被剩在一起，狗就會(huì)吃雞狗就會(huì)吃雞;如果雞米被剩在一起，雞就會(huì)吃米。求如果雞米被剩在一起，雞就會(huì)吃米。求獵人帶這三樣?xùn)|西過河的

2、順序獵人帶這三樣?xùn)|西過河的順序 2022-4-183引例引例4：解方程組：解方程組2121xyxy 第二步：解第二步：解得得 35y 第一步：第一步： -2，得，得5y=3 第三步：將第三步：將 代入代入， 得得15x 35y 第四步：得到方程組的解第四步：得到方程組的解 15x 35y 2022-4-184寫出一般二元一次方程組的解法步驟寫出一般二元一次方程組的解法步驟. .1111 22 1222(1)0(2)a xb ycaba ba xb yc 第一步第一步,21(1)(2)bb得 ：12211221a ba bxc bc b（ 3） 第二步第二步,解（解（3）得）得 12211221

3、c bc bxa ba b2022-4-185寫出一般二元一次方程組的解法步驟寫出一般二元一次方程組的解法步驟. .1111 22 1222(1)0(2)a xb ycaba ba xb yc 2 11 22 11 2a ca cya bab 第四步第四步,解（解（4）得）得 21(1)(2)aa得：第三步第三步,2 11 22 11 2a ba bya ca c（4） 第五步第五步,得到方程組的解為得到方程組的解為 1221122121122112c bc bxa ba ba ca cya ba b2022-4-186算法算法：在數(shù)學(xué)中，現(xiàn)代意義上的在數(shù)學(xué)中，現(xiàn)代意義上的“算法算法”通常是指

4、可以通常是指可以 用計(jì)算機(jī)來解決的某一類問題的程序或步驟，用計(jì)算機(jī)來解決的某一類問題的程序或步驟， 這些程序和步驟必須是明確和有效的，而且能這些程序和步驟必須是明確和有效的，而且能 夠在有限步之內(nèi)完成。夠在有限步之內(nèi)完成。 算法的特點(diǎn)：算法的特點(diǎn)：1.有序性有序性2.明確性：每一步都應(yīng)該是能有效執(zhí)行且有確定的結(jié)果，明確性：每一步都應(yīng)該是能有效執(zhí)行且有確定的結(jié)果， 而不應(yīng)該是模棱兩可的；而不應(yīng)該是模棱兩可的；3.有限性：應(yīng)能在有限步內(nèi)解決問題有限性：應(yīng)能在有限步內(nèi)解決問題.2022-4-187隨著計(jì)算機(jī)的出現(xiàn)，人們常把這些隨著計(jì)算機(jī)的出現(xiàn)，人們常把這些“步驟步驟”編寫編寫為為“程序程序”由計(jì)算機(jī)

5、來解決。由計(jì)算機(jī)來解決。在數(shù)學(xué)中，主在數(shù)學(xué)中，主要研究計(jì)算機(jī)能實(shí)現(xiàn)的算法，即按照某要研究計(jì)算機(jī)能實(shí)現(xiàn)的算法，即按照某種機(jī)械程序步驟一定可以得到結(jié)果的解種機(jī)械程序步驟一定可以得到結(jié)果的解決問題的程序。決問題的程序。比如解方程的算法、函數(shù)求值的算法、比如解方程的算法、函數(shù)求值的算法、作圖的算法，等等。作圖的算法，等等。2022-4-188例題例題1（1）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)一個(gè)算法，判斷7是否為質(zhì)數(shù)是否為質(zhì)數(shù)（2）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)一個(gè)算法，判斷35是否為質(zhì)數(shù)是否為質(zhì)數(shù) 2022-4-189例例1.(1).(1)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷7 7是否為質(zhì)數(shù)是否為質(zhì)數(shù). .第一步第一步

6、, 用用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.第四步第四步, 用用5除除7,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以5不能整除不能整除7.第五步第五步, 用用6除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以6不能整除不能整除7.因此，因此，7是質(zhì)數(shù)是質(zhì)數(shù).2022-4-1810例例1.(2

7、).(2)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷3535是否為質(zhì)是否為質(zhì)數(shù)數(shù). .第一步第一步, 用用2除除35,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以2不能整除不能整除35.第二步第二步, 用用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ù).2022-4-1811設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算

8、法,判斷整數(shù)判斷整數(shù)n(n2)是否為質(zhì)數(shù)是否為質(zhì)數(shù)?第一步，給定大于第一步，給定大于2的整數(shù)的整數(shù)n。第二步，令第二步，令i=2第三步，用第三步，用i除除n，得到余數(shù)，得到余數(shù)r。第四步，判斷第四步，判斷“r=0”是否成立。是否成立。第五步，判斷第五步，判斷“i(n-1)”是否成立。是否成立。 若是，則若是，則n不是質(zhì)不是質(zhì)數(shù)，結(jié)束算法數(shù)，結(jié)束算法; 否則，將否則，將i的值增加的值增加1，仍用，仍用i表示。表示。 若是，則若是，則n不是不是質(zhì)數(shù)，結(jié)束算法質(zhì)數(shù)，結(jié)束算法; 否則，返回第三步否則，返回第三步2022-4-1812例例2.用二分法設(shè)計(jì)一個(gè)求方程用二分法設(shè)計(jì)一個(gè)求方程x2-2=0是近似

9、根的算法。是近似根的算法。算法分析：假設(shè)精確度為算法分析：假設(shè)精確度為0.005第一步：令第一步：令f(x)=x2-2，因?yàn)?，因?yàn)閒 (1)0，所以設(shè)，所以設(shè)a=1，b=2；2abm第二步：令第二步：令 ，判斷，判斷f (m)是否為是否為0，若是，則，若是，則m為所求；為所求； 若否，則繼續(xù)判斷若否，則繼續(xù)判斷f (a)f (m)大于大于0還是小于還是小于0；|-|?0.005a ba b第第四四步步：判判斷斷是是否否成成立立 若若是是, ,則則、均均為為滿滿足足條條件件的的近近似似根根；若若否否，則則返返回回第第二二步步. .之之間間的的任任 意意取取值值第第五五步步：輸輸出出方方程程的的根

10、根. .,;, 0)()(babmmamfaf區(qū)區(qū)間間仍仍記記為為將將新新得得到到的的含含零零點(diǎn)點(diǎn)否否則則，含含零零點(diǎn)點(diǎn)的的區(qū)區(qū)間間為為則則含含零零點(diǎn)點(diǎn)的的區(qū)區(qū)間間為為第第三三步步：若若2022-4-1813 ab |a-b|12111.50.51.251.50.251.3751.50.1251.3751.43750.06251.406251.43750.031251.406251.4218750.0156251.41406251.4218750.00781251.41406251.417968750.003906252022-4-18141 1. .任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù), ,

11、設(shè)計(jì)一個(gè)算法求設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積以這個(gè)數(shù)為半徑的圓的面積. .第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r；第二步第二步:計(jì)算圓的面積計(jì)算圓的面積: S=r2;第三步第三步:輸出圓的面積輸出圓的面積S.練習(xí)練習(xí)2022-4-18152.2.任意給定一個(gè)大于任意給定一個(gè)大于1 1 的正整數(shù)的正整數(shù)n,n,設(shè)計(jì)一個(gè)算設(shè)計(jì)一個(gè)算法求出法求出n n的所有因數(shù)的所有因數(shù). .答案答案1：第一步：依次以第一步：依次以2(n-1)為除數(shù)去除為除數(shù)去除n,檢查余數(shù)檢查余數(shù)是否為是否為0,若是若是,則是則是n的因數(shù)的因數(shù);若不是若不是,則不是則不是n的因數(shù)的因數(shù).第二步：在第二步：在

12、n的因數(shù)中加入的因數(shù)中加入1和和n.第三步：輸出第三步：輸出n的所有因數(shù)的所有因數(shù).答案答案2:第一步第一步:給定大于給定大于1的整數(shù)的整數(shù)n第二步第二步:令令i=1第三步第三步:用用i除除n,得余數(shù)得余數(shù)r第四步第四步:判斷判斷“ r=0” 是否成立是否成立,若是若是, ,則則i是是n的因數(shù)的因數(shù),輸出輸出i, 第五步第五步:將將i的值增加的值增加1,仍用仍用i表示表示.第六步第六步:判斷判斷“in結(jié)束算法結(jié)束算法,否則返回第三步否則返回第三步.2022-4-18163.試給出一個(gè)判斷一元二次方程試給出一個(gè)判斷一元二次方程ax2+bx+c=0解的解的 個(gè)數(shù)的算法。個(gè)數(shù)的算法。算法：算法：第一步：輸入第一步：輸入a、b、c的值的值.第二步：計(jì)算第二步：計(jì)算 =b2-4ac的值的值.第三步：若第三步：若 0，則原方程有兩個(gè)不等的實(shí)根；，則原方程有兩個(gè)不等的實(shí)根； 若若 =0，則原方程只有一個(gè)實(shí)根；，則原方程只有一個(gè)實(shí)根； 若若 2x