【課件】新課標(biāo)人教A版數(shù)學(xué)必修三1.1.1算法的概念（共32張ppt）

1、算法的概念第一章算法初步趣味益智游戲 一人帶著一只狼、一只羊和一箱蔬菜要過(guò)河,但只有一條小船.乘船時(shí)，每次只能帶狼、羊和蔬菜中的一種.當(dāng)有人在場(chǎng)時(shí)，狼、羊、蔬菜都相安無(wú)事.一旦人不在,狼會(huì)吃羊,羊會(huì)吃菜.請(qǐng)?jiān)O(shè)計(jì)一個(gè)方案,安全地將狼、羊和蔬菜帶過(guò)河.如何發(fā)電子郵件？假如你的朋友不會(huì)發(fā)電子郵件,你能教會(huì)他嗎?發(fā)郵件的方法很多,下面就是一種操作步驟.第一步 登錄電子信箱;第二步 點(diǎn)擊“寫(xiě)信”；第三步 輸入收件人地址；第四步 輸入主題；第五步 輸入信件內(nèi)容；第六步 點(diǎn)擊“發(fā)送”. 我們做任何一件事,都是在一定條件下按某種順序的一系列.解決數(shù)學(xué)問(wèn)題也常常如此,例如用加減消元法解二元一次方程組時(shí),就可以按

2、照某一程序進(jìn)行損傷用配方法解一元二次方程,也是按一定程序操作的.1.1.1 算法的概念 一般地,對(duì)于一類問(wèn)題的機(jī)械式地、統(tǒng)一地、按部就班地求解過(guò)程稱為算法(algorithm)它是解決某一問(wèn)題的程序或步驟. 所謂 “算法”就是解題方法的精確描述.從更廣義的角度來(lái)看,并不是只有“計(jì)算”的問(wèn)題才有算法,日常生活中處處都有.如樂(lè)譜是樂(lè)隊(duì)演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤(pán)的算法. 按照這樣的理解,我們可以設(shè)計(jì)出很多具體數(shù)學(xué)問(wèn)題的算法.下面看幾個(gè)例子:做一做 請(qǐng)你寫(xiě)出解下面二元一次方程組的詳細(xì)過(guò)程. 第二步, 解得第三步, - 2得 5y=3; 第四步, 解得第五步, 得到方程組的解為解

3、：第一步, +2得 5x=1; 思考：你能寫(xiě)出解一般的二元一次方程組的步驟嗎？第一步, 得 第二步,解（3）得 第四步,解（4）得 第五步,得到方程組的解為思考這 兩個(gè)解方程組的算法的適用范圍有何不同？第一步：+2，得第二步：解 得第三步：將 代入,得-第一步： 得第二步：解，得 第三步：將帶入得 事實(shí)上，我們可以將一般的二元一次方程組的解法轉(zhuǎn)化成計(jì)算機(jī)語(yǔ)言，做成一個(gè)求解二元一次方程組的程序.這兒已經(jīng)做好了，試一試吧！練習(xí)1. 給出求1+2+3+4+5+6的一個(gè)算法.解法1.按照逐一相加的程序進(jìn)行.第一步:計(jì)算1+2,得3;第二步:將第一步中的運(yùn)算結(jié)果3與3相加得6;第三步:將第二步中的運(yùn)算結(jié)

4、果6與4相加得10;第四步:將第三步中的運(yùn)算結(jié)果10與5相加得15;第五步:將第四步中的運(yùn)算結(jié)果15與6相加得21.解法2.可以運(yùn)用下面公式直接計(jì)算.第一步,取 n =6;第二步,計(jì)算第三步,輸出計(jì)算結(jié)果.點(diǎn)評(píng):解法1繁瑣,步驟較多; 解法2簡(jiǎn)單，步驟較少. 找出好的算法是我們的追求目標(biāo).現(xiàn)在你對(duì)算法有了新的認(rèn)識(shí)了嗎？講授新課1.算法的定義 在數(shù)學(xué)中，算法通常是指按照一定規(guī)則解決某一類問(wèn)題的明確和有限的步驟.現(xiàn)在，算法通常可以編成計(jì)算機(jī)程序，讓計(jì)算機(jī)執(zhí)行并解決問(wèn)題.2.算法的要求(1)寫(xiě)出的算法,必須能解決一類問(wèn)題(例如解任意一個(gè)二元一次方程組),并且能重復(fù)使用;(2) 算法過(guò)程要能一步一步執(zhí)

5、行,每一步執(zhí)行的操作,必須確切,不能含混不清,而且在有限步之內(nèi)完成后能得出結(jié)果.講授新課3.算法的基本特征:明確性:算法對(duì)每一個(gè)步驟都有確切的、非二義性的規(guī)定,即每一步對(duì)于利用算法解決問(wèn)題的人或計(jì)算機(jī)來(lái)說(shuō)都是可讀的、可執(zhí)行的,而不需要計(jì)算者臨時(shí)動(dòng)腦筋. 有效性:算法的每一個(gè)步驟都能夠通過(guò)基本運(yùn)算有效地進(jìn)行,并得到確定的結(jié)果；對(duì)于相同的輸入,無(wú)論誰(shuí)執(zhí)行算法,都能夠得到相同的最終結(jié) 果有限性:算法應(yīng)由有限步組成,至少對(duì)某些輸入,算法應(yīng)在有限多步內(nèi)結(jié)束,并給出計(jì)算結(jié)果數(shù)據(jù)輸入:算法一定要根據(jù)輸入的初始數(shù)據(jù)或給定的初值才能正確執(zhí)行它的每一步驟.信息輸出:一個(gè)算法至少要有一個(gè)有效的信息輸出,這就是問(wèn)題求

6、解的結(jié)果.不唯一性:求解某一個(gè)題的解法不一定是唯一的, 對(duì)于一個(gè)問(wèn)題可以有不同的算法.4.算法的描述: 描述算法可以有不同的方式,常用的有自然語(yǔ)言、程序框圖、程序設(shè)計(jì)語(yǔ)言、偽代碼等.(1)自然語(yǔ)言 自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言,可以是漢語(yǔ)、英語(yǔ)或數(shù)學(xué)語(yǔ)言等.用自然語(yǔ)言描述算法的優(yōu)點(diǎn)是通俗易懂,當(dāng)算法中的操作步驟都是順序執(zhí)行時(shí)比較容易理解.缺點(diǎn)是如果算法中包含判斷和轉(zhuǎn)向,并且操作步驟較多時(shí),就不那么直觀清晰了.(2)程序框圖1.1.2程序框圖中講解(3)程序設(shè)計(jì)語(yǔ)言1.2基本算法語(yǔ)句中講解例1.(1)設(shè)計(jì)一個(gè)算法判斷7是否為質(zhì)數(shù).第一步, 用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以2不能整除7

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

8、5.因此，35不是質(zhì)數(shù).變式1: “判斷53是否質(zhì)數(shù)”的算法如下：第1步,用2除53得余數(shù)為1,余數(shù)不為0,所以2不能整除53;第2步,用3除53得余數(shù)為2,余數(shù)不為0,所以3不能整除53;第52步,用52除53得余數(shù)為1,余數(shù)不為0,故52不能整除53;所以53是質(zhì)數(shù).上述算法正確嗎？請(qǐng)說(shuō)明理由.設(shè)計(jì)一個(gè)具體問(wèn)題的算法時(shí),與過(guò)去熟悉地解數(shù)學(xué)題的過(guò)程有直接的聯(lián)系,但這個(gè)過(guò)程必須被分解成若干個(gè)明確的步驟,而且這些步驟必須是有效的.算法要“面面俱到”,不能省略任何一個(gè)細(xì)小的步驟,只有這樣,才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成.變式2:任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟

9、對(duì)n是否為質(zhì)數(shù)做出判定.分析:回顧這個(gè)問(wèn)題的解題過(guò)程.算法步驟:第一步:判斷n是否等于2.若n=2,則n是質(zhì)數(shù);若n2,則執(zhí)行第二步. 第二步:依次檢驗(yàn)2(n-1)這些整數(shù)是不是n的約數(shù),即是不是整除n的數(shù).若有這樣的數(shù),則n不是質(zhì)數(shù);若沒(méi)有這樣的數(shù),則n是質(zhì)數(shù).例2.用二分法設(shè)計(jì)一個(gè)求方程的近似根的算法.二分法 對(duì)于區(qū)間a,b 上連續(xù)不斷、且f(a)f(b)0的函數(shù)y=f(x),通過(guò)不斷地把函數(shù)f(x)的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)或其近似值的方法叫做二分法.算法步驟：第一步,令 ,給定精確度d.第二步,給定區(qū)間a,b,滿足f(a) f(b)0第三步,取

10、中間點(diǎn) 第四步,若f(a)f(m) 0,則含零點(diǎn)的區(qū)間為a,m；否則，含零點(diǎn)的區(qū)間為m, b.將新得到的含零點(diǎn)的仍然記為a,b.第五步,判斷f(m)是否等于或者a,b的長(zhǎng)度是否小于d，若是，則m是方程的近似解;否則，返回第三步當(dāng)d=0.005時(shí)，按照以上算法，可得下面表和圖.ab|a-b|12111.50.51.251.50.251.3751.50.1251.3751.437 50.062 51.406 251.437 50.031 251.406 251.421 8750.015 6251.414 6251.421 8750.007 812 51.414 062 51.417 968 750

11、.003 906 25y=x2-2121.51.3751.25 于是，開(kāi)區(qū)間（1.4140625,1.41796875）中的實(shí)數(shù)都是當(dāng)精確度為0.005時(shí)的原方程的近似解.練習(xí)2. 任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.算法步驟:第一步:給定一個(gè)正實(shí)數(shù)r;第二步:計(jì)算以r為半徑的圓的面積S=r2;第三步:得到圓的面積S.練習(xí)3. 任意給定一個(gè)大于 1 的正整數(shù)n，設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).算法步驟： 第一步,依次以2（n1）為除數(shù)除n，檢查余數(shù)是否為0；若是，則是n的因數(shù)；若不是，則不是n的因數(shù)； 第二步,在n的因數(shù)中加入1和n； 第三步, 輸出n的所有因數(shù).練習(xí)4. 寫(xiě)出求一元