必修三算法的概念

1.1.1算法的概念,章頭圖說明,章頭圖的后景是元代朱世杰所著的四元玉鑒，前景的前部是一臺(tái)計(jì)算機(jī)，后部是盛行一時(shí)的計(jì)算工具算籌和算盤。,中國古代數(shù)學(xué)在世界數(shù)學(xué)史上一度居于領(lǐng)先地們，它注重實(shí)際問題的解決，以算法為中心，寓理于算，其中蘊(yùn)涵了豐富的算法思想，算籌是中國古代的計(jì)算工具，在春秋時(shí)期已經(jīng)很普遍；算盤在明代開始盛行，即使在計(jì)算機(jī)普及的今天，許多人仍然在使用算盤。中國古代涌現(xiàn)了許多著名的數(shù)學(xué)家，如三國及兩晉時(shí)期的趙爽、劉徽，南北朝的祖沖之、宋、元時(shí)期的秦九韶、楊輝、朱世杰，等。古時(shí)著名的數(shù)學(xué)專著如九章算術(shù)周髀算經(jīng)數(shù)書九章四元玉鑒等。所有這些成就，都使中國數(shù)學(xué)曾經(jīng)處于世界巔峰。,數(shù)學(xué)史簡(jiǎn)介,計(jì)算機(jī)的問世可謂是20世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明。它把人類社會(huì)帶進(jìn)了信息技術(shù)時(shí)代。,計(jì)算機(jī)是對(duì)人腦的模擬，它強(qiáng)化了人的思維智能；,21世紀(jì)信息社會(huì)的兩個(gè)主要特征：“計(jì)算機(jī)無處不在”“數(shù)學(xué)無處不在”,21世紀(jì)信息社會(huì)對(duì)科技人才的要求：-會(huì)“用數(shù)學(xué)”解決實(shí)際問題-會(huì)用計(jì)算機(jī)進(jìn)行科學(xué)計(jì)算,算法的研究和應(yīng)用正是本課程的主題！,現(xiàn)代科學(xué)研究的三大支柱,研究算法,而算法是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。就像使用算盤一樣，人們需要給計(jì)算機(jī)編制“口決”算法，才能讓它工作，否則超級(jí)計(jì)算機(jī)只是一堆廢鐵而已。,要想了解計(jì)算機(jī)的工作原理，算法的學(xué)習(xí)是一個(gè)開始,問題的提出,有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？,問題的提出,有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？,方法和過程：,1、帶羊到對(duì)岸，返回；,2、帶菜到對(duì)岸，并把羊帶回；,3、帶狼狗到對(duì)岸，返回；,4、帶羊到對(duì)岸。,我們可以歸納它的步驟:,第一步:-2，得5y=3,第三步:,第四步：得到方程組的解為：x=1/5,y=3/5,第二步：解，得,第一步：-，得,第三步：將代入，得,第四步：得到方程組的解.,二、建構(gòu)數(shù)學(xué),1、算法的含義,算法（algorithm)古代指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程。在數(shù)學(xué)中，通常是指按照一定規(guī)則解決某一類問題的明確和有限的步驟。現(xiàn)在，算法通常可以編成計(jì)算機(jī)程序，讓計(jì)算機(jī)執(zhí)行并解決問題。,注意：解決某一類問題，明確而且有效，有限性，程序性，不唯一,【例】寫出你在家中燒開水的過程的一個(gè)算法。,總結(jié)：“第1”其實(shí)大部分事情都是按照一定的程序執(zhí)行，因此要理清事情的每一步?！暗?”判斷水是否燒開與是否繼續(xù)燒火的過程是一個(gè)反饋與判斷過程，因此有必要不斷重復(fù)過程“3”,解:1、往壺內(nèi)注水；2、點(diǎn)火加熱；3觀察：如果水開，則停止燒火，否則繼續(xù)燒火；4、如果水未開，重復(fù)“3”直至水開。,請(qǐng)寫出下面一個(gè)算法：,寫出已知直角三角形兩邊a,b，求斜邊的一個(gè)算法,解：輸入直角三角形兩邊a,b的值；計(jì)算=輸出斜邊長(zhǎng)L的值。,請(qǐng)?jiān)噷懗鲆粋€(gè)算法：,寫出求一個(gè)數(shù)絕對(duì)值的一個(gè)算法,解：請(qǐng)輸入要求絕對(duì)值的數(shù)a.,若a=0,則b=0(b為a的絕對(duì)值)。若a0，則b=a；若a0，則b=-a.,輸出a的絕對(duì)值b。,新課講解,算法的基本特點(diǎn),1、有限性,一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。,2、確定性,一個(gè)算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性。,3、有效性,算法中的每一個(gè)步驟都是可以在有限的時(shí)間內(nèi)有效地完成的基本操作，并能得到確定的結(jié)果。,廣播操圖解是廣播操的算法；菜譜是做菜的算法；歌譜是一首歌曲的算法；空調(diào)說明書是空調(diào)使用的算法等,例1、（1）設(shè)計(jì)一個(gè)算法，判斷7是否為質(zhì)數(shù)。（2）設(shè)計(jì)一個(gè)算法，判斷35是否為質(zhì)數(shù)。,算法（1）,第一步，用2除7，得到余數(shù)1。因?yàn)橛鄶?shù)不為0，所以2不能整除7。,三、數(shù)學(xué)運(yùn)用,第二步，用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、（1）設(shè)計(jì)一個(gè)算法，判斷7是否為質(zhì)數(shù)。（2）設(shè)計(jì)一個(gè)算法，判斷35是否為質(zhì)數(shù)。,算法（2）,第一步，用2除35，得到余數(shù)1。因?yàn)橛鄶?shù)不為0，所以2不能整除35。,三、數(shù)學(xué)運(yùn)用,第二步，用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能整除35。因此，35不是質(zhì)數(shù)。,你能寫出“判斷整數(shù)n(n2)是否為質(zhì)數(shù)”的算法嗎？,第一步，給定大于2的整數(shù)n。,四、數(shù)學(xué)探究,第二步，令i=2.,第三步，用i除n，得到余數(shù)r。第四步：判斷余數(shù)r是否為0，若是則n不是質(zhì)數(shù)，結(jié)束算法；否則，將i的值增加1，仍用i表示。,第五步，判斷i是否大于(n-1)，若是，則n是質(zhì)數(shù)，結(jié)束算法；否則，返回第三步。,算法分析：對(duì)于任意的整數(shù)n(n2),若用i表示2（n-1)中的任意整數(shù)，則“判斷n是否為質(zhì)數(shù)“的算法包含下面的重復(fù)操作：用i除n，得到余數(shù)r，判斷余數(shù)r是否為0，若是，則n不是質(zhì)數(shù)；否則，將i的值增加1，再執(zhí)行同樣的操作這個(gè)操作一直要進(jìn)行到i的值等于(n-1)為止。因此，”判斷i是否為質(zhì)數(shù)“的算法可以寫成：,例2,用二分法設(shè)計(jì)一個(gè)求方程的近似正根的算法，精確度0.05。,算法分析：令f(x)=x2-2=0(x0)，則方程x2-2=0的解就是函數(shù)f(x)的零點(diǎn)。“二分法”的基本思想是：把函數(shù)f(x)的零點(diǎn)所在的區(qū)間a,b(滿足f(a)f(b)0)“一分為二”。得到a,m和m,b。根據(jù)“f(a)f(m)0”是否成立，取出零點(diǎn)所在的區(qū)間a,m或m,b，仍記為a,b，對(duì)所得的區(qū)間a,b重復(fù)上述步驟，直到包含零點(diǎn)的區(qū)間a,b“足夠小“，則a,b內(nèi)的數(shù)可以作為方程的近似解。,例2,用二分