算法與程序框圖-課件

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

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

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

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

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

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

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

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

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

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

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

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

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