必修三算法的概念

1、,第一章,算法初步,1.1.1,算法的概念,一個人帶著三只狼和三只羊過河，,只有一條船，同船可容納一個人和兩,只動物，沒有人在的時候，如果狼的,數(shù)量不少于羊的數(shù)量狼就會吃羊,.,該人,如何將動物轉(zhuǎn)移過河？,問題提出,?,1,?,p,?,?,?,?,2,?,t,5730,1.,用計算機解二元一次方程組,exe,2.,在上述解二元一次方程組的過程中，,計算機是按照一定的指令來工作的，其,中最基礎(chǔ)的數(shù)學理論就是,算法,，本節(jié)課,我們就來學習,:,知識探究（一）：算法的概念,思考,1:,在初中，對于解二元一次方程組,你學過哪些方法？,加減消元法和代入消元法,思考,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òu)成了解二元一次方,程組的一個,“算法”,.,我們再根據(jù)這一算,法編制計算機程序，就可以讓計算機來,解二元一次方程組,.,那么解二元一次方程,組的,算法,包括哪些內(nèi)容？,思考,5:,一般地，算法是由,按照一定規(guī)則,解決某一類問題的基本步驟組成的,.,你認為：,(1),這些步驟的個數(shù)是有限的還是無限,的？,(2),每個步驟是否有明確的計算任務(wù)？,思考,

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

6、兩岸的動物都得保證狼的,數(shù)量要小于羚羊的數(shù)量，故在算法的構(gòu)造過程中盡,可能保證船里面有狼，這樣才能使得兩岸的羚羊數(shù),量占到優(yōu)勢,.,解：具體算法如下：,算法步驟：,第一步：人帶兩只狼過河，并自己返回,.,第二步：人帶一只狼過河，自己返回,.,第三步：人帶兩只羚羊過河，并帶兩只狼,返回,.,第四步：人帶一只羊過河，自己返回,.,第五步：人帶兩只狼過河,.,知識探究（二）,:,算法的步驟設(shè)計,思考,1:,如果讓計算機判斷,7,是否為質(zhì)數(shù)，如,何設(shè)計算法步驟？,第一步,，用,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:,如果讓計算機判斷,35,是否為質(zhì)數(shù)，如,何設(shè)計算法步驟？,第一步,，用,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ù)？如果讓計算,機判斷,89,是否為質(zhì)數(shù)，按照上述算法需,要設(shè)計多少個步驟？,第一步,，用,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,個,步驟，這些步驟基本是重復(fù)操作，我們可以,按下面的思路改進這個算法，減少算法的步,驟,.,

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

10、，,第四步，,思考,5:,一般地，判斷一個大于,2,的整數(shù)是否,為質(zhì)數(shù)的算法步驟如何設(shè)計？,第一步,，給定一個大于,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ù),不斷的曲線，寫出用“二分法”求方程,的一個近似解的算法,.,f(x)=0,第一步，,取函數(shù),f(x),，給定精確度,d.,

11、a+b,第三步，,取區(qū)間中點,.,m,2,第二步，,確定區(qū)間,a,，,b,，滿足,f(,a,),f(b),0.,第四步，,若,f(,a,),f(m),0,則含零點的區(qū)間,為,a,m,否則，含零點的區(qū)間為,m,，,b.,將新得到的含零點的區(qū)間仍記為,a,b;,第五步，,判斷,a,b,的長度是否小于,d,或,f(m),是否等于,0.,若是，則,m,是方程的近似解；,否則，返回第三步,.,對于方程,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ǔ)上的操作過程，算法,不一定要有運算結(jié)果，問題答案可以由計算機解,決設(shè)計一個解決某類問題的算法的核心內(nèi)容是,設(shè)計算法的步驟，它沒有一個固定