結構化程序相關設計講義

結構化程序相關設計講義2第三章結構化程序設計與基本算法3.1算法及其表示3.2結構化程序設計3.3順序結構3.4選擇結構3.5循環(huán)結構3.6流程轉移控制語句3.733.1算法及其表示N.Wirth提出：數(shù)據(jù)結構+算法=程序算法：為解決一個具體問題而采取的確定的有限的操作步驟，這里僅指計算機能執(zhí)行的算法算法特性：有窮性確定性

有效性

沒有輸入或有多個輸入

有一個或多個輸出

算法分類：數(shù)值算法：解決的是求數(shù)值解的問題，例如用輾轉相除法求兩個數(shù)的最大公約數(shù)等。非數(shù)值算法：主要用于解決需要用分析推理、邏輯推理才能解決的問題，例如人工智能中的許多問題，查找、分類等問題。43.1算法及其表示算法的表示方式自然語言傳統(tǒng)的流程圖

N-S結構化流程圖

偽代碼

開始/準備過程/處理選擇/決策手動輸入文檔顯示/輸出終止離頁連接53.2結構化程序設計已經(jīng)證明，任何程序均可只用順序結構、選擇結構、循環(huán)結構這三種結構綜合描述。只用這三種結構編制的程序，叫結構化程序。程序應符合結構化規(guī)則。采用順序、選擇和循環(huán)三種基本結構作為程序設計的基本單元只有一個入口；只有一個出口；無死語句，即不存在永遠都執(zhí)行不到的語句；無死循環(huán)，即不存在永遠都執(zhí)行不完的循環(huán)，但也有例外。采用“自頂向下、逐步求精”和模塊化的方法進行結構化程序設計E.W.Dijkstra，生于1930年，卒于2002年8月6日63.2結構化程序設計—流程表示BABA條件P順序結構選擇結構73.2結構化程序設計—流程表示條件PA真假假條件PA假真當型循環(huán)直到型循環(huán)83.3順序結構順序結構：按照語句出現(xiàn)的先后順序依次執(zhí)行。一般：表達式；例如：

i++;sum=a+b; cout<<a<<b<<endl;特例：；(空語句)

作用:當程序中某個位置在語法上需要一條語句，而在語義上又不要求執(zhí)行任何動作時，可放上一條空語句。一般適用于在循環(huán)語句中做空循環(huán)體：for(m=0;m<1000;m++);93.3順序結構復合語句：

{ [變量定義]

語句組

}作用：當程序中某個位置在語法上只允許一條語句，而在語義上要執(zhí)行多條語句才能完成某個操作時，需要使用復合語句。變量僅在定義它的復合語句內(nèi)有效一般適用于選擇、循環(huán)語句中的內(nèi)嵌語句。也有時為了清晰，特意將某段程序中{}括起來。103.4選擇結構選擇結構：根據(jù)條件的值來判斷程序的流向。C/C++中，提供兩類選擇控制語句:if語句，實現(xiàn)n分支，要求n個表達式;switch語句，實現(xiàn)多分支；只用1個表達式。113.4選擇結構3.2.1if語句if語句的三種形式:

形式1：

if(表達式)語句作用：當表達式為真(非0)時，執(zhí)行表達式后面的語句,否則繞過該語句，而執(zhí)行其后面的語句。例3.1已知兩個數(shù)x和y，比較它們的大小，使得x大于y。思考：如何將一瓶油與一瓶酒互相換瓶？

需借助于一個空瓶子內(nèi)存中的兩個單元也可以看成放著一瓶油與一瓶酒，要交換其中放的內(nèi)容，同樣需借助于一個空的內(nèi)存單元。這是由內(nèi)存”取之不盡，一沖就走”的物點決定的。123.4選擇結構于是，有if(x<y){t=x;x=y;y=t;} cout<<x<<y;#include"iostream.h"voidmain(){intx,y,t;cout<<"輸入xy"<<endl;cin>>x>>y;if(x<y){t=x;x=y;y=t;}//x與y交換

cout<<x<<">"<<y<<endl;}完整的程序如右：133.4選擇結構形式2：

if(表達式)

語句1else

語句2

作用：當表達式為真時，執(zhí)行語句1，否則執(zhí)行語句2。例3.2計算分段函數(shù)：143.4選擇結構實現(xiàn)此題可采用雙分支結構，也可采用單分支結構。if(x)y=sin(x)+sqrt(x*x+1);elsey=cos(x)－x*x+3*x;y=cos(x)－x*x+3*x;if(x)y=sin(x)+sqrt(x*x+1);思考：若將右邊的兩個語句上下交換一下，還能實現(xiàn)上例的要求嗎？

不能153.4選擇結構形式3：

if(表達式1)

語句1 elseif(表達式2)

語句2 ┆ elseif(表達式n)

語句n else

語句n+1作用：當表達式1的值為true時，執(zhí)行語句1；否則判斷當表達式2的值為true時執(zhí)行語句2；依此類推，若表達式的值都為false，則執(zhí)行語句n+1。163.4選擇結構例3.3已知成績mark，要求顯示對應五級制的評定，評定條件：if(mark>=90)cout<<"優(yōu)"; elseif(80<=mark&&mark<90)cout<<"良"; elseif(60<=mark&&mark<70)cout<<"及格"; elseif(70<=mark&&mark<80)cout<<"中"; else cout<<"不及格"; if(mark>=60)cout<<"及格";elseif(mark>=70)cout<<"中";elseif(mark>=80)cout<<"良";elseif(mark>=90)cout<<"優(yōu)";elsecout<<"不及格";√×注意：①不管有幾個分支，程序執(zhí)行一個分支后，其余分支不再執(zhí)行。②elseif不能寫成elseif。③當多分支中有多個表達式同時滿足，則只執(zhí)行第一個與之匹配的語句。173.4選擇結構if語句的嵌套形式

if語句的嵌套是指if或else后面的語句本身又是一個if語句。如：if(表達式1) if(表達式11)

語句11else

語句12else

語句2if(表達式1)if(表達式2)

語句1else

語句2

如何使之與第一個if配對？注意：為了增強程序的可讀性，建議采用鋸齒型的書寫形式。

else始終與它上面的最近的if語句配對，而這個if語句又沒有其它的else與之匹配。183.4選擇結構例3.4已知x，y，z三個數(shù)，使得x>y>z?？捎靡粋€IF語句和一個嵌套的IF語句實現(xiàn)。if(x<y){t=x;x=y;y=t;}if(y<z){t=y;y=z;z=t; if(x<y) {t=x;x=y;y=t;}}193.4選擇結構現(xiàn)場編程：體型判斷。按“體指數(shù)”對肥胖程度進行劃分，體指數(shù)t=體重w/(身高h)2

（w單位為公斤，h單位為米）當t<18時，為低體重；當t介于18和25之間時，為正常體重；當t介于25和27之間時，為超重體重；當t>=27時，為肥胖。編程從鍵盤輸入你的身高h和體重w，根據(jù)給定公式計算體指數(shù)t，然后判斷你的體重屬于何種類型。提示：可用3種方法編程中的一種算法1：用不帶else子句的if語句編程算法2：用在if子句中嵌入if語句的形式編程算法3：用在else子句中嵌入if語句的形式編程

(10分鐘，請自告奮勇)203.4選擇結構

3.2.2switch語句形式：switch(表達式）{case常量表達式1：語句組1；

[break；]case常量表達式2：語句組2；

[break；]┆case常量表達式n：語句組n；

[break；][default：語句組n+1]}執(zhí)行順序：當表達式的值與某個常量表達式的值相等時，則執(zhí)行該常量表達式后面相應的語句，若使用了break,則執(zhí)行完該語句后便退出switch語句；否則，還要依次執(zhí)行其后面的各條語句。若找不到相匹配的常量表達式，則執(zhí)行default后面的語句。必須為整型或字符型

213.4選擇結構現(xiàn)場編程：設計一個簡單的計算器程序，要求根據(jù)用戶從鍵盤輸入的表達式：操作數(shù)1運算符op操作數(shù)2

然后，計算表達式的值，指定的運算符為加（+）、減（-）、乘（*）、除（/）提示：用switch語句。223.4選擇結構 2a+1(1<=a<2)【例3.5】用switch結構求分段函數(shù)b=a2-3(2<=a<4) a其它正確：switch((int)a){case1:b=2*a+1;break;case2:case3:b=a*a-3;break;default:b=a;}錯誤：switch((int)a){casea>=1&&a<2:……casea>=2&&a<4:.…..default:b=a;}共用同一個語句組

思考：若省去break語句，情況會怎樣？

233.5循環(huán)結構C語言提供了三種循環(huán)語句，流程圖如下：

while do-while forwhile(表達式)

語句do語句while(表達式);for(表達式1;表達式2;表達式3)語句243.5循環(huán)結構例3.6/3.8用上述三種循環(huán)語句求while語句:n=1;s=0;while(n<=100){s=s+n;n=n+1;}n=1;s=0;do{s=s+n;n=n+1;}while(n<=100);do-while語句:for(n=1,s=0;n<=100;n++)s=s+n;for語句:253.5循環(huán)結構例3.7求下列級數(shù)的前m項和,要求其誤差小于0.00001分析:級數(shù)的通項為xm/m!,

第i項ti與第i-1項ti-1之間存在如下關系：

ti=ti-1*x/iinti(1);floatt(1),e(0);while(t>1e-5){e+=t;t/=i;i++;}inti(1);floatt(1),e(0);for(;t>1e-5;){e+=t;t/=i;i++;}for(i=1,t=1,e=0;t>1e-5;e+=t,t/=i,i++);分號不能省略空語句263.5循環(huán)結構例3.9將可打印的ASCII碼制成表格輸出，使每個字符與它的編碼對應起來，每行打印7個字符。看程序，思考：你認為完成該例，關鍵在什么地方？for通常有一個循環(huán)變量控制循環(huán)的次數(shù)，不要在循環(huán)體內(nèi)改變這個變量273.5循環(huán)結構現(xiàn)場編程----猜數(shù)游戲：先由計算機“想”一個數(shù)請人猜，如果人猜對了，則計算機給出提示：“Right!”，否則提示：“Wrong!”，并告訴人所猜的數(shù)是大還是小。現(xiàn)場編程----先由計算機“想”一個1到100之間的數(shù)請人猜，如果人猜對了，則結束游戲，否則計算機給出提示，告訴人所猜的數(shù)是太大還是太小，直到人猜對為止。計算機記錄人猜的次數(shù)，以此來反映猜數(shù)者“猜”的水平。283.5循環(huán)結構猜數(shù)游戲用到的庫函數(shù)隨機函數(shù)rand()#include<stdlib.h>

產(chǎn)生[0,32767]之間隨機數(shù).

隨機函數(shù)srand為函數(shù)rand()設置隨機數(shù)種子實現(xiàn)對函數(shù)rand所產(chǎn)生的偽隨機數(shù)的“隨機化”,使用計算機讀取其時鐘值并把該值自動設置為隨機數(shù)種子，產(chǎn)生[0,100]之間的隨機數(shù)C中函數(shù)time()返回以秒計算的當前時間值，該值被轉換為無符號整數(shù)并用作隨機數(shù)發(fā)生器的種子#include<time.h>srand(time(NULL));magic=rand()%101+0;

293.5循環(huán)結構#include"iostream.h"#include"stdlib.h"voidmain(){ inti,a; for(i=0;i<10;i++) { a=rand()%101; cout<<a<<''; }}問題：每一次運行程序，所得到的隨機數(shù)序列都一樣嗎？一樣這是因為初始種子是默認的，要改變必須使每次運行的初始種子不一樣，這就要用到srand函數(shù)了，想一想如何修改程序？303.5循環(huán)結構循環(huán)的嵌套：循環(huán)體內(nèi)包含另一個完整的循環(huán)結構。三種循環(huán)語句皆可以相互嵌套。例3.10打印九九乘法表

313.5循環(huán)結構#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){ for(intj=1;j<=9;j++) cout<<i<<"×"<<j<<"="<<i*j<<'\t'; cout<<endl;}}程序：思考：打印上三角或下三角程序如何改動？323.5循環(huán)結構#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){for(intk=1;k<=i-1;k++)cout<<'\t';for(intj=i;j<=9;j++)cout<<i<<"×"<<j<<"="<<i*j<<'\t'; cout<<endl;}}#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){for(intj=1;j<=i;j++)cout<<i<<"×"<<j<<"="<<i*j<<'\t';cout<<endl;}}打印下三角的程序打印上三角的程序333.5循環(huán)結構使用嵌套的循環(huán)體時，應注意以下問題：在嵌套的各層循環(huán)體中，使用復合語句（即用一對大花括號將循環(huán)體語句括起來）保證邏輯上的正確性

內(nèi)層和外層循環(huán)控制變量不應同名，以免造成混亂

嵌套的循環(huán)最好采用右縮進格式書寫，以保證層次的清晰性

循環(huán)嵌套不能交叉，即在一個循環(huán)體內(nèi)必須完整的包含著另一個循環(huán)

合法的嵌套循環(huán)343.5循環(huán)結構現(xiàn)場編程：國王的許諾。相傳國際象棋是古印度舍罕王的宰相達依爾發(fā)明的。舍罕王十分喜歡象棋，決定讓宰相自己選擇何種賞賜。這位聰明的宰相指著8×8共64格的象棋盤說：陛下，請您賞給我一些麥子吧，就在棋盤的第一個格子中放1粒，第2格中放2粒，第3格放4粒，以后每一格都比前一格增加一倍，依此放完棋盤上的64個格子，我就感恩不盡了。舍罕王讓人扛來一袋麥子，他要兌現(xiàn)他的許諾。

國王能兌現(xiàn)他的許諾嗎？試編程計算舍罕王共要多少麥子賞賜他的宰相，這些麥子合多少立方米？（已知1立方米麥子約1.42e8粒）

總粒數(shù)為：sum=1+2+22+23+…+263

353.5循環(huán)結構死循環(huán)永遠不會退出的循環(huán)為死循環(huán)for(;;){}while(1){}do{}while(1)一般情況下，要極力避免死循環(huán)絕大多數(shù)程序不需要死循環(huán)。如果出現(xiàn)，往往都是bug時間過長的循環(huán)會造成“假死”效果，也要考慮解決363.5循環(huán)結構選擇三種循環(huán)的一般原則：如果循環(huán)次數(shù)已知，用for如果循環(huán)次數(shù)未知，用while如果循環(huán)體至少要執(zhí)行一次，用do-while

這只是“一般”原則，不是“原則”373.6流程轉移控制語句—break&continueBreak在switch語句中出現(xiàn)過，保證多分支情況的正確執(zhí)行；break和continue還對for、while、do-while循環(huán)進行內(nèi)部手術：break，退出循環(huán)continue，中斷此次循環(huán)體的執(zhí)行，開始下一次

少用為妙假假真真break表達式1表達式2循環(huán)語句的下一條語句循環(huán)語句的下一條語句假假真真contiue表達式1表達式2continue383.6流程轉移控制語句—break&continue分析下面兩段代碼如何執(zhí)行的。for(m=20;m>0;m--){if(m%6==0)break;cout<<m<<"";}for(m=20;m>0;m--){if(m%6==0)continue;cout<<m<<"";}393.6流程轉移控制語句—gotogoto與標號標號舉例error:goto舉例gotoerror;一般形式

goto語句標號;

……

語句標號：……或語句標號：……

……goto語句標號;糟糕的goto：START_LOOP:if(fStatusOk){if(fDataAvaiable){i=10;gotoMID_LOOP;}else{gotoEND_LOOP;}}else{for(i=0;i<100;i++){MID_LOOP://lotsofcodehere……}gotoSTART_LOOP;}END_LOOP:Dijkstra早在1968年就指出：“Gotoconsideredharmful”

，“Ibecameconvincedthatthegotostatementshouldbeabolishedfromall"higherlevel"programminglanguages.”“Thegotostatement…istoomuchaninvitationtomakeamessofone'sprogram.”現(xiàn)代觀點認為：混亂根源不在goto，而在標號；任何程序都可以不用goto就實現(xiàn)其功能；但在某些情況下，使用goto可以讓程序更清晰使用原則：使用之后，程序仍然是單入口，單出口不要使用一個以上的標號不要用goto往回跳，要向下跳不要讓goto制造出永遠不會被執(zhí)行的代碼403.6流程轉移控制語句exit(0)作用是終止整個程序的執(zhí)行，強制返回操作系統(tǒng),調(diào)用該函數(shù)需要嵌入頭文件stdlib.h。此函數(shù)為出現(xiàn)異常，結束整個程序的運行提供了支持。例3.11分別用if和goto、for語句實現(xiàn)求和。

記住要寫上標號。413.7應用舉例1.求最大值（或最小值）例3.12從鍵盤輸入一組數(shù)，求這組數(shù)中的最大值。cin>>m;max=m;//第一個數(shù)假設為最大數(shù)

while(cin>>m,m!=0)if(m>max)max=m;max=0;//設一個較小的數(shù)為最大值的初值

for(inti=0;i<10;i++){cin>>m;if(m>max)max=m;}以輸入0作為結束，輸入數(shù)的個數(shù)未知

輸入數(shù)的個數(shù)已知

423.7應用舉例2求最大公約數(shù)例3.13輸入兩自然數(shù)m、n，求最大公約數(shù)。方法1:歐幾里德的輾轉相除法

(1)對于已知兩數(shù)m、n，使m>n；

(2)m除以n得余數(shù)r；

(3)若r=0,則n為最大公約數(shù)，算法結束；否則繼續(xù)進行下一步；

(4)則令nm，rn,轉第2步繼續(xù)相除得新的r。方法2:輾轉相減法先用兩個數(shù)相減，判別差是否為0，用小數(shù)和差組成新的數(shù)對再相減，直到差為0時為止。最后那一組相同的數(shù)對即為最大公約數(shù)。43#include"iostream.h"voidmain() { intm,n,t,r; cout<<"請輸入mn:"<<endl; cin>>m>>n; if(m<n){t=m;m=n;n=t;} while((r=m%n)!=0) { m=n;n=r; }cout<<"最大公約數(shù)為"<<m<<endl;//退出循環(huán)時m為最大公約數(shù)

}3.7應用舉例#include"iostream.h"voidmain() { intm,n; cout<<"請輸入mn:"<<endl; cin>>m>>n;

while(m-n!=0) if(m>n)m-=n;elsen-=m;cout<<"最大公約數(shù)為"<<m<<endl;//退出循環(huán)時m為最大公約數(shù)

}方法1方法2不要這句行嗎？443.7應用舉例3求素數(shù)例3.14求2~100之間的素數(shù)。素數(shù)(質(zhì)數(shù))----就是除1和它本身以外設有其他的約數(shù)的整數(shù)。判別某數(shù)為質(zhì)數(shù)的最簡單方法就是用j=2,3,…,m-1逐個判別m能否被j整除，若都不能被整除，m是素數(shù)。另一種判別方法是用j=2,3,…,sqrt(m)逐個判別m能否被j整除，若都不能被整除，m是素數(shù)。顯然，第一種方法比第二種循環(huán)要多一些。453.7應用舉例#include"iostream.h"voidmain(){intm,i,countm(0);booltag;for(m=2;m<=100;m++) {tag=false;//tag初值為false for(i=2;i<=m-1;i++) if(m%i==0)tag=true;//m被整除，設置為true //出了內(nèi)循環(huán)，tag的值若為false，說明m沒有被i整除過m是素數(shù)

if(tag==false) //等價于if(!tag) {cout<<m<<'\t'; countm++; if(countm%8==0)cout<<endl; } }}第一種方法463.7應用舉例#include<stdio.h>#include<math.h>voidmain(){ intm,i,k; printf("Pleaseenteranumber:"); scanf("%d",&m); k=sqrt(m); for(i=2;i<=k;i++){ if(m%i==0)break; } if(i>k) printf("Yes!\n"); else printf("No!\n"); printf("Programisover!\n");}進一步，輸入一個數(shù)，判斷其是否是素數(shù)。473.7應用舉例4窮舉法----測試所有的情況例3.15a馬克思手稿中有一道趣味數(shù)學題：有30個人，其中有男人、女人和小孩，在一家飯館里吃飯共花了50先令，每個男人各花3先令，每個女人各花2先令，每個小孩各花1先令，問男人、女人和小孩各有幾人？對這種不定方程組，可采用窮舉法。提示，本題就是解方程組483.7應用舉例#include<stdio.h>main(){intx,y,z;printf("Man\tWomen\tChildern\n");for(x=0;x<=30;x++)for(y=0;y<=30;y++)for(z=0;z<=30;z++)if(x+y+z==30&&3*x+2*y+z==50)printf("%3d\t%5d\t%8d\n",x,y,z);}三重循環(huán)窮舉493.7應用舉例#include<stdio.h>

main(){intx,y,z;printf("Man\tWomen\tChildern\n");for(x=0;x<=16;x++)for(y=0;y<=25;y++){z=30–