_算法與程序框圖_ppt.ppt

1、算法與程序框圖,1.1.1 算法的概念,中國古代數(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é)史簡介,計(jì)算機(jī)的問世可謂是20 世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明。它把人類社會帶進(jìn)了信息技術(shù)時(shí)代。,計(jì)算機(jī)是對人腦的模

2、擬，它強(qiáng)化了人的思維智能；,21世紀(jì)信息社會的兩個主要特征： “計(jì)算機(jī)無處不在” “數(shù)學(xué)無處不在”,21世紀(jì)信息社會對科技人才的要求： -會“用數(shù)學(xué)”解決實(shí)際問題 -會用計(jì)算機(jī)進(jìn)行科學(xué)計(jì)算,而算法是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。就像使用算盤一樣，人們需要給計(jì)算機(jī)編制“口決”算法，才能讓它工作，否則超級計(jì)算機(jī)只是一堆廢鐵而已；,要想了解計(jì)算機(jī)的工作原理，算法的學(xué)習(xí)是一個開始,問題的提出,有一個農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？,方法和過程：,1、帶羊到對岸，返回；,2、帶菜到對岸，并把羊帶回；,3、

3、帶狼狗到對岸，返回；,4、帶羊到對岸。,第一步:-2得: 5y=3 ,第二步: 解得:,第三步: 將 代入,解得 .,對于一般的二元一次方程組 其中 也可以按照上述步驟求解.,思考？,第二步：解，得,第一步： - ，得 ,第三步：將 代入，得,這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來解二元一次方程組.,算法的概念與特征,算法(algorithm)這個詞出現(xiàn)于12世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程.,在數(shù)學(xué)上,現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來解決的某一類問題的程序或步驟,這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.,

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

5、能整除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能整除35。因此，35不是質(zhì)數(shù),2、算法的特點(diǎn),有限性：一個算法應(yīng)在執(zhí)行有限個步驟后必須結(jié)束.,確定性：算法中每一個步驟和次序應(yīng)當(dāng)是確定的.,3、算法的思想 ：程序化思想,你能寫出“判斷整數(shù)n(n2)是否為質(zhì)數(shù)”的算法嗎？,第一步，給定大于2的整數(shù)n。,第二步，令i=2.,第三步，用i除n，得到余數(shù)r。,第五步，判斷i是否大于(n-1)，若是，則n是質(zhì)數(shù)；否則，返回第三步,算法分析：對于任意

6、的整數(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í)行同樣的操作 這個操作一直要進(jìn)行到i的值等于(n-1)為止。因此，”判斷i是否為質(zhì)數(shù)“的算法可以寫成：,第四步，判斷余數(shù)r是否為0，若是則n不是質(zhì)數(shù)，結(jié)束算法； 否則，將i的值增加1，仍用i表示。,算法分析：令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,

7、b。根據(jù)“f(a)f(m)0”是否成立，取出零點(diǎn)所在的區(qū)間a,m或m,b，仍記為a,b，對所得的區(qū)間a,b重復(fù)上述步驟，直到包含零點(diǎn)的區(qū)間a,b“足夠小“，則a,b內(nèi)的數(shù)可以作為方程的近似解。,例2:用二分法設(shè)計(jì)一個求方程x2-2=0（X0) 的近似根的算法.精確度為0.05,解,例2:用二分法設(shè)計(jì)一個求方程x2-2=0（X0)的近似根的算法.精確度為0.05,課堂練習(xí),設(shè)計(jì)一個求一般的一元二次方程 的根的算法,四、回顧反思,1、算法的含義：,2、算法的特點(diǎn) ：有限性、確定性,3、算法的思想 ：程序化思想,練習(xí)一:任意給定一個正實(shí)數(shù),設(shè)計(jì)一個算法求以這個數(shù)為半徑的圓的面積.,算法分析:,第一步:輸入任意一個正實(shí)數(shù)r; 第二步:計(jì)算以r為半徑的圓的面積S=r2; 第三步:輸出圓的面積.,練習(xí)二:任意給定一個大于1的正整數(shù)n,設(shè)計(jì)一個算法求出n的所有因數(shù).,算法分析:,第一步:依次從2(n-1)為除數(shù)去除n,判斷余數(shù)是否為0,若是,則是n