必修三算法的概念

1、,第一章,算法初步,1.1.1,算法的概念,一個(gè)人帶著三只狼和三只羊過(guò)河，,只有一條船，同船可容納一個(gè)人和兩,只動(dòng)物，沒(méi)有人在的時(shí)候，如果狼的,數(shù)量不少于羊的數(shù)量狼就會(huì)吃羊,.,該人,如何將動(dòng)物轉(zhuǎn)移過(guò)河？,問(wèn)題提出,?,1,?,p,?,?,?,?,2,?,t,5730,1.,用計(jì)算機(jī)解二元一次方程組,exe,2.,在上述解二元一次方程組的過(guò)程中，,計(jì)算機(jī)是按照一定的指令來(lái)工作的，其,中最基礎(chǔ)的數(shù)學(xué)理論就是,算法,，本節(jié)課,我們就來(lái)學(xué)習(xí),:,知識(shí)探究（一）：算法的概念,思考,1:,在初中，對(duì)于解二元一次方程組,你學(xué)過(guò)哪些方法？,加減消元法和代入消元法,思考,2,：用加減消元法解二元一次方程組,x

2、-2y=-1,2x+y=1,的具體步驟是什么？,思考,2:,用加減消元法解二元一次方程組,x,?,?,2,y,?,?,1,的具體步驟是什么？,?,?,2,x,?,y,?,1,?,x,?,2,y,?,?,1,?,?,2,x,?,y,?,1,第一步，,+,2,，得,5x=1 .,第二步，,x,?,1,5,第三步，,第四步，,第五步，,解，得,x,?,1,5,.,-,2,，得,5y,3,.,解，得,.,y,?,3,5,?,?,x,1,得到方程組的解為,?,?,?,5,?,?,y,?,3,?,5,.,思考,3:,參照上述思路，一般地，解方程,a,1,x,?,b,1,y,?,c,1,（,a,1,b,2,

3、?,a,2,b,1,?,0,）,組,的基,a,2,x,?,b,2,y,?,c,2,本步驟是什么？,第一步,，,b,2,-,b,1,，得,(,a,1,b,2,?,a,2,b,1,),x,?,b,2,c,1,?,b,1,c,2,.,b,2,c,1,?,b,1,c,2,x,?,第二步,，解,，得,.,a,1,b,2,?,a,2,b,1,a,第三步,，,a,-,2,，得,1,(,a,1,b,2,?,a,2,b,1,),y,?,a,1,c,2,?,a,2,c,1,.,a,1,c,2,?,a,2,c,1,y,?,第四步,，解,，得,.,a,1,b,2,?,a,2,b,1,b,2,c,1,?,b,1,c,2

4、,x,?,a,1,b,2,?,a,2,b,1,a,1,c,2,?,a,2,c,1,y,?,a,1,b,2,?,a,2,b,1,第五步,，得到方程組的解為,思考,4:,根據(jù)上述分析，用加減消元法解,二元一次方程組，可以分為五個(gè)步驟進(jìn),行，這五個(gè)步驟就構(gòu)成了解二元一次方,程組的一個(gè),“算法”,.,我們?cè)俑鶕?jù)這一算,法編制計(jì)算機(jī)程序，就可以讓計(jì)算機(jī)來(lái),解二元一次方程組,.,那么解二元一次方程,組的,算法,包括哪些內(nèi)容？,思考,5:,一般地，算法是由,按照一定規(guī)則,解決某一類(lèi)問(wèn)題的基本步驟組成的,.,你認(rèn)為：,(1),這些步驟的個(gè)數(shù)是有限的還是無(wú)限,的？,(2),每個(gè)步驟是否有明確的計(jì)算任務(wù)？,思考,

5、6:,有人對(duì)哥德巴赫猜想,“任何大于,4,的,偶數(shù)都能寫(xiě)成兩個(gè)質(zhì)數(shù)之和”,設(shè)計(jì)了如下操,作步驟：,第一步，檢驗(yàn),6=3+3,，,第二步，檢驗(yàn),8=3+5,，,第三步，檢驗(yàn),10=5+5,，,利用計(jì)算機(jī)無(wú)窮地進(jìn)行下去！,請(qǐng)問(wèn)：這是一個(gè)算法嗎？,思考,7:,根據(jù)上述分析，你能歸納出,算法,的概念嗎？,在數(shù)學(xué)中，按照一定規(guī)則解決某一類(lèi)問(wèn),題的明確和有限的步驟,稱(chēng)為算法,.,一個(gè)人帶著三只狼和三只羊過(guò)河，,只有一條船，同船可容納一個(gè)人和兩,只動(dòng)物，沒(méi)有人在的時(shí)候，如果狼的,數(shù)量不少于羊的數(shù)量狼就會(huì)吃羊,.,該人,如何將動(dòng)物轉(zhuǎn)移過(guò)河？,分析：任何動(dòng)物同船不用考慮動(dòng)物的爭(zhēng)斗但需考慮,承載的數(shù)量，還應(yīng)考慮到

6、兩岸的動(dòng)物都得保證狼的,數(shù)量要小于羚羊的數(shù)量，故在算法的構(gòu)造過(guò)程中盡,可能保證船里面有狼，這樣才能使得兩岸的羚羊數(shù),量占到優(yōu)勢(shì),.,解：具體算法如下：,算法步驟：,第一步：人帶兩只狼過(guò)河，并自己返回,.,第二步：人帶一只狼過(guò)河，自己返回,.,第三步：人帶兩只羚羊過(guò)河，并帶兩只狼,返回,.,第四步：人帶一只羊過(guò)河，自己返回,.,第五步：人帶兩只狼過(guò)河,.,知識(shí)探究（二）,:,算法的步驟設(shè)計(jì),思考,1:,如果讓計(jì)算機(jī)判斷,7,是否為質(zhì)數(shù)，如,何設(shè)計(jì)算法步驟？,第一步,，用,2,除,7,，得到余數(shù),1,所以,2,不能整除,7.,第二步,，用,3,除,7,，得到余數(shù),1,所以,3,不能整除,7.,第三

7、步,，用,4,除,7,，得到余數(shù),3,所以,4,不能整除,7.,第四步,，用,5,除,7,，得到余數(shù),2,所以,5,不能整除,7.,第五步,，用,6,除,7,，得到余數(shù),1,所以,6,不能整除,7.,因此，,7,是質(zhì)數(shù),.,思考,2:,如果讓計(jì)算機(jī)判斷,35,是否為質(zhì)數(shù)，如,何設(shè)計(jì)算法步驟？,第一步,，用,2,除,35,，得到余數(shù),1,所以,2,不能整除,35.,，用,，用,，用,3,除,35,，得到余數(shù),4,除,35,，得到余數(shù),5,除,35,，得到余數(shù),因此，,2,所以,3,不能整除,35.,3,所以,4,不能整除,35.,0,所以,5,能整除,35.,不是質(zhì)數(shù),.,第二步,第三步,第四步

8、,35,思考,3:,整數(shù),89,是否為質(zhì)數(shù)？如果讓計(jì)算,機(jī)判斷,89,是否為質(zhì)數(shù)，按照上述算法需,要設(shè)計(jì)多少個(gè)步驟？,第一步,，用,2,除,89,，得到余數(shù),1,所以,2,不能整除,89.,第二步,，用,3,除,89,，得到余數(shù),2,所以,3,不能整除,89.,第三步,，用,4,除,89,，得到余數(shù),1,所以,4,不能整除,89., ,第八十七步,，用,88,除,89,，得到余數(shù),1,所以,88,不能,整除,89.,因此，,89,是質(zhì)數(shù),.,思考,4:,用,2,88,逐一去除,89,求余數(shù)，需要,87,個(gè),步驟，這些步驟基本是重復(fù)操作，我們可以,按下面的思路改進(jìn)這個(gè)算法，減少算法的步,驟,.,

9、（,1,）用,i,表示,2,88,中的任意一個(gè)整數(shù)，并從,2,開(kāi)始取數(shù)；,（,2,）用,i,除,89,，得到余數(shù),r.,若,r=0,，則,89,不,是質(zhì)數(shù)；若r0，將,i,用,i+1,替代，再執(zhí)行同,樣的操作；,（,3,）這個(gè)操作一直進(jìn)行到,i,取,88,為止,.,你能按照這個(gè)思路，設(shè)計(jì)一個(gè)“判斷,89,是否,為質(zhì)數(shù)”的算法步驟嗎？,算法設(shè)計(jì),:,第一步，,令,i=2,；,用,i,除,89,，得到余數(shù),r,；,若,r=0,，則,89,不是質(zhì)數(shù)，結(jié)束算,法；若r0，將,i,用,i+1,替代；,判斷“,i,88”是否成立？若是，,則,89,是質(zhì)數(shù)，結(jié)束算法；否則，,返回第二步,.,第二步，,第三步

10、，,第四步，,思考,5:,一般地，判斷一個(gè)大于,2,的整數(shù)是否,為質(zhì)數(shù)的算法步驟如何設(shè)計(jì)？,第一步,，給定一個(gè)大于,2,的整數(shù),n,；,，用,，判斷“r=0”是否成立,令,i=2,；,i,除,n,，得到余數(shù),r,；,.,若是，則,n,不是質(zhì)數(shù)，結(jié)束算法；否則，將,i,的值增加,1,，仍用,i,表示；,i(n-,1)”是否成立，若是，,則,n,是質(zhì)數(shù)，結(jié)束算法；否則，返回,第三步,.,第二步，,第三步,第四步,第五步，判斷“,理論遷移,例,設(shè)函數(shù),f(x),的圖象是一條連續(xù),不斷的曲線，寫(xiě)出用“二分法”求方程,的一個(gè)近似解的算法,.,f(x)=0,第一步，,取函數(shù),f(x),，給定精確度,d.,

11、a+b,第三步，,取區(qū)間中點(diǎn),.,m,2,第二步，,確定區(qū)間,a,，,b,，滿(mǎn)足,f(,a,),f(b),0.,第四步，,若,f(,a,),f(m),0,則含零點(diǎn)的區(qū)間,為,a,m,否則，含零點(diǎn)的區(qū)間為,m,，,b.,將新得到的含零點(diǎn)的區(qū)間仍記為,a,b;,第五步，,判斷,a,b,的長(zhǎng)度是否小于,d,或,f(m),是否等于,0.,若是，則,m,是方程的近似解；,否則，返回第三步,.,對(duì)于方程,x,?,2,?,0(,x,?,0),給定,d=0.005.,|a-b|,1,0.5,0.25,0.125,0.062 5,0.031 25,0.015 625,0.007 812 5,1.414 062 5,1.417 968 75,0.003 906 25,a,1,1,1.25,1.375,1.375,1.406 25,1.406 25,1.414 625,b,2,1.5,1.5,1.5,1.437 5,1.437 5,1.421 875,1.421 875,2,小結(jié)作業(yè),算法是建立在解法基礎(chǔ)上的操作過(guò)程，算法,不一定要有運(yùn)算結(jié)果，問(wèn)題答案可以由計(jì)算機(jī)解,決設(shè)計(jì)一個(gè)解決某類(lèi)問(wèn)題的算法的核心內(nèi)容是,設(shè)計(jì)算法的步驟，它沒(méi)有一個(gè)固定