fortran語言編程第一章

1、第第1 1章章 引論引論FORTRANFORTRAN語言語言 前一頁 休息2計算機算法計算機算法l 解 決 某 類 具 體 問 題 的 方 法 和 步 驟解 決 某 類 具 體 問 題 的 方 法 和 步 驟例如例如 看電影，通常需要如下的步驟來實現(xiàn)：看電影，通常需要如下的步驟來實現(xiàn)：買電影買電影票票 持票按時到指定電影院進場持票按時到指定電影院進場按指定座位坐下按指定座位坐下看電影看電影退場退場 前一頁 休息3計算機算法計算機算法l利用計算機解決某類問題的方法和步利用計算機解決某類問題的方法和步驟驟 前一頁 休息4算法按處理對象分類算法按處理對象分類l 數(shù)值算法數(shù)值算法數(shù)值計算數(shù)值計算l 非

2、數(shù)值算法非數(shù)值算法應(yīng)用范圍十分廣泛，最常見的是事務(wù)應(yīng)用范圍十分廣泛，最常見的是事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理、管理領(lǐng)域，例如圖書檢索、人事管理、行車調(diào)度管理等行車調(diào)度管理等 前一頁 休息5算法的表示算法的表示表示一個算法，可以用不同的方法，常用的有：表示一個算法，可以用不同的方法，常用的有： 自然語言自然語言 傳統(tǒng)流程圖傳統(tǒng)流程圖 結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖 - 三種基本結(jié)構(gòu)的流程圖三種基本結(jié)構(gòu)的流程圖 - N-S流程圖流程圖 偽代碼偽代碼 IPO圖圖 前一頁 休息6例例1用自然語言描述求解用自然語言描述求解“5!=？”的算法的算法 步驟步驟5：輸出結(jié)果：輸出結(jié)果120步驟步驟1：先求：先

3、求12，得到結(jié)果，得到結(jié)果2 步驟步驟4：步驟：步驟3的結(jié)果的結(jié)果24乘以乘以5，得最終，得最終 結(jié)果結(jié)果120 步驟步驟2：步驟：步驟1的結(jié)果的結(jié)果2乘以乘以3，得到結(jié)果，得到結(jié)果6 步驟步驟3：步驟：步驟2的結(jié)果的結(jié)果6乘以乘以4，得到結(jié)果，得到結(jié)果24 前一頁 休息7例例2用自然語言描述求解用自然語言描述求解“n!=？”的算法的算法 S7：輸出：輸出T S6：若：若In 成立，返回重新執(zhí)行成立，返回重新執(zhí)行S4， 以及其后的步驟以及其后的步驟S5、S6 S5：將：將I+1IS4：將：將TI T S3：將：將1I S2: 將將 1TS1：輸入：輸入n值值設(shè)一個變量（設(shè)一個變量（T）代表）代

4、表被乘數(shù)，另外一個被乘數(shù)，另外一個變量（變量（I）代表乘）代表乘數(shù)，直接將每一步數(shù)，直接將每一步的乘積放在被乘數(shù)的乘積放在被乘數(shù)T變量中變量中 前一頁 休息8傳統(tǒng)流程圖表示傳統(tǒng)流程圖表示 美國國家標(biāo)準(zhǔn)化協(xié)會美國國家標(biāo)準(zhǔn)化協(xié)會ANSI 規(guī)定的常用流程圖符號規(guī)定的常用流程圖符號 前一頁 休息9例例3用傳統(tǒng)流程圖描述求解用傳統(tǒng)流程圖描述求解“n!=？”的算的算法法 開始開始 1 T 2 I TI T I+1 I I n 輸出輸出T 結(jié)束結(jié)束 是是否否 前一頁 休息10例例4 用傳統(tǒng)流程圖表示用傳統(tǒng)流程圖表示 “判定一個大于或判定一個大于或 等于等于3的正整數(shù)是的正整數(shù)是 否是素數(shù)？否是素數(shù)？”的算法

5、的算法 前一頁 休息11例例4用傳統(tǒng)流程圖表示用傳統(tǒng)流程圖表示“判定一個大于判定一個大于或等于或等于3的正整數(shù)是否是素數(shù)？的正整數(shù)是否是素數(shù)？”的算的算法法思路分析：思路分析：所謂素數(shù)（質(zhì)數(shù)），是指除了所謂素數(shù)（質(zhì)數(shù)），是指除了1和該數(shù)本和該數(shù)本身外不能被其他任何整數(shù)整除的數(shù)。身外不能被其他任何整數(shù)整除的數(shù)。因此，判斷一個數(shù)因此，判斷一個數(shù)n（n3）是否是素數(shù)）是否是素數(shù)的方法為，將的方法為，將n作為被除數(shù)，并用作為被除數(shù)，并用2到到（n-1）之間的各個整數(shù)輪流作為除數(shù)，）之間的各個整數(shù)輪流作為除數(shù)，若都不能被整除，則若都不能被整除，則n為素數(shù)。為素數(shù)。 前一頁 休息12 前一頁 休息13 前

6、一頁 休息14結(jié)構(gòu)化流程圖表示結(jié)構(gòu)化流程圖表示l三種基本結(jié)構(gòu)的流程圖三種基本結(jié)構(gòu)的流程圖lN-S流程圖流程圖 前一頁 休息15 (1)順序結(jié)構(gòu)順序結(jié)構(gòu) a A B b 前一頁 休息16(2) (2) 選擇結(jié)構(gòu)選擇結(jié)構(gòu)( (又稱選取結(jié)構(gòu)又稱選取結(jié)構(gòu)) ) 前一頁 休息17(3) (3) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)( (又稱重復(fù)結(jié)構(gòu)又稱重復(fù)結(jié)構(gòu)) ) 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu) 直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)和直到型循環(huán)結(jié)構(gòu)條件互逆當(dāng)型循環(huán)和直到型循環(huán)結(jié)構(gòu)條件互逆 前一頁 休息18三種基本結(jié)構(gòu)的共同點三種基本結(jié)構(gòu)的共同點l 只有一個入口，圖中的只有一個入口，圖中的a點點l 一個出口，圖中的一個出口，圖中

7、的b點點l 結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行l(wèi) 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)” 由這三種基本結(jié)構(gòu)所構(gòu)成的算法由這三種基本結(jié)構(gòu)所構(gòu)成的算法稱為稱為結(jié)構(gòu)化算法結(jié)構(gòu)化算法，并可組合應(yīng)用來，并可組合應(yīng)用來解決任何復(fù)雜問題。解決任何復(fù)雜問題。 前一頁 休息19 1971年由兩位美國學(xué)年由兩位美國學(xué)者提出了一種新的流程圖形者提出了一種新的流程圖形式，這種流程圖完全去掉了式，這種流程圖完全去掉了帶箭頭的流程線，稱為帶箭頭的流程線，稱為N-S流程圖流程圖。 N-S流程圖流程圖 前一頁 休息20 順序結(jié)構(gòu)順序結(jié)構(gòu) A B 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 前一頁 休息21 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)

8、 前一頁 休息22例例5 用用N-S流程圖表示求流程圖表示求5!的算法的算法 前一頁 休息23例例6 用用N-S流程圖表示流程圖表示表示表示“判定一個大于或等判定一個大于或等于于3的正整數(shù)是否是素數(shù)？的正整數(shù)是否是素數(shù)？”的算法的算法 前一頁 休息24例例7 用用N-S流程圖表示流程圖表示 “判定判定20002500年年 中的每一年是否閏年，中的每一年是否閏年， 將結(jié)果輸出。將結(jié)果輸出?！钡乃惴ǖ乃惴?前一頁 休息25例例7用用N-S流程圖表示流程圖表示“判定判定20002500年中的每年中的每一年是否閏年，將結(jié)果輸出。一年是否閏年，將結(jié)果輸出?！钡乃惴ǖ乃惴ㄋ悸贩治觯核悸贩治觯?能被能被4整

9、除但不能被整除但不能被100整除的年整除的年份，或者能被份，或者能被100整除同時又能整除同時又能被被400整除的年份，是閏年。整除的年份，是閏年。 前一頁 休息26 前一頁 休息27 例例88用偽代碼表示求用偽代碼表示求5!5!的算法的算法BEGIN t1 i2 do until i5 tt*i ii+1 enddo write tEND 前一頁 休息28課堂練習(xí)課堂練習(xí)1 1如果將求解階乘的問題改一下改為：如果將求解階乘的問題改一下改為：計算計算1357911 請用自然語言描述其算法？請用自然語言描述其算法？ 前一頁 休息29參考答案參考答案S1：將：將1 TS2：將：將3 IS3：將：將

10、TI TS4：將：將I+2 IS5：若：若I 11成立，返回重新執(zhí)行成立，返回重新執(zhí)行S3及及S4S6：輸出：輸出T 前一頁 休息30用自然語言描述求解用自然語言描述求解“百錢百雞百錢百雞”的算的算法法 一只公雞值五文錢一只公雞值五文錢 一只母雞值三文錢一只母雞值三文錢 三只小雞值一文錢三只小雞值一文錢請問用一百文錢買一百只雞，公雞、母雞請問用一百文錢買一百只雞，公雞、母雞 和小雞各有幾只？和小雞各有幾只？課堂練習(xí)課堂練習(xí)2 2 前一頁 休息31分析：分析：假設(shè)公雞、母雞和小雞的個數(shù)分別為假設(shè)公雞、母雞和小雞的個數(shù)分別為x,y和和z 數(shù)學(xué)模型數(shù)學(xué)模型 5X+3Y+Z/3=100 X+Y+Z=1

11、00 z=(100-5*x-3*y)*3 z是是3的倍數(shù)的倍數(shù) z=100-x-y 前一頁 休息32參考答案參考答案S1： X 0 S2： Y 0 S3：100-X-Y ZS4: 如果如果Z能被能被3整除，同時整除，同時5*X+3*Y+Z/3等于等于100， 則則X,Y,Z的值為一個合理的解，輸出的值為一個合理的解，輸出X,Y,ZS5：Y+1 YS6：如果：如果Y 33，返回執(zhí)行，返回執(zhí)行S3、S4和和S5S7：X+1 XS8：如果：如果X 20，返回執(zhí)行，返回執(zhí)行S2、S3、S4和和S5S9：算法結(jié)束：算法結(jié)束 前一頁 休息33課堂練習(xí)課堂練習(xí)3 3給出給出 輸入輸入n個數(shù)據(jù)，找出最大的數(shù)個

12、數(shù)據(jù)，找出最大的數(shù) 算法算法N-S流程圖流程圖 前一頁 休息34參考答案參考答案 前一頁 休息35算法設(shè)計策略算法設(shè)計策略【例】 設(shè)有算式：A B C DC D C=A B C，其中的A，B，C，D均為一位非負(fù)整數(shù)，要求找出A，B，C，D各值。 前一頁 休息36算法設(shè)計策略算法設(shè)計策略-枚舉法枚舉法 思路分析思路分析：l在有限的范圍中，列舉和檢驗所有可能的結(jié)果，從中在有限的范圍中，列舉和檢驗所有可能的結(jié)果，從中找出那些符合要求的候選解作為問題的解。找出那些符合要求的候選解作為問題的解。例如：設(shè)正整數(shù)例如：設(shè)正整數(shù)A A、B B、C C、D D，A A和和C C的取值范圍應(yīng)是的取值范圍應(yīng)是1,1

13、, 99，B B和和D D的取值范圍應(yīng)是的取值范圍應(yīng)是0,0, 99，分別對相應(yīng)范圍中，分別對相應(yīng)范圍中的每一個數(shù)值進行檢測，輸出滿足條件（的每一個數(shù)值進行檢測，輸出滿足條件（10001000A A100100B B1010C CD D）（）（100100C C1010D DC C）= =（100100A A1010B BC C）的數(shù)值。）的數(shù)值。 前一頁 休息37算法描述算法描述：for a1 step 1 until 9 do for b0 step 1 until 9 do for c1 step 1 until 9 do for d0 step 1 until 9 do x1000a1

14、00b10cd y100c10dc z100a10bc if x-y=z then 輸出輸出a，b，c，d 前一頁 休息38對付復(fù)雜性的基本方法對付復(fù)雜性的基本方法按功能劃分按功能劃分若干基本模塊若干基本模塊樹狀的程序結(jié)構(gòu)樹狀的程序結(jié)構(gòu)算法設(shè)計策略算法設(shè)計策略-分而治之分而治之 前一頁 休息39算法設(shè)計策略算法設(shè)計策略-遞歸法遞歸法 當(dāng)求解問題滿足：當(dāng)求解問題滿足： (1) (1)：有遞推關(guān)系：有遞推關(guān)系 (2) (2)：有出口，通常使用遞歸法。：有出口，通常使用遞歸法。例如：求例如：求f(n)=n!f(n)=n! 可以理解為當(dāng)可以理解為當(dāng)n=1n=1時，時，f(n)=1(f(n)=1(出口出

15、口) ) 當(dāng)當(dāng)n=kn=k時，時，f(k)=f(k-1)f(k)=f(k-1)* *k(k(遞推關(guān)系遞推關(guān)系) )所以，可以用遞歸法求所以，可以用遞歸法求n!n! 前一頁 休息40算法的主要特征算法的主要特征 有效性有效性 所有操作都應(yīng)能有效地執(zhí)行，并能得到確所有操作都應(yīng)能有效地執(zhí)行，并能得到確定的結(jié)果定的結(jié)果有窮性有窮性 總是可以在執(zhí)行有限步有限的時間內(nèi)完成總是可以在執(zhí)行有限步有限的時間內(nèi)完成確定性確定性 每個操作必須是明確的，對于相同的輸每個操作必須是明確的，對于相同的輸 入只能得出相同的結(jié)果入只能得出相同的結(jié)果輸輸 入入 一個算法可有零個或多個輸入一個算法可有零個或多個輸入輸輸 出出 一

16、個算法可以有一個或多個輸出。一個算法可以有一個或多個輸出。 任何一個算法至少應(yīng)有一個輸出任何一個算法至少應(yīng)有一個輸出 前一頁 休息41算法的主要因素算法的主要因素 正確性正確性 算法應(yīng)該滿足具體問題的需求，正確反映求解算法應(yīng)該滿足具體問題的需求，正確反映求解 問題對輸入、輸出和加工處理等方面的需求。問題對輸入、輸出和加工處理等方面的需求。可讀性可讀性 可讀性好的算法有助于對算法的理解，易于調(diào)可讀性好的算法有助于對算法的理解，易于調(diào) 試和修改等試和修改等健壯性健壯性 當(dāng)輸入了非法數(shù)據(jù)時，算法應(yīng)能適當(dāng)?shù)刈龀龇串?dāng)輸入了非法數(shù)據(jù)時，算法應(yīng)能適當(dāng)?shù)刈龀龇?映或進行處理，輸出表示錯誤性質(zhì)的信息并中止映或進

17、行處理，輸出表示錯誤性質(zhì)的信息并中止高效性高效性 算法的時間開銷和空間開銷往往是相互制約的，算法的時間開銷和空間開銷往往是相互制約的， 對高時間效率和低內(nèi)存空間占用量的要求，只能對高時間效率和低內(nèi)存空間占用量的要求，只能 根據(jù)問題的性質(zhì)折中處理根據(jù)問題的性質(zhì)折中處理 前一頁 休息42算法復(fù)雜性分析算法復(fù)雜性分析 前一頁 休息43 例例99欲在按升序排列的欲在按升序排列的n n個元素個元素 a a1 1,a,a2 2, ,a,an n(a(ai iaai+1i+1) )中查找中查找 是否有與是否有與b b相同的元素。相同的元素。 算法一：從第一個元素算法一：從第一個元素a1開始逐一比較。開始逐一

18、比較。此時，最好的情況是此時，最好的情況是a1就是要查找的元素，就是要查找的元素，只需比較一次。最壞情況則需要比較只需比較一次。最壞情況則需要比較n次，次，即一直比較到即一直比較到an才能得到結(jié)果；假定每個才能得到結(jié)果；假定每個元素與元素與b相同是等概率的，則平均需要比相同是等概率的，則平均需要比較較n/2次。次。 前一頁 休息44算法二：采用折半查找算法二：采用折半查找( (二分查找二分查找) )的方法，即的方法，即先用位居先用位居中點中點的元素的元素a a（n/2n/2）與與b b比較，比較， 若若b= ab= a（n/2n/2），則查找成功。，則查找成功。 若若baba（n/2n/2），

19、同時，同時b ba a（n/2n/2），則在，則在a a1 1,a,a2 2, ,a,a（n/2-1n/2-1）中采用上述方法繼續(xù)查找；中采用上述方法繼續(xù)查找； 否則在否則在a a（n/2+1n/2+1）,a,a（n/2+2n/2+2）, ,a,an n采用上述采用上述方法繼續(xù)查找。方法繼續(xù)查找。 這種算法最多也只需要比較這種算法最多也只需要比較loglog2 2n n次。次。 前一頁 休息45算法復(fù)雜性分析算法復(fù)雜性分析 前一頁 休息46 前一頁 休息47結(jié)構(gòu)化程序設(shè)計思想結(jié)構(gòu)化程序設(shè)計思想 前一頁 休息48軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息49軟件開發(fā)過程軟

20、件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息50軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息51軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息52軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息53軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息54軟件開發(fā)過程軟件開發(fā)過程軟件的開發(fā)過程軟件的開發(fā)過程 前一頁 休息55程序設(shè)計方法程序設(shè)計方法 程序設(shè)計是一個將人類思維轉(zhuǎn)化程序設(shè)計是一個將人類思維轉(zhuǎn)化為計算機思維的過程，可分為為計算機思維的過程，可分為面向過面向過程的程序設(shè)計程的程序設(shè)計和和面向?qū)ο蟮某绦蛟O(shè)計面

21、向?qū)ο蟮某绦蛟O(shè)計兩大類。兩大類。 前一頁 休息56面向過程的程序設(shè)計面向過程的程序設(shè)計 l過程是過程是為了得到問題的解而執(zhí)行的一步步的為了得到問題的解而執(zhí)行的一步步的操作；操作；l面向過程的程序設(shè)計面向過程的程序設(shè)計是一種基于功能分析及是一種基于功能分析及每個功能由計算機的一個操作過程實現(xiàn)的程每個功能由計算機的一個操作過程實現(xiàn)的程序設(shè)計方法，又稱為傳統(tǒng)的程序設(shè)計。序設(shè)計方法，又稱為傳統(tǒng)的程序設(shè)計。l面向過程程序設(shè)計的面向過程程序設(shè)計的關(guān)鍵是規(guī)劃算法和數(shù)據(jù)關(guān)鍵是規(guī)劃算法和數(shù)據(jù)結(jié)構(gòu)。結(jié)構(gòu)。 前一頁 休息57面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計 l面向?qū)ο蟪绦蛟O(shè)計面向?qū)ο蟪绦蛟O(shè)計模擬自然界認(rèn)識和處理

22、事模擬自然界認(rèn)識和處理事物的方法物的方法,將數(shù)據(jù)和對數(shù)據(jù)的操作方法組織在將數(shù)據(jù)和對數(shù)據(jù)的操作方法組織在一起，形成一個相對獨立的整體，稱為一起，形成一個相對獨立的整體，稱為對象對象l對象是活動的，對象行為靠消息觸發(fā)而激活對象是活動的，對象行為靠消息觸發(fā)而激活l面向?qū)ο蟪绦蛟O(shè)計的面向?qū)ο蟪绦蛟O(shè)計的關(guān)鍵是確定對象并對其關(guān)鍵是確定對象并對其分類分類 前一頁 休息58程序設(shè)計過程程序設(shè)計過程傳統(tǒng)的程序設(shè)計過程主要包括以下幾個階段：傳統(tǒng)的程序設(shè)計過程主要包括以下幾個階段：1分析問題分析問題 通過原始資料，取得對問題的一個清晰的通過原始資料，取得對問題的一個清晰的理解，進而確定解決問題的目標(biāo)（稱為理解，進而確定解決問題的目標(biāo)（稱為輸出輸出）以及實現(xiàn)該目標(biāo)所需要的條件（稱為以及實現(xiàn)該目標(biāo)所需要的條件（稱為輸入輸入）。）。 前一頁 休息59程序設(shè)計過程程序設(shè)計過程2設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)描述了問題涉及的對象之間的聯(lián)數(shù)據(jù)結(jié)構(gòu)描述了問題涉及的對象之間的聯(lián)系和組織結(jié)構(gòu)系和組織結(jié)構(gòu)；算法描述了求解問題的步算法描述了求解問題的步驟或規(guī)則驟或規(guī)則。設(shè)計合理的數(shù)據(jù)結(jié)構(gòu)往往可以。設(shè)計合理的數(shù)據(jù)