算法與程序框圖-課件

算法與程序框圖1算法與程序框圖11.1.1算法的概念21.1.1算法的概念2問(wèn)題的提出有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過(guò)河。如果沒(méi)有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過(guò)河。問(wèn)農(nóng)夫該如何解此難題？方法和過(guò)程：1、帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。3問(wèn)題的提出有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜[問(wèn)題]請(qǐng)你寫(xiě)出解二元一次方程組的詳細(xì)求解過(guò)程.①②第一步:②-①×2得:5y=3③第二步:解③得:第三步:將代入①,解得. 對(duì)于一般的二元一次方程組其中也可以按照上述步驟求解.4[問(wèn)題]請(qǐng)你寫(xiě)出解二元一次方程組的詳細(xì)求解過(guò)程.①第一步: 這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來(lái)解二元一次方程組.算法的概念與特征 算法(algorithm)這個(gè)詞出現(xiàn)于12世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程.在數(shù)學(xué)上,現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟,這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.5 這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算算法的概念:算法是指解決給定問(wèn)題的有窮操作步驟的描述，簡(jiǎn)單的說(shuō)，算法就是解決問(wèn)題的步驟和方法。6算法的概念:算法是指解決給定問(wèn)題的有窮操作步驟的說(shuō)明:(1)事實(shí)上算法并沒(méi)有精確化的定義.(2)算法雖然沒(méi)有一個(gè)明確的定義,但其特點(diǎn)是鮮明的,不僅要注意算法的程序性、有限性、構(gòu)造性、精確性的特點(diǎn)，還應(yīng)該充分理解算法問(wèn)題的指向性，即算法往往指向解決某一類問(wèn)題，泛泛地談算法是沒(méi)有意義的。7說(shuō)明:7算法學(xué)的發(fā)展隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到了前所未有的發(fā)展,現(xiàn)在已經(jīng)發(fā)展到了各個(gè)領(lǐng)域.有遺傳算法,排序算法,加密算法,蟻群算法等,與生物學(xué),計(jì)算機(jī)科學(xué)等有著很廣泛的聯(lián)系,尤其是在現(xiàn)在的航空航天中,更是有著更廣泛的應(yīng)用.很多復(fù)雜的運(yùn)算都是借助計(jì)算機(jī)和算法來(lái)完成的,在高端科學(xué)技術(shù)中有著很重要的地位.8算法學(xué)的發(fā)展隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到王小云：1966年生，1983年至1993年就讀于山東大學(xué)數(shù)學(xué)系，先后獲得學(xué)士、碩士和博士學(xué)位，1993年畢業(yè)后留校任教。2005年６月受聘為清華大學(xué)高等研究中心＂楊振寧講座教授＂，現(xiàn)為清華大學(xué)＂長(zhǎng)江學(xué)者特聘教授＂9王小云：9王小云破譯了美國(guó)政府使用的密碼

ＭＤ５密碼算法，運(yùn)算量達(dá)到２的８０次方。即使采用現(xiàn)在最快的巨型計(jì)算機(jī)，也要運(yùn)算１００萬(wàn)年以上才能破解。但王小云和她的研究小組用普通的個(gè)人電腦，幾分鐘內(nèi)就可以找到有效結(jié)果。

ＳＨＡ－１密碼算法，由美國(guó)專門(mén)制定密碼算法的標(biāo)準(zhǔn)機(jī)構(gòu)－－－美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院與美國(guó)國(guó)家安全局設(shè)計(jì)，早在１９９４年就被推薦給美國(guó)政府和金融系統(tǒng)采用，是美國(guó)政府目前應(yīng)用最廣泛的密碼算法。

2005年初，王小云和她的研究小組宣布，成功破解郵箱密碼。《崩潰！密碼學(xué)的危機(jī)》，美國(guó)《新科學(xué)家》雜志用這樣富有驚聳的標(biāo)題概括王小云里程碑式的成就。因?yàn)橥跣≡频某霈F(xiàn)，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院宣布，美國(guó)政府５年內(nèi)將不再使用ＳＨＡ－１，取而代之的是更為先進(jìn)的新算法，微軟、Ｓｕｎ和Ａｔｍｅｌ等知名公司也紛紛發(fā)表各自的應(yīng)對(duì)之策。

10王小云破譯了美國(guó)政府使用的密碼

ＭＤ５密碼算法，運(yùn)算量達(dá)到例1設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積算法分析：第一步：輸入圓的半徑第二步：利用公式“圓的面積=圓周率×（半徑的平方）”計(jì)算圓的面積；第三步：輸出圓的面積。說(shuō)明:用語(yǔ)言描述一個(gè)算法,最便捷的方式就是按解決問(wèn)題的步驟進(jìn)行描述.每一步做一件事情.11例1設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積算法例2設(shè)計(jì)房租收費(fèi)的算法,其要求是:住房面積80平方米以內(nèi),每平方米收費(fèi)3元,住房面積超過(guò)80平方米時(shí),超過(guò)部分,每平方米收費(fèi)5元.輸入住房面積數(shù),輸出應(yīng)付的房租.算法分析：第一步：輸入住房面積S第二步：根據(jù)面積選擇計(jì)費(fèi)方式：如果S小于或等于80，則租金為M=S×3，否則為M=240+(S-80)×5第三步：輸出房租M的值。12例2設(shè)計(jì)房租收費(fèi)的算法,其要求是:住房面積80若是,則m為所求;例3:用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近似根的算法.精確度為0.005算法分析:第一步:令f(x)=x2-2.因?yàn)閒(1)<0,f(2)>0,所以設(shè)a=1,b=2.第二步:令判斷f(m)是否為0.若否,則繼續(xù)判斷f(a)f(m)大于0還是小于0.第三步:若f(a)(m)>0,則令a=m;否則,令b=m.第四步:判斷|a-b|<0.005,是否成立?若是,則a或b為滿足條件的近似根;若否,則返回第二步.13

算法的基本特點(diǎn)1、有窮性一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。2、確定性算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性。3、可行性算法中的每一個(gè)步驟都是可以在有限的時(shí)間內(nèi)完成的基本操作，并能得到確定的結(jié)果。14算法的基本特點(diǎn)1、有窮性一個(gè)算法應(yīng)包括有限的操作步注:與一般的解決問(wèn)題的過(guò)程比較,算法有以下特征:①設(shè)計(jì)一個(gè)具體問(wèn)題的算法時(shí),與過(guò)去熟悉地解數(shù)學(xué)題的過(guò)程有直接的聯(lián)系,但這個(gè)過(guò)程必須被分解成若干個(gè)明確的步驟,而且這些步驟必須是有效的.②算法要“面面俱到”,不能省略任何一個(gè)細(xì)小的步驟,只有這樣,才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成.15注:與一般的解決問(wèn)題的過(guò)程比較,算法有以下特征:15 計(jì)算機(jī)解決任何問(wèn)題都要依賴于算法.只有將解決問(wèn)題的過(guò)程分解為若干個(gè)明確的步驟,即算法,并用計(jì)算機(jī)能夠接受的“語(yǔ)言”準(zhǔn)確地描述出來(lái),計(jì)算機(jī)才能夠解決問(wèn)題.16 計(jì)算機(jī)解決任何問(wèn)題都要依賴于算法.只有將解決問(wèn)題的過(guò)程分解練習(xí)一:任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.算法分析:第一步:輸入任意一個(gè)正實(shí)數(shù)r;第二步:計(jì)算以r為半徑的圓的面積S=πr2;第三步:輸出圓的面積.17練習(xí)一:任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓練習(xí)二:任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).算法分析:第一步:依次從2~(n-1)為除數(shù)去除n,判斷余數(shù)是否為0,若是,則是n的因數(shù);若不是,則不是n的因數(shù).第二步:在n的因數(shù)中加入1和n;第三步:輸出n的所有因數(shù).18練習(xí)二:任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所練習(xí)三:為了加強(qiáng)居民的節(jié)水意識(shí),某市制訂了以下生活用水收費(fèi)標(biāo)準(zhǔn):每戶每月用水未超過(guò)7m3時(shí),每立方米收費(fèi)1.0元,并加收0.2元的城市污水處理費(fèi);超過(guò)7m3的部分,每立方米收費(fèi)1.5元,并加收0.4元的城市污水處理費(fèi),請(qǐng)你寫(xiě)出某戶居民每月應(yīng)交納的水費(fèi)y(元)與用水量x(m3)之間的函數(shù)關(guān)系,然后設(shè)計(jì)一個(gè)求該函數(shù)值的算法.解:y與x之間的函數(shù)關(guān)系為:(當(dāng)0≤x≤7時(shí))(當(dāng)x>7時(shí))19練習(xí)三:為了加強(qiáng)居民的節(jié)水意識(shí),某市制訂了以下生活用水收費(fèi)標(biāo)解:y與x之間的函數(shù)關(guān)系為:(當(dāng)0≤x≤7時(shí))(當(dāng)x>7時(shí))求該函數(shù)值的算法分析:第一步:輸入每月用水量x;第二步:判斷x是否不超過(guò)7.若是,則y=1.2x;若否,則y=1.9x-4.9.第三步:輸出應(yīng)交納的水費(fèi)y.20解:y與x之間的函數(shù)關(guān)系為:(當(dāng)0≤x≤7時(shí))求該函數(shù)值的算作業(yè):課本P6頁(yè)T2(只需用自然語(yǔ)言寫(xiě)出算法步驟)21作業(yè):21再見(jiàn)22再見(jiàn)22算法與程序框圖23算法與程序框圖11.1.1算法的概念241.1.1算法的概念2問(wèn)題的提出有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過(guò)河。如果沒(méi)有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過(guò)河。問(wèn)農(nóng)夫該如何解此難題？方法和過(guò)程：1、帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。25問(wèn)題的提出有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜[問(wèn)題]請(qǐng)你寫(xiě)出解二元一次方程組的詳細(xì)求解過(guò)程.①②第一步:②-①×2得:5y=3③第二步:解③得:第三步:將代入①,解得. 對(duì)于一般的二元一次方程組其中也可以按照上述步驟求解.26[問(wèn)題]請(qǐng)你寫(xiě)出解二元一次方程組的詳細(xì)求解過(guò)程.①第一步: 這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來(lái)解二元一次方程組.算法的概念與特征 算法(algorithm)這個(gè)詞出現(xiàn)于12世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程.在數(shù)學(xué)上,現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟,這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.27 這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算算法的概念:算法是指解決給定問(wèn)題的有窮操作步驟的描述，簡(jiǎn)單的說(shuō)，算法就是解決問(wèn)題的步驟和方法。28算法的概念:算法是指解決給定問(wèn)題的有窮操作步驟的說(shuō)明:(1)事實(shí)上算法并沒(méi)有精確化的定義.(2)算法雖然沒(méi)有一個(gè)明確的定義,但其特點(diǎn)是鮮明的,不僅要注意算法的程序性、有限性、構(gòu)造性、精確性的特點(diǎn)，還應(yīng)該充分理解算法問(wèn)題的指向性，即算法往往指向解決某一類問(wèn)題，泛泛地談算法是沒(méi)有意義的。29說(shuō)明:7算法學(xué)的發(fā)展隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到了前所未有的發(fā)展,現(xiàn)在已經(jīng)發(fā)展到了各個(gè)領(lǐng)域.有遺傳算法,排序算法,加密算法,蟻群算法等,與生物學(xué),計(jì)算機(jī)科學(xué)等有著很廣泛的聯(lián)系,尤其是在現(xiàn)在的航空航天中,更是有著更廣泛的應(yīng)用.很多復(fù)雜的運(yùn)算都是借助計(jì)算機(jī)和算法來(lái)完成的,在高端科學(xué)技術(shù)中有著很重要的地位.30算法學(xué)的發(fā)展隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到王小云：1966年生，1983年至1993年就讀于山東大學(xué)數(shù)學(xué)系，先后獲得學(xué)士、碩士和博士學(xué)位，1993年畢業(yè)后留校任教。2005年６月受聘為清華大學(xué)高等研究中心＂楊振寧講座教授＂，現(xiàn)為清華大學(xué)＂長(zhǎng)江學(xué)者特聘教授＂31王小云：9王小云破譯了美國(guó)政府使用的密碼

ＭＤ５密碼算法，運(yùn)算量達(dá)到２的８０次方。即使采用現(xiàn)在最快的巨型計(jì)算機(jī)，也要運(yùn)算１００萬(wàn)年以上才能破解。但王小云和她的研究小組用普通的個(gè)人電腦，幾分鐘內(nèi)就可以找到有效結(jié)果。

ＳＨＡ－１密碼算法，由美國(guó)專門(mén)制定密碼算法的標(biāo)準(zhǔn)機(jī)構(gòu)－－－美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院與美國(guó)國(guó)家安全局設(shè)計(jì)，早在１９９４年就被推薦給美國(guó)政府和金融系統(tǒng)采用，是美國(guó)政府目前應(yīng)用最廣泛的密碼算法。

2005年初，王小云和她的研究小組宣布，成功破解郵箱密碼?！侗罎?！密碼學(xué)的危機(jī)》，美國(guó)《新科學(xué)家》雜志用這樣富有驚聳的標(biāo)題概括王小云里程碑式的成就。因?yàn)橥跣≡频某霈F(xiàn)，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院宣布，美國(guó)政府５年內(nèi)將不再使用ＳＨＡ－１，取而代之的是更為先進(jìn)的新算法，微軟、Ｓｕｎ和Ａｔｍｅｌ等知名公司也紛紛發(fā)表各自的應(yīng)對(duì)之策。

32王小云破譯了美國(guó)政府使用的密碼

ＭＤ５密碼算法，運(yùn)算量達(dá)到例1設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積算法分析：第一步：輸入圓的半徑第二步：利用公式“圓的面積=圓周率×（半徑的平方）”計(jì)算圓的面積；第三步：輸出圓的面積。說(shuō)明:用語(yǔ)言描述一個(gè)算法,最便捷的方式就是按解決問(wèn)題的步驟進(jìn)行描述.每一步做一件事情.33例1設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積算法例2設(shè)計(jì)房租收費(fèi)的算法,其要求是:住房面積80平方米以內(nèi),每平方米收費(fèi)3元,住房面積超過(guò)80平方米時(shí),超過(guò)部分,每平方米收費(fèi)5元.輸入住房面積數(shù),輸出應(yīng)付的房租.算法分析：第一步：輸入住房面積S第二步：根據(jù)面積選擇計(jì)費(fèi)方式：如果S小于或等于80，則租金為M=S×3，否則為M=240+(S-80)×5第三步：輸出房租M的值。34例2設(shè)計(jì)房租收費(fèi)的算法,其要求是:住房面積80若是,則m為所求;例3:用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近似根的算法.精確度為0.005算法分析:第一步:令f(x)=x2-2.因?yàn)閒(1)<0,f(2)>0,所以設(shè)a=1,b=2.第二步:令判斷f(m)是否為0.若否,則繼續(xù)判斷f(a)f(m)大于0還是小于0.第三步:若f(a)(m)>0,則令a=m;否則,令b=m.第四步:判斷|a-b|<0.005,是否成立?若是,則a或b為滿足條件的近似根;若否,則返回第二步.35

算法的基本特點(diǎn)1、有窮性一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。2、確定性算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性。3、可行性算法中的每一個(gè)步驟都是可以在有限的時(shí)間內(nèi)完成的基本操作，并能得到確定的結(jié)果。36算法的基本特點(diǎn)1、有窮性一個(gè)算法應(yīng)包括有限的操作步注:與一般的解決問(wèn)題的過(guò)程比較,算法有以下特征:①設(shè)計(jì)一個(gè)具體問(wèn)題的算法時(shí),與過(guò)去熟悉地解數(shù)學(xué)題的過(guò)程有直接的聯(lián)系,但這個(gè)過(guò)程必須被分解成若干個(gè)明確的步驟,而且這些步驟必須是有效的.②算法要“面面俱到”,不能省略任何一個(gè)細(xì)小的步驟,只有這樣,才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成.37注:與一般的解決問(wèn)題的過(guò)程比較,算法有以下特征:15 計(jì)算機(jī)解決任何問(wèn)題都要依賴于算法.只有將解決問(wèn)題的過(guò)程分解為若干個(gè)明確的步驟,即算法,并用計(jì)算機(jī)能夠接受的“語(yǔ)言”準(zhǔn)確地描述出來(lái),計(jì)算機(jī)才能夠解決問(wèn)題.38 計(jì)算機(jī)解決任何問(wèn)題都要依賴于算法.只有將解決問(wèn)題的過(guò)程分解練習(xí)一:任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以