09程序設(shè)計(jì)語言初步第四章二ppt課件

1、 1第四章第四章 算法設(shè)計(jì)方法算法設(shè)計(jì)方法 24.1 算法的概念算法的概念4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究提綱提綱 3 程序設(shè)計(jì)的目的和步驟程序設(shè)計(jì)的目的和步驟 算法的描述方式算法的描述方式 計(jì)算機(jī)算法及其特性計(jì)算機(jī)算法及其特性4.1 算法的概念算法的概念 44.1 算法的概念算法的概念一一. 程序設(shè)計(jì)的目的程序設(shè)計(jì)的目的計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的根本問題是：什計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的根本問題是：什么能夠被有效地自動化么能夠被有效地自動化 ；設(shè)計(jì)程序的根本目的：讓計(jì)算機(jī)

2、幫助人們設(shè)計(jì)程序的根本目的：讓計(jì)算機(jī)幫助人們自動地完成所要處理的復(fù)雜任務(wù)；自動地完成所要處理的復(fù)雜任務(wù)；程序設(shè)計(jì)兩個核心問題：程序設(shè)計(jì)兩個核心問題：“做什么與做什么與“怎怎么做么做” ；其中需求分析解決；其中需求分析解決“做什么做什么”，程，程序設(shè)計(jì)解決序設(shè)計(jì)解決“怎么做怎么做” 。 54.1 算法的概念算法的概念二二. 程序設(shè)計(jì)兩步走程序設(shè)計(jì)兩步走對復(fù)雜問題，直接寫出能解決該問題的對復(fù)雜問題，直接寫出能解決該問題的計(jì)算機(jī)程序是困難的，為此，人們在進(jìn)計(jì)算機(jī)程序是困難的，為此，人們在進(jìn)行程序設(shè)計(jì)時分兩步走：行程序設(shè)計(jì)時分兩步走：1算法設(shè)計(jì)：不使用程序設(shè)計(jì)語言，而使算法設(shè)計(jì)：不使用程序設(shè)計(jì)語言，而

3、使用一種較簡單明了的表達(dá)方式例如自用一種較簡單明了的表達(dá)方式例如自然語言設(shè)計(jì)出求解問題的步驟序列然語言設(shè)計(jì)出求解問題的步驟序列-算法。算法。2程序編寫：根據(jù)設(shè)計(jì)并描述好的算法，程序編寫：根據(jù)設(shè)計(jì)并描述好的算法，使用某種程序設(shè)計(jì)語言編寫對應(yīng)于該算使用某種程序設(shè)計(jì)語言編寫對應(yīng)于該算法的程序法的程序 。 6三三. 算法的概念算法的概念算法：是解決問題的步驟序列操作序列算法：是解決問題的步驟序列操作序列）。）。 4.1 算法的概念算法的概念起床起床穿衣、疊被穿衣、疊被去水房洗漱去水房洗漱回宿舍放洗漱用品回宿舍放洗漱用品騎車去食堂騎車去食堂排隊(duì)買飯排隊(duì)買飯吃飯吃飯交回餐具交回餐具騎車去教室騎車去教室描述

4、的是描述的是活動和過活動和過程程7:20前離開宿舍前離開宿舍7:50前離開食堂前離開食堂8:00前進(jìn)入教室前進(jìn)入教室描述的是操作執(zhí)行后描述的是操作執(zhí)行后的狀態(tài)，通過狀態(tài)的的狀態(tài)，通過狀態(tài)的轉(zhuǎn)移來描述所執(zhí)行的轉(zhuǎn)移來描述所執(zhí)行的操作。操作?？赡艿幕顒樱嚎赡艿幕顒樱浩鸫?、穿衣疊起床、穿衣疊被、洗漱等被、洗漱等可能的活動：可能的活動：騎車到食堂、騎車到食堂、排隊(duì)買飯、吃排隊(duì)買飯、吃飯、交回餐具飯、交回餐具 74.1 算法的概念算法的概念四四. 計(jì)算機(jī)算法及其特性計(jì)算機(jī)算法及其特性什么是計(jì)算機(jī)可執(zhí)行的操作；什么是計(jì)算機(jī)可執(zhí)行的操作；要在計(jì)算機(jī)能力集上進(jìn)行算法設(shè)計(jì)；要在計(jì)算機(jī)能力集上進(jìn)行算法設(shè)計(jì)；算法必須

5、具備的五個特性：算法必須具備的五個特性：可執(zhí)行性：算法中的每一個步驟都是計(jì)算機(jī)可執(zhí)行可執(zhí)行性：算法中的每一個步驟都是計(jì)算機(jī)可執(zhí)行的在計(jì)算機(jī)能力集范圍內(nèi)）的在計(jì)算機(jī)能力集范圍內(nèi)） ；確定性：算法中的每一個步驟，必須是明確定義的確定性：算法中的每一個步驟，必須是明確定義的，不得有任何歧義性，不得有任何歧義性 ；有窮性：算法必須在執(zhí)行有窮步之后結(jié)束；有窮性：算法必須在執(zhí)行有窮步之后結(jié)束； 有輸入信息的說明：對加工對象提要求；有輸入信息的說明：對加工對象提要求；有輸出信息的步驟有輸出信息的步驟 ：至少要輸出問題答案。：至少要輸出問題答案。 8例例1 求求12910 ，即，即10！ 算法思路：算法思路：

6、 計(jì)算機(jī)能力集只提供兩數(shù)相乘的運(yùn)算。計(jì)算機(jī)能力集只提供兩數(shù)相乘的運(yùn)算。 N！=N （N-1）！）！ 10！=10 9！=10 9 8！ =10 9 8 7！ =. =10 9 8 2 1! 先計(jì)算先計(jì)算1！、再計(jì)算！、再計(jì)算2!=2*1!、再計(jì)算、再計(jì)算3!=3*2!,以此類推，直到計(jì)算出以此類推，直到計(jì)算出10!=10*9!。 使用變量使用變量p 9例例1 求求12910 ，即，即10！第一種算法：第一種算法：S1(求求2!)：先求：先求21，得到結(jié)果，得到結(jié)果2并賦值給變量并賦值給變量p；即：；即：21p；S2 (求求3!) ：將步驟：將步驟S1得到的乘積得到的乘積pp=2再乘以再乘以3，

7、得結(jié)果，得結(jié)果6并并 賦值給變量賦值給變量p；即：；即： 3 pp；S3(求求4!)：將：將pp=6再乘以再乘以4，得，得24并賦值給變量并賦值給變量p；即：；即： 4pp；S4(求求5！)：將：將pp=24再乘以再乘以5，得，得120并賦值給變量并賦值給變量p；即：；即： 5pp；S9(求求10!)：將：將pp=362880)乘以乘以10，得，得3628800，10pp； 10#includemain() int p; p=2*1; /求求2!賦值給賦值給p p=3*p; /求求3!賦值給賦值給p p=4*p; p=5*p; p=6*p; p=7*p; p=8*p; p=9*p; p=10*

8、p; /求求10!賦值給賦值給p printf(%d,p); system(pause); return 0; 評價：求評價：求10!需要寫需要寫9個賦值操作，算法個賦值操作，算法過于繁瑣！試想：過于繁瑣！試想：求求1000！的算法！的算法 11 對算法進(jìn)行抽象對算法進(jìn)行抽象:核心操作就是兩數(shù)相乘核心操作就是兩數(shù)相乘ipp ，反復(fù)相乘，反復(fù)相乘10-1=9次，次，i初始值為初始值為2，p初始值為初始值為1，每相乘一次，每相乘一次i的值加的值加1。 根據(jù)上述分析，本題可利用循環(huán)結(jié)構(gòu)求解：根據(jù)上述分析，本題可利用循環(huán)結(jié)構(gòu)求解：第第1次循環(huán)用于求次循環(huán)用于求2！，第！，第2次循環(huán)在第次循環(huán)在第1次循

9、次循環(huán)基礎(chǔ)上求環(huán)基礎(chǔ)上求3！，！，,第第9次循環(huán)在第次循環(huán)在第8次循環(huán)基礎(chǔ)次循環(huán)基礎(chǔ)上求上求10！例例1 求求12910 ，即，即10！ 12定義兩個變量定義兩個變量p和和i，p代表階乘結(jié)果代表階乘結(jié)果,i代表本次循環(huán)要代表本次循環(huán)要求的是求的是i!； 循環(huán)條件：循環(huán)條件：ip；S4：使：使i的值加的值加1，即，即i+1=i；S5：如果：如果i=10，返回重新執(zhí)行步驟，返回重新執(zhí)行步驟S3以及其后的以及其后的步驟步驟S4和和S5；否則，算法結(jié)束。；否則，算法結(jié)束。 最后得到最后得到p的值就是的值就是10！的值。！的值。 求求12910算法思路：算法思路：“迭代和迭代和“循環(huán)循環(huán)” ：在程序設(shè)計(jì)

10、中，重復(fù)執(zhí)行同樣操：在程序設(shè)計(jì)中，重復(fù)執(zhí)行同樣操作的過程稱為作的過程稱為“迭代迭代”。程序中被重復(fù)執(zhí)行的程序段。程序中被重復(fù)執(zhí)行的程序段稱為稱為“循環(huán)循環(huán)”。 14例例1源程序源程序#include main() int n, i, p; /n：存儲要求階乘的數(shù)；：存儲要求階乘的數(shù)；p：存儲求得的階乘；：存儲求得的階乘； printf(input n:n);scanf(%d,&n);i=2; p=1; while (i = n) p=i*p; i=i+1; printf(%d!=%d,n,p); system(pause); return 0; 15 練習(xí)練習(xí)1：輸入十個整數(shù)，求出最大

11、值、最小值：輸入十個整數(shù)，求出最大值、最小值。 算法思路：采用迭代計(jì)算的方法算法思路：采用迭代計(jì)算的方法 以求最大值為例，即：以求最大值為例，即： Max(N1)=N1 Max(N2,N1)= N1 if N2=N1 Max(N3,N2,N1)= Max( N3, Max(N2,N1) ) . Max(Nn , Nn-1 ,N2,N1) Max(Nn ,Max(Nn-1 ,N2,N1)定義變量定義變量max來存儲前來存儲前n-1個整數(shù)的最大值。個整數(shù)的最大值。第第n個數(shù)將和個數(shù)將和max比比較，決定前較，決定前n個數(shù)的個數(shù)的最大值。最大值。整個問題就被轉(zhuǎn)變?yōu)榍笳麄€問題就被轉(zhuǎn)變?yōu)榍?次兩個次兩個

12、數(shù)的最大值。數(shù)的最大值。每一次都是讀入一個數(shù)，和之每一次都是讀入一個數(shù)，和之前求得的最大數(shù)再去比較。前求得的最大數(shù)再去比較。 16循環(huán)條件：循環(huán)條件：imax,則則max=n； 否則，如果否則，如果nmin,則則min=n； i=i+1;循環(huán)初始化：循環(huán)初始化：讀入一整數(shù)讀入一整數(shù)n;minn; max=n;i2；請寫出本題源程序請寫出本題源程序 17源程序：輸入十個整數(shù)，求出最大值、最小值源程序：輸入十個整數(shù)，求出最大值、最小值#include#define COUNT 10 main() int i, n, max, min;/i:循環(huán)計(jì)數(shù)；循環(huán)計(jì)數(shù)；n:讀取的數(shù)；讀取的數(shù)； /max:當(dāng)

13、前最大值當(dāng)前最大值; min:當(dāng)前最小值當(dāng)前最小值 scanf(%d, &n); max=n; /將第一個數(shù)作為最大值和最小值將第一個數(shù)作為最大值和最小值 min=n; i=2; /代表接下去要讀取的是第代表接下去要讀取的是第2個數(shù)個數(shù) 18源程序：輸入十個整數(shù)，求出最大值、最小值源程序：輸入十個整數(shù)，求出最大值、最小值(續(xù)續(xù)) while (i max) /求最大數(shù)求最大數(shù) max = n; else if (n i；問題分析：就是反復(fù)輸入處理每一個學(xué)生的信息，處理問題分析：就是反復(fù)輸入處理每一個學(xué)生的信息，處理120次。次。 20輸入輸入120個學(xué)生的學(xué)號和成績，要求將他們之中個學(xué)

14、生的學(xué)號和成績，要求將他們之中成績在成績在60分以上者的學(xué)號和成績打印出來。分以上者的學(xué)號和成績打印出來。S1S1：1=i1=i；S2S2：讀入第：讀入第i i個學(xué)生的學(xué)號和成績分別到變量個學(xué)生的學(xué)號和成績分別到變量numnum和和scorescore中；中；S3S3：如果：如果score 60score 60，則打印，則打印numnum和和score score ；S4S4：i+1=ii+1=i；S5S5：如果：如果i120i120，則返回，則返回S2S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。，繼續(xù)執(zhí)行；否則，算法結(jié)束。循環(huán)處理模式：循環(huán)處理模式：處理本次循環(huán)要做的任務(wù)；處理本次循環(huán)要做的任務(wù)；為下一

15、次循環(huán)做準(zhǔn)備；為下一次循環(huán)做準(zhǔn)備； 214.1 算法的概念算法的概念練習(xí)練習(xí)2：請寫出本題對應(yīng)的程序：請寫出本題對應(yīng)的程序 224.1 算法的概念算法的概念#include main() int no,total,count;/no:學(xué)號。學(xué)號。total:總學(xué)生數(shù)?？倢W(xué)生數(shù)。count：計(jì)數(shù)：計(jì)數(shù) float score;/成果成果 printf(how many int numbers do you want to input:n);scanf(%d,&total); count=1;while(count60) printf(no:%dtscore:%fn,no,score);

16、count=count+1; system(pause); return 0； 23例例3 一個大于或等于一個大于或等于3的正整數(shù)，判斷它是否為一的正整數(shù)，判斷它是否為一個素?cái)?shù)質(zhì)數(shù)）個素?cái)?shù)質(zhì)數(shù)） 。所謂質(zhì)數(shù)，是指除了所謂質(zhì)數(shù)，是指除了1和該數(shù)本身外，不能被其和該數(shù)本身外，不能被其他任何整數(shù)整除的數(shù)。例如，他任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)質(zhì)數(shù)）。是素?cái)?shù)質(zhì)數(shù)）。因?yàn)樗荒鼙灰驗(yàn)樗荒鼙?，3，4，12整除。整除。由于素?cái)?shù)在當(dāng)代的密碼學(xué)中扮演了中心的作用，由于素?cái)?shù)在當(dāng)代的密碼學(xué)中扮演了中心的作用，所以該問題具有重要意義。所以該問題具有重要意義。判斷一個數(shù)判斷一個數(shù)nn3是否為質(zhì)數(shù)：將是否為質(zhì)數(shù)：

17、將n作為被除作為被除數(shù)，將數(shù)，將2到到n-1各個整數(shù)依次作為除數(shù)，如果各個整數(shù)依次作為除數(shù)，如果都不能被整除，則都不能被整除，則n為素?cái)?shù)。為素?cái)?shù)。4.1 算法的概念算法的概念 24判斷質(zhì)數(shù)看看n能否被能否被2到到n-1之間的各個整數(shù)整除：之間的各個整數(shù)整除： 變量抽象：變量抽象：n：存放被判斷的整數(shù)；：存放被判斷的整數(shù)；i：存放除：存放除 數(shù)，取值為數(shù)，取值為2,n-1；r：存放：存放n/i得到的余數(shù)得到的余數(shù)循環(huán)體：循環(huán)體：n被被i除，得余數(shù)除，得余數(shù)r；即；即n mod i=r；如果如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素?cái)?shù)不是素?cái)?shù)”，算法結(jié)束；否則算法結(jié)束；否

18、則i+1=i；循環(huán)條件：循環(huán)條件： ir；如果如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素?cái)?shù)不是素?cái)?shù)”，令令isPrim=1；否則；否則i+1=i；循環(huán)條件：循環(huán)條件： irn mod i=rS4S4：如果：如果r=0r=0，表示，表示n n能被能被i i整除，則打印整除，則打印n“n“不是素?cái)?shù)不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行，算法結(jié)束；否則執(zhí)行S5S5；S5S5：i+1=ii+1=i；S6S6：如果：如果in-1in-1，返回，返回S3S3；否則，打?。环駝t，打印n“n“是素?cái)?shù)是素?cái)?shù)”，算法結(jié)束。，算法結(jié)束。 n：被判斷的整數(shù)；：被判斷的整數(shù)；i：被除數(shù)；：被除數(shù)；r：

19、存放：存放n/i得到的余數(shù)得到的余數(shù)事實(shí)上，事實(shí)上，i只需只需2到到 之間的整數(shù)整除即可。之間的整數(shù)整除即可。n 274.1 算法的概念算法的概念4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究提綱提綱 284.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu) 三種控制結(jié)構(gòu)三種控制結(jié)構(gòu)(Bohra和和Jacopini )順序結(jié)構(gòu)、順序結(jié)構(gòu)、 選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 順序結(jié)構(gòu)順序結(jié)構(gòu) 按書寫順序執(zhí)行的語句構(gòu)按書寫順序執(zhí)行的語句構(gòu)成的程序段。成的程序段。 29選擇結(jié)構(gòu)選擇結(jié)構(gòu)u

20、 根據(jù)給定的表達(dá)式是否成立而選擇執(zhí)行操作根據(jù)給定的表達(dá)式是否成立而選擇執(zhí)行操作A A或操或操作作B B。如果表達(dá)式成立，則執(zhí)行操作。如果表達(dá)式成立，則執(zhí)行操作A A；如果表達(dá)式不；如果表達(dá)式不成立，則執(zhí)行操作成立，則執(zhí)行操作B B。u操作操作B B可以為空?？梢詾榭铡?.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu) 30 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)C語言無直到型循環(huán)結(jié)構(gòu)。語言無直到型循環(huán)結(jié)構(gòu)。比較：直到型循環(huán)結(jié)構(gòu)和比較：直到型循環(huán)結(jié)構(gòu)和C語言中的語言中的do-while結(jié)構(gòu)？結(jié)構(gòu)？ 直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu) 31三種控制結(jié)構(gòu)的共同點(diǎn)三種控制結(jié)構(gòu)的共同點(diǎn)

21、 只有一個入口只有一個入口a a處）處） 只有一個出口只有一個出口b b處）處） 結(jié)構(gòu)內(nèi)的每一個部分都有機(jī)會被執(zhí)行到結(jié)構(gòu)內(nèi)的每一個部分都有機(jī)會被執(zhí)行到 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)”（無終止的循環(huán)）（無終止的循環(huán)）4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)由這三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可由這三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜問題！以解決任何復(fù)雜問題！ 324.1 算法的概念算法的概念4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究提綱提綱 334.

22、3 算法的描述方法算法的描述方法 用自然語言描述 用流程圖描述 用N-S流程圖描述 用偽碼描述 用計(jì)算機(jī)語言描述 344.3 算法的描述方法自然語言算法的描述方法自然語言文字冗長；文字冗長； 不嚴(yán)格，易產(chǎn)生歧義二義性）；不嚴(yán)格，易產(chǎn)生歧義二義性）； 不方便描述分支和循環(huán)結(jié)構(gòu)；不方便描述分支和循環(huán)結(jié)構(gòu)； 354.3 算法的描述方法流程圖算法的描述方法流程圖 流程圖的基本元素流程圖的基本元素ANSIANSI規(guī)定）規(guī)定） 起止框輸入/出框判斷框處理框流程線 連接點(diǎn) 注釋框 364.3 算法的描述方法流程圖算法的描述方法流程圖流程圖描述的選擇結(jié)構(gòu)流程圖描述的選擇結(jié)構(gòu) 37 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu) 直

23、到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)流程圖描述的循環(huán)結(jié)構(gòu)流程圖描述的循環(huán)結(jié)構(gòu)4.3 算法的描述方法流程圖算法的描述方法流程圖 38連接點(diǎn)小圓圈）：用于將畫在不同地方的流程線連連接點(diǎn)小圓圈）：用于將畫在不同地方的流程線連接起來接起來 39求求10！流程圖！流程圖使用當(dāng)型循使用當(dāng)型循環(huán)結(jié)構(gòu)描述環(huán)結(jié)構(gòu)描述 40打印學(xué)生序號打印學(xué)生序號及成績流程圖及成績流程圖 41判斷質(zhì)判斷質(zhì)數(shù)的流數(shù)的流程圖程圖使用直到型循使用直到型循環(huán)結(jié)構(gòu)描述環(huán)結(jié)構(gòu)描述判斷判斷r是否是否為為0條件成立則條件成立則跳出循環(huán)跳出循環(huán) 42練習(xí)：將以上流程圖改成用當(dāng)型循環(huán)結(jié)構(gòu)表示。練習(xí)：將以上流程圖改成用當(dāng)型循環(huán)結(jié)構(gòu)表示。該流程圖中循該流程圖中循

24、環(huán)結(jié)構(gòu)有兩個環(huán)結(jié)構(gòu)有兩個出口！違反單出口！違反單入單出原則！入單出原則！如何改進(jìn)？如何改進(jìn)？ 43改進(jìn)后的流程圖：改進(jìn)后的流程圖：單入單出單入單出 設(shè)置標(biāo)志設(shè)置標(biāo)志位位isPrim 44 傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端 對流程線的使用沒有嚴(yán)格限制，閱讀困難；對流程線的使用沒有嚴(yán)格限制，閱讀困難； 不能保證算法結(jié)構(gòu)的單入單出特性；不能保證算法結(jié)構(gòu)的單入單出特性； 占用篇幅較多占用篇幅較多 ； 4.3 算法的描述方法算法的描述方法N-S流程圖流程圖必須限制箭頭的濫用，讓流程只能順序執(zhí)必須限制箭頭的濫用，讓流程只能順序執(zhí)行下去！行下去！保證結(jié)構(gòu)化原則的流程描述工具保證結(jié)構(gòu)化原則的流程描述工具N-S

25、圖圖 45 基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法N-S流程圖流程圖p、p1表示的是表示的是判斷條件；判斷條件；A、B框是操作；框是操作；留意：留意：A、B框可框可以是一個簡單以是一個簡單的操作如讀的操作如讀入數(shù)據(jù)或打印入數(shù)據(jù)或打印輸出等），也輸出等），也可以是三種基可以是三種基本結(jié)構(gòu)之一本結(jié)構(gòu)之一順序結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)選擇結(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) 46例例1 求求10!的的N-S流程圖流程圖4.3 算法的描述方法算法的描述方法N-S流程圖流程圖 47例例2 打印學(xué)生成績打印學(xué)生成績N-S流程圖流程圖4.3 算法的描述方法算法的描述方法N-S流程圖流程圖

26、 48例例3 判斷質(zhì)數(shù)的判斷質(zhì)數(shù)的N-S流程圖流程圖4.3 算法的描述方法算法的描述方法N-S流程圖流程圖 494.3 算法的描述方法偽碼描述算法的描述方法偽碼描述 流程圖和流程圖和N-S圖畫起來比較費(fèi)事，適合于表示圖畫起來比較費(fèi)事，適合于表示算法，而在算法設(shè)計(jì)中使用不是很理想。算法，而在算法設(shè)計(jì)中使用不是很理想。 偽碼偽碼 用介于自然語言和程序設(shè)計(jì)語言之間的文用介于自然語言和程序設(shè)計(jì)語言之間的文字和符號來描述算法。字和符號來描述算法?！厩巴?IF x is positive THEN print x ELSE print yWHILE i60 THEN print score i加加1 5

27、04.3 算法的描述方法算法的描述方法例例4：利用泰勒級數(shù)：利用泰勒級數(shù)：- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn計(jì)算正弦的值，直到最后一項(xiàng)絕對值小于計(jì)算正弦的值，直到最后一項(xiàng)絕對值小于10-6 時為止。時為止。被除被除數(shù)數(shù)除數(shù)除數(shù)符號符號n1 n2 n3分析：求分析：求n項(xiàng)和的算法思路項(xiàng)和的算法思路Sum(a1)=a1Sum(a1,a2)=Sum(a1)+a2 =a1+a2Sum(a1,a2, a3)=Sum(a1,a2)+a3Sum(a1,a2,an)=Sum(a1,a2,an-1

28、)+an 514.3 算法的描述方法算法的描述方法 算法的核心操作是求兩數(shù)之和，其中第一個操算法的核心操作是求兩數(shù)之和，其中第一個操作數(shù)是前一次求得的和。如何求第二個操作數(shù)作數(shù)是前一次求得的和。如何求第二個操作數(shù)？ 算法算法1：n決定了第決定了第n項(xiàng)因子的值，即第二個操項(xiàng)因子的值，即第二個操作數(shù)；因此每一次可根據(jù)當(dāng)前作數(shù)；因此每一次可根據(jù)當(dāng)前n的值計(jì)算出第的值計(jì)算出第二個操作數(shù)。二個操作數(shù)。 請用請用NS圖描述出算法圖描述出算法1。 52求求sin(x)算法算法1i代表下一個代表下一個p是第幾項(xiàng)，是第幾項(xiàng)，因此初值是因此初值是1變量抽象：變量抽象： x：存儲未知數(shù)：存儲未知數(shù)x的的值；值； s

29、um：存儲和：存儲和 ； p：存儲當(dāng)前待加的：存儲當(dāng)前待加的因子；因子；i：當(dāng)前待加：當(dāng)前待加的是第幾個因子的是第幾個因子 53問題：任何數(shù)據(jù)類型只能表示一定范圍內(nèi)的數(shù)，問題：任何數(shù)據(jù)類型只能表示一定范圍內(nèi)的數(shù)，當(dāng)試圖往變量中存儲在范圍之外的數(shù)，數(shù)據(jù)無當(dāng)試圖往變量中存儲在范圍之外的數(shù)，數(shù)據(jù)無法正確存儲。求法正確存儲。求x的的n次方和次方和(2n-1)!時可能會導(dǎo)時可能會導(dǎo)致結(jié)果太大而溢出。致結(jié)果太大而溢出。解決方法：解決方法：1.用浮點(diǎn)型變量來保存用浮點(diǎn)型變量來保存(2n-1)!的結(jié)果的結(jié)果2.改進(jìn)算法改進(jìn)算法算法算法2 544.3 算法的描述方法算法的描述方法=pi 1- - - -)!32

30、() 1(32ixii=Pi- - - -+ +)!12() 1(121ixiiPiPipi 1- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn算法算法2：設(shè)第：設(shè)第i項(xiàng)因子表示為項(xiàng)因子表示為 ，調(diào)查，調(diào)查 和和 的關(guān)系。的關(guān)系。 = = * *(-1)(-1)* * x2 /(2i-1) x2 /(2i-1)* *(2i-(2i-2)2)Pipi 1- 55請用請用NS圖描述算法圖描述算法2。4.3 算法的描述方法算法的描述方法 【源程序演示】i代表下一個代表下一個p是第幾項(xiàng)，是第幾項(xiàng)，因此

31、初值是因此初值是1 56#include#includemain()int i;float x; double sum,p; /p用于存放待加的那一項(xiàng)用于存放待加的那一項(xiàng)printf(input x:);scanf(%f,&x);/*變量初始化變量初始化*/sum=0.0;i=1;p=x;/*求解求解*/while(fabs(p)1e-8) sum=sum+p; i=i+1; p=-p*x*x/(2*i-2)*(2*i-1); printf(sin(%f) = %lfn,x,sum); system(pause); return 0; 574.1 算法的概念算法的概念4.2 算法的三種

32、基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究提綱提綱 58 源自于對源自于對goto語句的爭論語句的爭論 goto語句詳見語句詳見436頁頁4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 59#include main() int count=1; start: /標(biāo)號標(biāo)號,是跟有冒號的標(biāo)識符是跟有冒號的標(biāo)識符 if (count10) goto end; printf(%d ,count); count=count+1; goto start; end: printf(n); system(p

33、ause); return 0; 1 2 3 4 5 6 7 8 9 10請按任意鍵繼續(xù). . .運(yùn)行效果：運(yùn)行效果： 604.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、閱讀、修改和維護(hù)種程序便于編寫、閱讀、修改和維護(hù) 。 結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)化，提倡清晰的結(jié)構(gòu) 。 結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思想：采用分而治之的方結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思想：采用分而治之的方法，將一個復(fù)雜問題分解為相對簡單的一些子問

34、題，法，將一個復(fù)雜問題分解為相對簡單的一些子問題，然后針對這些子問題進(jìn)行求解。如果某個子問題仍然然后針對這些子問題進(jìn)行求解。如果某個子問題仍然是比較復(fù)雜的，再進(jìn)一步分解為子是比較復(fù)雜的，再進(jìn)一步分解為子-子問題，直到所有子問題，直到所有問題都能夠求解。求解問題的過程是分階段進(jìn)行的，問題都能夠求解。求解問題的過程是分階段進(jìn)行的，每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼拿總€階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)范圍內(nèi)67個之內(nèi)）。個之內(nèi)）。 614.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法自頂向下；自頂向下；逐步細(xì)化；逐步細(xì)化；模塊化設(shè)計(jì)函數(shù)）；

35、模塊化設(shè)計(jì)函數(shù)）；結(jié)構(gòu)化編碼三種基本結(jié)構(gòu)）。結(jié)構(gòu)化編碼三種基本結(jié)構(gòu)）。 62例例4.13 利用輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公約數(shù)。利用輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公約數(shù)。輾轉(zhuǎn)相除法求最大公約數(shù)的數(shù)學(xué)定義如下：輾轉(zhuǎn)相除法求最大公約數(shù)的數(shù)學(xué)定義如下：GCDx,y）= y | xy and x MOD y = 0 GCDy, x MOD y）| xy and x MOD y 0; 闡明：先判斷闡明：先判斷x能否被能否被y整除，若可以，則最大公約數(shù)就整除，若可以，則最大公約數(shù)就是除數(shù)是除數(shù)y；否則，則將；否則，則將y 作為被除數(shù)，作為被除數(shù)，x MOD y 作為作為除數(shù)繼續(xù)上面的操作，直到除數(shù)繼續(xù)上面

36、的操作，直到x能否被能否被y整除為止。整除為止。 GCD(6,4)GCD(4,2)= 2=GCD(124,6)最大公約數(shù)為最大公約數(shù)為2例如：求例如：求GCD(124,6)的過程為：的過程為： 63算法算法1xyr231交換變量交換變量x和和y的值：的值：自頂向下，逐步細(xì)化自頂向下，逐步細(xì)化 64最終算法1 算法設(shè)計(jì)任務(wù)結(jié)算法設(shè)計(jì)任務(wù)結(jié)束的標(biāo)準(zhǔn)是各步束的標(biāo)準(zhǔn)是各步驟已精細(xì)到能用驟已精細(xì)到能用語句描述，即滿語句描述，即滿足算法的足算法的5大特大特征標(biāo)志算法設(shè)計(jì)征標(biāo)志算法設(shè)計(jì)任務(wù)結(jié)束任務(wù)結(jié)束 。 65算法算法2思索：能否不借助于變量思索：能否不借助于變量r，而是而是xy; y x%y？ 或者或者y

37、 x%y；x y 66 練習(xí)練習(xí)3：設(shè)計(jì)算法，求一個正整數(shù)的長度。：設(shè)計(jì)算法，求一個正整數(shù)的長度。 算法算法1：例如：例如num=12345，求，求num的長度的長度 第第1步：去掉最低位，步：去掉最低位，num=1234，長度，長度len=1 第第2步：去掉最低位，步：去掉最低位，num=123，長度，長度len=2 第第3步：去掉最低位，步：去掉最低位，num=12，長度，長度len=3 第第4步：去掉最低位，步：去掉最低位，num=1，長度，長度len=4 第第5步：去掉最低位，步：去掉最低位，num=0，長度，長度len=5算法中每一步的核心操作是從算法中每一步的核心操作是從num中去

38、掉最低中去掉最低位，長度位，長度len加加1 67 68 假設(shè)假設(shè)num長度不超過長度不超過8，例如，例如num=12345，求，求num的長度的長度 算法算法2：試探能被：試探能被10的幾次方除后商不為的幾次方除后商不為0 第第1步：步： num /107=0 第第2步：步： num /106=0 第第3步：步： num /105=0 第第4步：步： num /104!=0,說明長度為說明長度為4+15算法中每一步的核心操作是試探：算法中每一步的核心操作是試探：num除除10i后商是否后商是否0 69 增加對輸增加對輸入為入為0的的判斷判斷進(jìn)一步細(xì)化進(jìn)一步細(xì)化 70 練習(xí)練習(xí)4：輸入一個不超

39、過：輸入一個不超過8位的正整數(shù)，要求把位的正整數(shù)，要求把這個整數(shù)分解為單個數(shù)字，然后打印出每一個這個整數(shù)分解為單個數(shù)字，然后打印出每一個數(shù)字每一個數(shù)字之間用兩個空格分開）。例數(shù)字每一個數(shù)字之間用兩個空格分開）。例如用戶輸入了如用戶輸入了4200，程序打印結(jié)果為：，程序打印結(jié)果為：4 2 0 0。設(shè)計(jì)算法。設(shè)計(jì)算法。 第第1步：得到步：得到num最高位最高位4并輸出，并輸出，num=200 第第2步：得到步：得到num最高位最高位2并輸出，并輸出，num=0 第第3步：得到步：得到num最高位最高位0并輸出，并輸出，num=9 第第4步：得到步：得到num最高位最高位0并輸出，并輸出，num=0

40、 71 72 練習(xí)練習(xí)5：設(shè)計(jì)算法，判斷一個正整數(shù)是否是回：設(shè)計(jì)算法，判斷一個正整數(shù)是否是回文數(shù)?；匚臄?shù)是指正讀和反讀都一樣的數(shù)。文數(shù)。回文數(shù)是指正讀和反讀都一樣的數(shù)。 算法算法1： 比較第比較第1位和倒數(shù)第位和倒數(shù)第1位位 比較第比較第2位和倒數(shù)第位和倒數(shù)第2位位 算法算法2：反著讀，假設(shè)讀得的數(shù)為：反著讀，假設(shè)讀得的數(shù)為reverseNum，判斷，判斷num和和reverseNum是否相等是否相等 73以求以求a0a1a2a3的逆數(shù)為例，假設(shè)的逆數(shù)為例，假設(shè)reverse實(shí)現(xiàn)逆著實(shí)現(xiàn)逆著讀讀reverse(a3)=a3reverse(a2a3)=a3a2=a3*10 + a2= rever

41、se(a3)*10+a2reverse(a1a2a3)=a3a2a1=a3a2*10 + a1 =reverse(a2a3)*10+ a1reverse(a0a1a2a3)=a3a2a1a0 =a3a2a1*10+a0 =reverse(a1a2a3)*10+a0 74判斷回文數(shù)判斷回文數(shù)-算法算法1 75判斷回文數(shù)判斷回文數(shù)-算法算法2 76#includemain() int num;/存放輸入的整數(shù) int num1; /*循環(huán)中處理的數(shù),每循環(huán)一次,右邊少一位,假設(shè)num為1234,則num1初始值為1234,然后是123,然后是12.;*/ int reverse;/*是用分解出來的

42、數(shù)字組成的新數(shù)*/ int m;/*m:存放每一個分解出來的數(shù)字;*/ printf(請輸入一個小于8位的正整數(shù):); /讀取要判斷的整數(shù) scanf(%d,&num); /*從右到左依次取出各個數(shù)字組裝成一個新的整數(shù)保持到reverse中*/ num1=num; reverse=0; while(num1!=0) m=num1%10; /*取出num1的最低位*/ reverse=reverse*10+m; /*將最低位組裝到reverse中*/ num1=num1/10; /*去掉num1的最低位*/ if (num=reverse) printf(%d 是回文數(shù)n,num); e

43、lse printf(%d 不是回文數(shù)n,num); system(PAUSE); return 0; 77總結(jié)：循環(huán)結(jié)構(gòu)解題總結(jié)：循環(huán)結(jié)構(gòu)解題 很多題目都需要循環(huán)結(jié)構(gòu)進(jìn)行求解。很多題目都需要循環(huán)結(jié)構(gòu)進(jìn)行求解。 當(dāng)一時難以整理出每次循環(huán)迭代所做的事當(dāng)一時難以整理出每次循環(huán)迭代所做的事情時，可以先看一下如果這件事情交給人做的情時，可以先看一下如果這件事情交給人做的話，一步一步是怎么做的。話，一步一步是怎么做的。 在上一步基礎(chǔ)上抽象出循環(huán)結(jié)構(gòu)的四個方面。在上一步基礎(chǔ)上抽象出循環(huán)結(jié)構(gòu)的四個方面。 78總結(jié)：循環(huán)結(jié)構(gòu)解題總結(jié)：循環(huán)結(jié)構(gòu)解題 2和和3一般沒有絕對的先后順序。一般沒有絕對的先后順序。 在分

44、析清楚在分析清楚2和和3后，才分析后，才分析4為什么？）。為什么？）。 一般將一般將1放在最后分析放在最后分析在在4中，要對出現(xiàn)在中，要對出現(xiàn)在2和和3中的某些變量進(jìn)行修改，為中的某些變量進(jìn)行修改，為下次循環(huán)做好準(zhǔn)備，并使得循環(huán)能最終結(jié)束。下次循環(huán)做好準(zhǔn)備，并使得循環(huán)能最終結(jié)束。思考上述四項(xiàng)工作有無先后順序？應(yīng)該是什么順序？思考上述四項(xiàng)工作有無先后順序？應(yīng)該是什么順序？ 79總結(jié)：對一批數(shù)進(jìn)行處理的模式總結(jié)：對一批數(shù)進(jìn)行處理的模式循環(huán)次數(shù)未知循環(huán)次數(shù)未知循環(huán)次數(shù)已知循環(huán)次數(shù)已知 804.1 算法的概念算法的概念4.2 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)4.3 算法的描述方法算法的描述方法4.

45、4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究提綱提綱 81例例4.14 設(shè)計(jì)交通車輛觀測統(tǒng)計(jì)算法。設(shè)計(jì)交通車輛觀測統(tǒng)計(jì)算法。 問題描述：在一個路口設(shè)置一個探測器，通過通問題描述：在一個路口設(shè)置一個探測器，通過通信線路連接到后臺的計(jì)算機(jī)。路口每通過一輛信線路連接到后臺的計(jì)算機(jī)。路口每通過一輛汽車，探測器向計(jì)算機(jī)發(fā)出一個車輛信號汽車，探測器向計(jì)算機(jī)發(fā)出一個車輛信號1，探測器每隔探測器每隔1秒鐘向計(jì)算機(jī)發(fā)出一個時鐘信號秒鐘向計(jì)算機(jī)發(fā)出一個時鐘信號0，觀測結(jié)束向計(jì)算機(jī)發(fā)出結(jié)束信號，觀測結(jié)束向計(jì)算機(jī)發(fā)出結(jié)束信號。 要求在計(jì)算機(jī)上設(shè)計(jì)一個程序，能夠接收探測器要求在計(jì)算機(jī)

46、上設(shè)計(jì)一個程序，能夠接收探測器發(fā)出的信號，統(tǒng)計(jì)出觀測的時長、在觀測時長發(fā)出的信號，統(tǒng)計(jì)出觀測的時長、在觀測時長內(nèi)通過的車輛總數(shù)、以及兩輛車之間最大的時內(nèi)通過的車輛總數(shù)、以及兩輛車之間最大的時間間隔。間間隔。 問題分析：探測器向計(jì)算機(jī)發(fā)出的信號可以認(rèn)為是一個問題分析：探測器向計(jì)算機(jī)發(fā)出的信號可以認(rèn)為是一個任意長的字符序列以任意長的字符序列以#終了），比如：終了），比如：“011011000111101#”，這樣設(shè)計(jì)程序?qū)嶋H上演變?yōu)樽x取，這樣設(shè)計(jì)程序?qū)嶋H上演變?yōu)樽x取該字符序列，然后進(jìn)行相關(guān)的操作。該字符序列，然后進(jìn)行相關(guān)的操作。 1 4.5 算法設(shè)計(jì)實(shí)例研究算法設(shè)計(jì)實(shí)例研究觀測時長：字符序列中觀測

47、時長：字符序列中0的個數(shù)的個數(shù)(6秒秒)；車輛總數(shù)：字符序列中車輛總數(shù)：字符序列中1的個數(shù)的個數(shù)(9輛輛)；兩車間最大時間間隔：兩個兩車間最大時間間隔：兩個1之間的最大連續(xù)之間的最大連續(xù)0的個數(shù)的個數(shù)(3秒秒)；探測器探測器 82 計(jì)算觀測時長（計(jì)算觀測時長（0的個數(shù)和車輛總數(shù)（的個數(shù)和車輛總數(shù)（1的的個數(shù)是容易實(shí)現(xiàn)的，但是如何計(jì)算最大時間個數(shù)是容易實(shí)現(xiàn)的，但是如何計(jì)算最大時間間隔需要進(jìn)一步考慮。在對一個比較復(fù)雜的問間隔需要進(jìn)一步考慮。在對一個比較復(fù)雜的問題進(jìn)行分析時，我們應(yīng)該采用分而治之的方法題進(jìn)行分析時，我們應(yīng)該采用分而治之的方法，將復(fù)雜的問題分解為相對比較簡單的問題，將復(fù)雜的問題分解為相

48、對比較簡單的問題，再針對該較簡單問題進(jìn)行求解。再針對該較簡單問題進(jìn)行求解。 我們首先設(shè)計(jì)算法主體框架。我們首先設(shè)計(jì)算法主體框架?！?000110100011010#0000110100011010#”！留意：！留意：2019年年9月出版的教材假設(shè)接收到的信月出版的教材假設(shè)接收到的信號總是以號總是以1開場，因此算法會有所簡化開場，因此算法會有所簡化 83“0000110100011010#0000110100011010#”signal!=#待細(xì)化待細(xì)化 84 85Level 1層算法設(shè)計(jì)層算法設(shè)計(jì)第0層算法第1層算法 86“0000110100011010#0000110100011010#”

49、 分析：處理時鐘信號分析：處理時鐘信號0 觀測時長觀測時長seconds加加1； 兩種情況。如果此兩種情況。如果此前已接收到車輛信前已接收到車輛信號號1 (如何判斷？如何判斷？)，則間隔時長則間隔時長interval加加1；否則不做任何；否則不做任何處理。處理。 87“0000110100011010#0000110100011010#” 分析：處理車輛信號分析：處理車輛信號1 第一種：第一種： “0000110100011010#”（這是第一個（這是第一個1） 車輛總數(shù)車輛總數(shù)vehicles加加1 第二種：第二種： “0000110100011010#”（不是第一個（不是第一個1，且，且前

50、一個信號也是前一個信號也是1 ） 車輛總數(shù)車輛總數(shù)vehicles加加1 第三種：第三種： “0000110100011010#”（不是第一個（不是第一個1，且，且前一個信號是前一個信號是0 ） 車輛總數(shù)車輛總數(shù)vehicles加加1 處理是否要更新最長時間間隔（處理是否要更新最長時間間隔（ interval：兩車之間：兩車之間的時間間隔，的時間間隔，longest：兩車之間的最長時間間隔）：兩車之間的最長時間間隔） 88“0000110100011010#0000110100011010#” 分析：處理車輛信號分析：處理車輛信號1vehicles vehicles +1；情況情況1：第一個：

51、第一個1 判斷式：判斷式： vehicles =1情況情況2：不是第一個：不是第一個1，且前，且前一個信號也是一個信號也是1 判斷式：判斷式： vehicles1 & interval=0情況情況3：不是第一個：不是第一個1，且前，且前一個信號是一個信號是0 : 判斷式：判斷式： vehicles1 & interval0 處置：處置：1若若intervallongest 那么那么 longest interval。 2） interval0。情況情況1情況情況3情況情況2 89“0000110100011010#”驗(yàn)證算法驗(yàn)證算法【程序演示】 90#includemain()

52、 int vehicles; /記錄車輛信號總數(shù)記錄車輛信號總數(shù) int seconds; /記錄時鐘信號總數(shù)記錄時鐘信號總數(shù) int longest; /記錄最長時間間隔記錄最長時間間隔 int interval; /記錄時間間隔記錄時間間隔 char signal; /存放讀取的信號存放讀取的信號 /* 初始化設(shè)置初始化設(shè)置 */ vehicles=0; seconds=0; longest=0; interval=0; printf(please input signal: n); scanf(%c,&signal);/* 讀入第一個信號讀入第一個信號 */ 91 /* 循環(huán)結(jié)構(gòu)

53、處理輸入信號的字符序列循環(huán)結(jié)構(gòu)處理輸入信號的字符序列,邊讀取邊處理邊讀取邊處理 */ while (signal!=#) if (signal=1) /* 處理車輛信號處理車輛信號*/ vehicles=vehicles+1; if (vehicles1 & interval0) if (intervallongest) longest=interval; interval=0; else/* 處理時鐘信號處理時鐘信號*/ seconds=seconds+1; if (vehicles0) interval=interval+1; scanf(%c,&signal); 92/*

54、 輸出結(jié)果輸出結(jié)果 */ printf(%d vehicles passed in %d secondsn,vehicles,seconds); printf(the longest gap was %d secondsn,longest); system(PAUSE); return 0; 93 練習(xí)：將一個由數(shù)字字符組成的字符串轉(zhuǎn)換為練習(xí)：將一個由數(shù)字字符組成的字符串轉(zhuǎn)換為整數(shù)或者小數(shù)并輸出。如：整數(shù)或者小數(shù)并輸出。如：輸入輸入:134.567# 輸出輸出:134.567 94 #includemain() char ch; int num; /存放小數(shù)點(diǎn)前面的字符轉(zhuǎn)換后得到的整數(shù)存放小數(shù)

55、點(diǎn)前面的字符轉(zhuǎn)換后得到的整數(shù) float fnum; /存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的浮點(diǎn)數(shù)存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的浮點(diǎn)數(shù) int n; /存放字符對應(yīng)的數(shù)字存放字符對應(yīng)的數(shù)字 int p; / 存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的數(shù)字對應(yīng)的基數(shù)存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的數(shù)字對應(yīng)的基數(shù)1/p。小數(shù)點(diǎn)后第一位數(shù)的。小數(shù)點(diǎn)后第一位數(shù)的基數(shù)是基數(shù)是1/10 int flag;/用于表示輸入的字符中是否有小數(shù)點(diǎn)。若有，則用于表示輸入的字符中是否有小數(shù)點(diǎn)。若有，則flag值為值為1；否則為；否則為0 num = 0; fnum = 0; p = 10; flag = 0; printf(pl

56、ease input the string:); 算法算法1：讀情況對字符進(jìn)行處理：讀情況對字符進(jìn)行處理 95 scanf(%c,&ch); while( ch != #) if (ch=.) flag = 1;/flag為為1，表示輸入了小數(shù)點(diǎn)，表示輸入了小數(shù)點(diǎn) else /處理小數(shù)點(diǎn)之前的字符處理小數(shù)點(diǎn)之前的字符 n = ch - 0; if (flag = 0)/若輸入的是小數(shù)點(diǎn)之前的數(shù)若輸入的是小數(shù)點(diǎn)之前的數(shù) num = num * 10 + n; else/處理小數(shù)點(diǎn)之后的字符處理小數(shù)點(diǎn)之后的字符 fnum = fnum + (float)n / p; /必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換

57、，否則必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換，否則n/p結(jié)果為結(jié)果為0 p = p * 10; scanf(%c,&ch); 96 if (flag = 0) printf(the result is:%dn,num); else printf(the result is:%fn,num+fnum); system(pause); return 0; 97 #includemain() char ch; int num; float fnum; int n; int p; printf(please input the string:); /處理整數(shù)部分 num = 0; scanf(%c,&c

58、h); while(ch != . & ch != #) n = ch - 0; num = num * 10 + n; scanf(%c,&ch); 算法算法2：先循環(huán)處理小數(shù)點(diǎn)前面：先循環(huán)處理小數(shù)點(diǎn)前面的字符，再循環(huán)處理小數(shù)點(diǎn)的字符，再循環(huán)處理小數(shù)點(diǎn)后面的字符后面的字符 98 if (ch=.) /處理小數(shù)部分處理小數(shù)部分 p = 10; scanf(%c,&ch); while(ch != #) n = ch - 0; fnum = fnum + (float)n / p; /必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換，否則必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換，否則n/p結(jié)果為結(jié)果為0 scanf(%

59、c,&ch); p = p * 10; if (fnum 0) printf(the result is:%dn,num); else printf(the result is:%fn,num+fnum); system(pause); return 0; 99迭代算法迭代算法迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對一組指令運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對一組指令或一定步驟進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令或這些或一定步驟進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令或這些步

60、驟時，都從變量的原值推出它的一個新值。步驟時，都從變量的原值推出它的一個新值。利用迭代算法解決問題，需要做好以下三個方面的工作利用迭代算法解決問題，需要做好以下三個方面的工作 確定迭代變量確定迭代變量ai。在可以用迭代算法解決的問題中，至少存。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。就是迭代變量。 建立迭代關(guān)系式，即建立迭代關(guān)系式，即aif(ai-1)對迭代過程進(jìn)行控制對迭代過程進(jìn)行控制 。迭代過程的控制通常可分為兩種情況。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計(jì)算出來；另一：一種是所需的迭代次數(shù)是個確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種