算法與程序框圖

1、1.1.1 算法的概念算法的概念 中國古代數(shù)學(xué)在世界數(shù)學(xué)史上一度居于領(lǐng)中國古代數(shù)學(xué)在世界數(shù)學(xué)史上一度居于領(lǐng)先地們，它注重實(shí)際問題的解決，以算法為中心，先地們，它注重實(shí)際問題的解決，以算法為中心，寓理于算，其中蘊(yùn)涵了豐富的算法思想，算籌是寓理于算，其中蘊(yùn)涵了豐富的算法思想，算籌是中國古代的計(jì)算工具，在春秋時(shí)期已經(jīng)很普遍；中國古代的計(jì)算工具，在春秋時(shí)期已經(jīng)很普遍；算盤在明代開始盛行，即使在計(jì)算機(jī)普及的今天，算盤在明代開始盛行，即使在計(jì)算機(jī)普及的今天，許多人仍然在使用算盤。中國古代涌現(xiàn)了許多著許多人仍然在使用算盤。中國古代涌現(xiàn)了許多著名的數(shù)學(xué)家，如三國及兩晉時(shí)期的趙爽、劉徽，名的數(shù)學(xué)家，如三國及兩晉

2、時(shí)期的趙爽、劉徽，南北朝的祖沖之、宋、元時(shí)期的秦九韶、楊輝、南北朝的祖沖之、宋、元時(shí)期的秦九韶、楊輝、朱世杰，等。古時(shí)著名的數(shù)學(xué)專著如朱世杰，等。古時(shí)著名的數(shù)學(xué)專著如九章算術(shù)九章算術(shù)周髀算經(jīng)周髀算經(jīng)數(shù)書九章數(shù)書九章四元玉鑒四元玉鑒等。所等。所有這些成就，都使中國數(shù)學(xué)曾經(jīng)處于世界巔峰有這些成就，都使中國數(shù)學(xué)曾經(jīng)處于世界巔峰數(shù)學(xué)史簡介 計(jì)算機(jī)的問世可謂是計(jì)算機(jī)的問世可謂是20 世紀(jì)最偉大的科學(xué)世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明。它把人類社會(huì)帶進(jìn)了信息技術(shù)時(shí)代。技術(shù)發(fā)明。它把人類社會(huì)帶進(jìn)了信息技術(shù)時(shí)代。計(jì)算機(jī)是對(duì)人腦的模擬，它強(qiáng)化了人的思維智能；計(jì)算機(jī)是對(duì)人腦的模擬，它強(qiáng)化了人的思維智能；2121世紀(jì)信息社會(huì)

3、的兩個(gè)主要特征：世紀(jì)信息社會(huì)的兩個(gè)主要特征：“計(jì)算機(jī)無處不在計(jì)算機(jī)無處不在”“數(shù)學(xué)無處不在數(shù)學(xué)無處不在”2121世紀(jì)信息社會(huì)對(duì)科技人才的要求：世紀(jì)信息社會(huì)對(duì)科技人才的要求：-會(huì)會(huì)“用數(shù)學(xué)用數(shù)學(xué)”解決實(shí)際問題解決實(shí)際問題-會(huì)用計(jì)算機(jī)進(jìn)行科學(xué)計(jì)算會(huì)用計(jì)算機(jī)進(jìn)行科學(xué)計(jì)算 而算法是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。就像使而算法是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。就像使用算盤一樣，人們需要給計(jì)算機(jī)編制用算盤一樣，人們需要給計(jì)算機(jī)編制“口決口決”算法，才能讓它工作，否則超級(jí)計(jì)算機(jī)只是一堆算法，才能讓它工作，否則超級(jí)計(jì)算機(jī)只是一堆廢鐵而已；廢鐵而已；問題的提出問題的提出 有一個(gè)農(nóng)夫帶一條狼狗、一只羊和有一個(gè)農(nóng)夫帶一條狼狗、一只羊和

4、一筐白菜過河。如果沒有農(nóng)夫看管，則一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？何解此難題？ 方法和過程方法和過程：1、帶羊到對(duì)岸，返回；帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。帶羊到對(duì)岸。問題問題請(qǐng)你寫出解二元一次方程組的詳細(xì)求解過請(qǐng)你寫出解二元一次方程組的詳細(xì)求解過程程. 2121xyxy 第一步第一步:-2得得: 5y=3 第二步第二步: 解解得得:35y 第三

5、步第三步: 將將 代入代入,解得解得 .35y 15x 對(duì)于一般的二元一次方程組對(duì)于一般的二元一次方程組其中其中 也可以按照上述步驟求解也可以按照上述步驟求解.111222a x b yca x b yc1 22 10aba b思考？0 1221222111babacybxacybxa?第二步：解，得第二步：解，得12211221babacacay第一步：第一步： - - ，得，得 1a2a12211221)(cacaybaba第三步：將第三步：將 代入代入，得，得12211221babacacay12212112babacbcbx這些步驟就構(gòu)成了解二元一次方程組的這些步驟就構(gòu)成了解二元一次方

6、程組的算法算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來解二元一次方程組讓計(jì)算機(jī)來解二元一次方程組.算法的概念與特征算法的概念與特征算法算法(algorithm)這個(gè)詞出現(xiàn)于這個(gè)詞出現(xiàn)于12世紀(jì)世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程.在數(shù)學(xué)上在數(shù)學(xué)上,現(xiàn)代意義上的現(xiàn)代意義上的“算法算法”通常是指可通常是指可以用計(jì)算機(jī)來解決的某一類問題的以用計(jì)算機(jī)來解決的某一類問題的程序或步程序或步驟驟,例例1 1、（、（1 1）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)一個(gè)算法，判斷7 7是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。 （2 2）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)

7、一個(gè)算法，判斷3535是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。算法（算法（1 1） 第一步，用第一步，用2 2除除7 7，得到余數(shù)，得到余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所，所以以2 2不能整除不能整除7 7。 第二步，用第二步，用3 3除除7 7，得到余數(shù)，得到余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所，所以以3 3不能整除不能整除7 7。 第三步，用第三步，用4 4除除7 7，得到余數(shù)，得到余數(shù)3 3。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以，所以4 4不能整除不能整除7 7。 第四步，用第四步，用5 5除除7 7，得到余數(shù)，得到余數(shù)2 2。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以5 5

8、不能整除不能整除7 7。 第五步，用第五步，用6 6除除7 7，得到余數(shù)，得到余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所，所以以6 6不能整除不能整除7 7。因此，。因此，7 7是質(zhì)數(shù)是質(zhì)數(shù)例例1 1、（、（1 1）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)一個(gè)算法，判斷7 7是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。 （2 2）設(shè)計(jì)一個(gè)算法，判斷）設(shè)計(jì)一個(gè)算法，判斷3535是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。算法（算法（2 2） 第一步，用第一步，用2 2除除3535，得到余數(shù)，得到余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以2 2不能整除不能整除3535。 第二步，用第二步，用3 3除除3535，得到余數(shù)，得到余數(shù)2 2

9、。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以3 3不能整除不能整除3535。 第三步，用第三步，用4 4除除3535，得到余數(shù)，得到余數(shù)3 3。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以4 4不能整除不能整除3535。 第四步，用第四步，用5 5除除3535，得到余數(shù)，得到余數(shù)0 0。因?yàn)橛鄶?shù)為。因?yàn)橛鄶?shù)為0 0，所，所以以5 5能整除能整除3535。因此，。因此，3535不是質(zhì)數(shù)不是質(zhì)數(shù)2、算法的特點(diǎn)、算法的特點(diǎn) 有限性：一個(gè)算法應(yīng)在執(zhí)行有限個(gè)步驟后必須結(jié)束有限性：一個(gè)算法應(yīng)在執(zhí)行有限個(gè)步驟后必須結(jié)束.確定性：算法中每一個(gè)步驟和次序應(yīng)當(dāng)是確定的確定性：算法中每一個(gè)步驟和次序應(yīng)當(dāng)是確定的.3、

10、算法的思想、算法的思想 ：程序化思想：程序化思想你能寫出你能寫出“判斷整數(shù)判斷整數(shù)n(nn(n2)2)是否為質(zhì)數(shù)是否為質(zhì)數(shù)”的算法嗎？的算法嗎？ 第一步，給定大于第一步，給定大于2 2的整數(shù)的整數(shù)n n。 第二步，令第二步，令i=2.i=2. 第三步，用第三步，用i i除除n n，得到余數(shù)，得到余數(shù)r r。 第五步，判斷第五步，判斷i i是否大于是否大于(n-1)(n-1)，若是，則，若是，則n n是質(zhì)數(shù)；否是質(zhì)數(shù)；否則，返回第三步則，返回第三步 算法分析：對(duì)于任意的整數(shù)n(n2),若用i表示2至（n-1)中的任意整數(shù)，則“判斷n是否為質(zhì)數(shù)“的算法包含下面的重復(fù)操作：用i除n，得到余數(shù)r，判斷

11、余數(shù)r是否為0，若是，則n不是質(zhì)數(shù)；否則，將i的值增加1，再執(zhí)行同樣的操作這個(gè)操作一直要進(jìn)行到i的值等于(n-1)為止。因此，”判斷i是否為質(zhì)數(shù)“的算法可以寫成：第四步，判斷余數(shù)第四步，判斷余數(shù)r r是否為是否為0 0，若是則，若是則n n不是質(zhì)數(shù)，結(jié)束算法；不是質(zhì)數(shù)，結(jié)束算法；否則，將否則，將i i的值增加的值增加1 1，仍用，仍用i i表示。表示。算法分析：算法分析：令令f(x)=x2-2=0(x0)，則方程，則方程x2-2=0的解就是的解就是函數(shù)函數(shù)f(x)的零點(diǎn)。的零點(diǎn)。 “二分法二分法”的基本思想是：把函數(shù)的基本思想是：把函數(shù)f(x)的零點(diǎn)所在的區(qū)間的零點(diǎn)所在的區(qū)間a,b(滿足滿足f

12、(a)f(b)0)“一分為二一分為二”。得到。得到a,m和和m,b。根據(jù)根據(jù)“f(a)f(m)0”是否成立，取出零點(diǎn)所在的區(qū)間是否成立，取出零點(diǎn)所在的區(qū)間a,m或或m,b，仍記為，仍記為a,b，對(duì)所得的區(qū)間，對(duì)所得的區(qū)間a,b重復(fù)上述步驟，直重復(fù)上述步驟，直到包含零點(diǎn)的區(qū)間到包含零點(diǎn)的區(qū)間a,b“足夠小足夠小“，則，則a,b內(nèi)的數(shù)可以作為方內(nèi)的數(shù)可以作為方程的近似解。程的近似解。例例2:用二分法設(shè)計(jì)一個(gè)求方程用二分法設(shè)計(jì)一個(gè)求方程x2-2=0（x0)的近似根的算法的近似根的算法.精確度為精確度為0.05 22.x第一步：令f x給定精確度d=0.052ab第三步：令m( )( )0,f af

13、m第四步：若則含零點(diǎn)的區(qū)間為a,m;否則含零點(diǎn)的區(qū)間為m,b.將新得到的含零點(diǎn)的區(qū)間仍記為a,b.第五步：判斷a,b的長度是否小于d或f(m)是否行于0.若是,則m是方程的近似解;否則,返回第三步解解( )( )0f af b第二步：確定區(qū)間a,b,滿足例例2:用二分法設(shè)計(jì)一個(gè)求方程用二分法設(shè)計(jì)一個(gè)求方程x2-2=0（x0)的的近似根的算法近似根的算法.精確度為精確度為0.05課堂練習(xí)設(shè)計(jì)一個(gè)求一般的一元二次方程 的根的算法02cbxax1 1、算法的含義、算法的含義：2、算法的特點(diǎn)、算法的特點(diǎn) ：有限性、確定性：有限性、確定性3、算法的思想、算法的思想 ：程序化思想：程序化思想練習(xí)一練習(xí)一:任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積算法求以這個(gè)數(shù)為半徑的圓的面積.算法分析算法分析:第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r;第二步第二步:計(jì)算以計(jì)算以r為半徑的圓的面積為半徑的圓的面積s=r2;第三步第三步:輸出圓的面積輸出圓的面積.練習(xí)二練習(xí)二:任意給定一個(gè)大于任意給定一個(gè)大于1的正整數(shù)的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出設(shè)計(jì)一個(gè)算法求出n的所有因數(shù)的所有因數(shù).算法分析算法分析:第一步第一步:依次從依次從2(n-1)為除數(shù)去除為