第7章結(jié)構(gòu)化算法的實(shí)現(xiàn)7.1

基本控制結(jié)構(gòu)的C++實(shí)現(xiàn)7.2

子算法設(shè)計(jì)與C++實(shí)現(xiàn)7.3

遞歸與迭代學(xué)習(xí)目的：

① 理解算法控制結(jié)構(gòu)與C++控制語(yǔ)句之間的關(guān)系；

② 能夠根據(jù)結(jié)構(gòu)化算法的PAD圖編制C++程序； ③ 深入理解遞歸與迭代的原理與過程； ④ 熟練應(yīng)用遞歸技術(shù)解決問題。7.1基本控制結(jié)構(gòu)的C++實(shí)現(xiàn)7.1.1

順序結(jié)構(gòu)的C++實(shí)現(xiàn)7.1.2

分支結(jié)構(gòu)的C++實(shí)現(xiàn)7.1.3

循環(huán)結(jié)構(gòu)的C++實(shí)現(xiàn)7.1.4 復(fù)雜結(jié)構(gòu)C++實(shí)現(xiàn)示例理想的算法設(shè)計(jì)應(yīng)是語(yǔ)言無(wú)關(guān)的，可使用任何語(yǔ)言實(shí)現(xiàn)它，但是這將帶來(lái)兩個(gè)問題：

其一，常用算法描述工具的描述能力有限，有些問題采用具體程序 語(yǔ)言所提供的語(yǔ)法對(duì)算法進(jìn)行描述效率會(huì)更高、結(jié)構(gòu)更簡(jiǎn)單； 其二，由于算法與語(yǔ)言的脫離，在使用具體語(yǔ)言實(shí)現(xiàn)算法時(shí)，程序 與算法描述之間并不總是一一對(duì)應(yīng)的，經(jīng)常需要對(duì)算法進(jìn)行適當(dāng)調(diào) 整，以利于實(shí)現(xiàn)。在結(jié)構(gòu)化程序設(shè)計(jì)與實(shí)現(xiàn)時(shí)巧妙地應(yīng)用高級(jí)語(yǔ)言所提供的各種便利的語(yǔ)法，能起到事半功倍的效果。7.1.1

順序結(jié)構(gòu)的C++實(shí)現(xiàn)如果將程序中的每條分支語(yǔ)句和循環(huán)語(yǔ)句等復(fù)雜語(yǔ)句作為一個(gè)整體（一條復(fù)雜的語(yǔ)句），那么C++程序中物理上順序排列的語(yǔ)句（除goto外）的執(zhí)行順序與其排列的前后順序相同，它們之間構(gòu)成了順序結(jié)構(gòu)，因此可以將C++的所有語(yǔ)法用于順序結(jié)構(gòu)算法的實(shí)現(xiàn)。#include"iostream.h"voidmain(){doubler,Peri_bottom,S_bottom,S_side,V,h;

cout<<"Pleaseentertheradius!r=";

cin>>r;

cout<<"Pleaseentertheheight!h=";

cin>>h;

Peri_bottom=6.28*r;

S_side=Peri_bottom*h;

S_bottom=9.86*r;V=S_bottom*h;

cout<<"Thelateralareais"<<S_side<<endl;

cout<<"Thevolumeis"<<V<<endl;}7.1.2

分支結(jié)構(gòu)的C++實(shí)現(xiàn)算法的分支結(jié)構(gòu)在C++中可以采用if語(yǔ)句或switch語(yǔ)句來(lái)實(shí)現(xiàn)，其中switch語(yǔ)句主要用于實(shí)現(xiàn)多分支結(jié)構(gòu)，這兩種語(yǔ)句的結(jié)構(gòu)與算法的分支結(jié)構(gòu)具有很好的對(duì)應(yīng)關(guān)系。[例7.1][例2.4]中算法的C++實(shí)現(xiàn)。#include"iostream.h"#include"math.h"voidmain(){doublea,b,c,x1,x2,q;

cout<<"請(qǐng)輸入一元二次方程的系數(shù)：\na=";

cin>>a;

cout<<"b=";

cin>>b;

cout<<"c=";

cin>>c;

if(a==0)

cout<<"錯(cuò)誤輸入"<<endl;else{q=b*b-4*a*c;

if(q<0)

cout<<"沒有實(shí)數(shù)解"<<endl;else{//下面兩行為減少運(yùn)算次數(shù)

q=sqrt(q);a*=2;x1=(-b+q)/a;x2=(-b-q)/a;

cout<<"第一個(gè)根為"<<x1<<endl;

cout<<"第二個(gè)根為"<<x2<<endl;}}}[例7.2][例2.6]中算法的C++實(shí)現(xiàn)#include"iostream.h"voidmain(){

intMonth;

cout<<"請(qǐng)輸入月份序號(hào)";

cin>>Month;

if(Month<0||Month>12)

cout<<"錯(cuò)誤月份序號(hào)"<<endl;else{switch(Month-1){case0:

cout<<"January"<<endl;break;case1:

cout<<"February"<<endl;break;case2:

cout<<"March"<<endl;break;case3:

cout<<"April"<<endl;break;case4:

cout<<"May"<<endl;break;//其他月份此處忽略

}}}7.1.3

循環(huán)結(jié)構(gòu)的C++實(shí)現(xiàn)循環(huán)結(jié)構(gòu)在C++程序中有多種實(shí)現(xiàn)方式，較好的風(fēng)格是直到型循環(huán)使用do語(yǔ)句、當(dāng)型循環(huán)使用while語(yǔ)句、步長(zhǎng)型采用for語(yǔ)句。#include"iostream.h"voidmain(){

intn=0,s=0,temp=0;

cout<<"Pleaseenteradigital";

cin>>n;

while(n!=0){temp=n/10;s=s*10+(n-temp*10);n=temp;}

cout<<s<<endl;}#include"iostream.h"voidmain(){

intn=0,s=0,temp=0;

cout<<"Pleaseenteradigital";

cin>>n;for(;n!=0;temp=n/10,s=s*10+(n-temp*10),n=temp);

cout<<s<<endl;}7.1.4 復(fù)雜結(jié)構(gòu)C++實(shí)現(xiàn)示例...do{

if(con2)

{

if(con4)

block3

else

block4

}

else

{

if(con3)

block1

else

block2

}}while(con1)block5CBA7.1.4 復(fù)雜結(jié)構(gòu)C++實(shí)現(xiàn)示例[例7.3]求任意n個(gè)整數(shù)中的最大者與最小者。算法輸入： 依次輸入n個(gè)整數(shù)。算法輸出： 上述整數(shù)中的最大、最小值。數(shù)據(jù)結(jié)構(gòu)：

n為整數(shù)，意義與題同。Max和Min均為整數(shù)，是已經(jīng)輸入數(shù) 據(jù)中的 最大和最小數(shù)。x為每次輸入的整數(shù)。i為整數(shù)。問題分析： 每循環(huán)一次輸入一個(gè)整數(shù)，將之與以前的最大數(shù)Max和最小 數(shù)Min對(duì) 比后，根據(jù)比較結(jié)果更新Max和Min的值。算法結(jié)束Max←xMin←xi←i+1n，xMax，Min算法開始直到i=nMax<xMin>xMax←xMin←xxvoidmain(){

intn=0,x=0,i=2;

cout<<"InpoutNplease\n";

cin>>n;

cout<<"InpoutXplease\n";

cin>>x;

intMax=x,Min=x;

while(i<=n){

cout<<"InpoutXplease\n";

cin>>x;

if(Max<=x)Max=x;elseif(Min>x)Min=x;i++;}

cout<<"Max="<<Max<<endl;

cout<<"Min="<<Min<<endl;}7.2子算法設(shè)計(jì)與C++實(shí)現(xiàn)7.2.1

參數(shù)為普通類型的子算法7.2.2

參數(shù)為指針的子算法7.2.3

參數(shù)為引用的子算法7.2.4 子算法設(shè)計(jì)與C++實(shí)現(xiàn)示例對(duì)于出現(xiàn)在算法中不同部分的一組相同操作，為減少算法描述工作量，同時(shí)使算法更加簡(jiǎn)潔易讀，通常的做法是將這個(gè)重復(fù)部分提取出來(lái)作為一個(gè)獨(dú)立模塊并加以命名，在需要的地方通過模塊名及參數(shù)等信息調(diào)用這個(gè)模塊，而不是反復(fù)重復(fù)相同的描述，這樣的模塊被稱為子算法（或函數(shù)）。PAD圖表示方式如下：進(jìn)入返回具體操作返回值子算法名（子算法參數(shù)表）7.2.1

參數(shù)為普通類型的子算法子算法的參數(shù)為基本類型變量，調(diào)用子算法時(shí)的調(diào)用參數(shù)（實(shí)在參數(shù)）與子算法輸入?yún)?shù)（形式參數(shù)）的形實(shí)結(jié)合采用傳值方式，對(duì)應(yīng)于C++函數(shù)定義及其調(diào)用的一般形式。算法輸入：子算法入口參數(shù)為正整數(shù)n和i。算法輸出：返回上述整數(shù)組成的的值。數(shù)據(jù)結(jié)構(gòu)：

k為整型變量，含義見下述公式，該量同時(shí)用作循環(huán)變量。問題分析：所給公式中有多個(gè)階乘運(yùn)算，時(shí)間代價(jià)較高。同時(shí)，階乘運(yùn)算的結(jié)果往往很大，比如10的階乘就已達(dá)3628800，因此當(dāng)n稍大就可能造成存儲(chǔ)溢出?？紤]到分子和分母之間存在公共因子，因此首先對(duì)所給公式化簡(jiǎn)如下：[例7.4]編寫算法求變形后公式的優(yōu)點(diǎn)在于：……7.2.1

參數(shù)為普通類型的子算法算法描述及程序?qū)崿F(xiàn)如下：int

GetCombination(intn,inti)進(jìn)入返回nTemp←1k←1；k<=i；k←k+1nTemp←nTemp*(n-i+k)/kGetCombination←nTemplongGetCombination(intn,inti){longnTemp=1;

for(intk=1;k<=i;k++){

nTemp=nTemp*(n-i+k)/k;}returnnTemp;}7.2.2

參數(shù)為指針的子算法這類子算法的參數(shù)可以為基本類型指針、數(shù)組、函數(shù)指針等。[例7.5] 使用子算法求n個(gè)正整數(shù)中的最小數(shù)，并求兩組5個(gè)整數(shù)中 最小數(shù)之和。算法輸入： 子算法的入口參數(shù)為一維數(shù)組array[]及其所含元素?cái)?shù)。算法輸出： 子算法返回?cái)?shù)組中的最小值。數(shù)據(jù)結(jié)構(gòu)： data[]為整型數(shù)組。n為所含元素?cái)?shù)；nTemp、nTemp1、 nTemp2為整型變量存儲(chǔ)中間結(jié)果。算法分析： 因?yàn)樾枰獌纱螐囊粋€(gè)數(shù)組中提取最小值，因此將這部分功 能獨(dú)立作為一個(gè)模塊，形成一個(gè)子算法，以便在需要時(shí)調(diào) 用。這個(gè)功能比較簡(jiǎn)單，按照一般思路得到下面子算法及 調(diào)用子算法的主算法。7.2.2

參數(shù)為指針的子算法這類子算法的參數(shù)可以為基本類型指針、數(shù)組、函數(shù)指針等。i←1；i<=n；i←i+1進(jìn)入返回GetMin←nTempnTemp←data[0]nTemp>data[i]nTemp←data[i]int

GetMin(array[],nNum)#include"iostream.h"int

GetMin(intarray[],int

nNum){

int

nTemp=array[0];

for(inti=0;i<nNum;i++){

if(nTemp>array[i])

nTemp=array[i];}returnnTemp;}voidmain(){

intdata1[5]={8,12,4,3,6};

intdata2[5]={2,7,8,2,1};

intnTemp1=GetMin(data1,5);

intnTemp2=GetMin(data2,5);

cout<<nTemp1+nTemp2<<endl;}7.2.3

參數(shù)為引用的子算法引用類型參數(shù)使子算法定義形式與其調(diào)用形式之間具有直觀的對(duì)應(yīng)性，達(dá)到類似于傳址調(diào)用的效果，引用類型參數(shù)可以提高數(shù)據(jù)傳遞效率。[例7.7]設(shè)計(jì)子算法，根據(jù)汽車的信息（車牌號(hào)、油箱體積、本年度累計(jì)加油次數(shù)）計(jì)算本年度該汽車使用汽油量。算法名稱： GetTotalConsumption；算法輸入： 汽車信息（包括汽車牌照、油箱體積、加油次數(shù)）。算法輸出： 子算法返回汽車的年耗油量。數(shù)據(jù)結(jié)構(gòu)： 類型CarInfo為結(jié)構(gòu)，具有三個(gè)字段：szSerial(汽車牌照 號(hào)，字符串)、nVol（油箱體積，整型）、nNum（加油次 數(shù)，整型）。進(jìn)入返回問題分析： 由于子算法所需要的輸入均與某輛汽車相關(guān)，顯然最好的 風(fēng)格是將它們作為一個(gè)整體，因此在本算法實(shí)現(xiàn)中定義了 結(jié)構(gòu)類型CarInfo，而為了提高參數(shù)的傳遞效率，將子算法 的參數(shù)類型取為引用類型CarType&。具體描述和相應(yīng)的C++ 實(shí)現(xiàn)（其中包括子算法的調(diào)用方法示例）如下：7.2.3

參數(shù)為引用的子算法進(jìn)入返回temp←info.nVol×info.nNumGetTotalConsumption←tempint

GetTotalConsumption(CarInfo&info)#include"iostream.h"#include"string.h"struct

CarInfo{char*szPlate;int

nVol;int

nNum;};int

GetTotalConsumption(CarInfo&info){

inttemp;temp=info.nVol*info.nNum;returntemp;}voidmain(){

CarInfoi;

i.szPlate=newchar[10];

strcpy(i.szPlate,"京A:StruRef");

i.nNum=40;

i.nVol=100;

cout<<GetTotalConsumption(i)<<endl;}7.2.4 子算法設(shè)計(jì)與C++實(shí)現(xiàn)示例[例7.8]設(shè)計(jì)一個(gè)班級(jí)成績(jī)管理程序，該程序能夠?qū)⒚總€(gè)學(xué)生的成績(jī)按照總成績(jī)由高到低的順序存儲(chǔ)，并可通過學(xué)號(hào)查尋學(xué)生的成績(jī)。學(xué)生的成績(jī)包括總成績(jī)、語(yǔ)文成績(jī)、數(shù)學(xué)成績(jī)、化學(xué)成績(jī)等。算法名稱： InsertScore主要功能： 將學(xué)生的各科成績(jī)按照總成績(jī)排序插入到班級(jí)成績(jī)表的 適當(dāng)位置。算法輸入： nNum（整型，學(xué)號(hào)）、pName（字符串，學(xué)生姓名）、 nChi（整型，語(yǔ)文成績(jī)）、nMath（整型，數(shù)學(xué)成績(jī)）、 nChem（整型，化學(xué)成績(jī)）算法輸出： 無(wú)返回值數(shù)據(jù)結(jié)構(gòu)： 使用了班級(jí)成績(jī)表ClassScore。成績(jī)表第i項(xiàng)尚未使用將成績(jī)插入當(dāng)前元素處當(dāng)前元素總成績(jī)<nTotal調(diào)用ShiftRight右移數(shù)組元素在當(dāng)前位置插入新成績(jī)voidInsertScore(int

nNum,char*pName,int

nChi,int

nMath,int

nChem)進(jìn)入返回nTotal=nChi+nMath+nChemi←0；i<學(xué)生總數(shù)；i←i+17.2.4 子算法設(shè)計(jì)與C++實(shí)現(xiàn)示例[例7.8]算法名稱：

ShiftRight。主要功能：

將某個(gè)名次以下的成績(jī)名次順次下降一名，空出位置用于插入新成績(jī)。算法輸入：

nIndexFrom（整型，該名次及該名次后的所有學(xué)生名次向后移一名）。算法輸出： 無(wú)返回值。問題分析： 向后移動(dòng)一個(gè)數(shù)組的元素應(yīng)從數(shù)組的倒數(shù)第二個(gè)元素開始，將這個(gè)元素拷貝到倒數(shù)第一個(gè)元素、將第i-1個(gè)元素拷貝到第i個(gè)元素，直到第nIndexFrom拷貝完為止。這個(gè)過程中如果發(fā)現(xiàn)某個(gè)元素尚未被賦給有效值，那么沒必要拷貝這個(gè)元素，直接進(jìn)入下一個(gè)元素的拷貝即可。進(jìn)入返回對(duì)ClassScore[]，從倒數(shù)第二個(gè)元素到第nIndexFrom個(gè)元素拷貝當(dāng)前元素所有字段至下一個(gè)元素如該元素為空voidShiftRight(int

nIndexFrom)7.2.4 子算法設(shè)計(jì)與C++實(shí)現(xiàn)示例[例7.8]算法名稱： GetScore。主要功能： 根據(jù)學(xué)生的學(xué)號(hào)查尋班級(jí)成績(jī)表，并得到該學(xué)生的成績(jī)。算法輸入： No（整型，學(xué)號(hào)）、marks（類型為SCORE&）。算法輸出： 無(wú)返回值，查得的學(xué)生成績(jī)放置于子算法參數(shù)marks中。數(shù)據(jù)結(jié)構(gòu)： 使用了ClassScore[]。問題分析： 從成績(jī)表中的第一名順序檢索全表，發(fā)現(xiàn)某項(xiàng)的學(xué)號(hào)與檢索關(guān)鍵字nNo相同則返回相應(yīng)的成績(jī)。voidGetScore(int

nNo,SCORE&marks)進(jìn)入返回nNo=ClassScore[i].Nomarks=當(dāng)前表項(xiàng)從第一名開始對(duì)所有學(xué)生7.3遞歸與迭代7.3.1 遞歸7.3.2 迭代7.3.3 應(yīng)用示例7.3.1 遞歸分治法： 將復(fù)雜問題它分解成若干規(guī)模較小，復(fù)雜程度較低的小問題，在解決了所有小問題后，根據(jù)這些小問題之間的關(guān)系，將它們組合在一起，從而得到復(fù)雜問題的解。遞歸： 在采用分治法解決復(fù)雜問題時(shí)經(jīng)常會(huì)發(fā)現(xiàn)，在將問題劃分成各個(gè)層次后，雖然各層次問題的解題算法相同，并且隨著層次的加深，問題的復(fù)雜性變低，但是解決某個(gè)層次的問題往往依賴于下一層問題的解決，只要下一層問題得到解決，這一層的問題就可以解決。由于各層的算法相同，因此很容易就會(huì)想到將任意一層的解題過程用一個(gè)函數(shù)描述出來(lái)，由于上一層和下一層的依賴關(guān)系，顯然解決上一層復(fù)雜問題時(shí)需要調(diào)用解決當(dāng)前層相對(duì)簡(jiǎn)單問題的函數(shù)，解決當(dāng)前層問題又需要調(diào)用解決下一層更簡(jiǎn)單問題的函數(shù)，周而復(fù)始，直到最底層極其簡(jiǎn)單問題的解決，一旦最底層的問題得以解決，那么回過頭來(lái)解決它上一層的問題，然后是再上一層的問題……，一層一層地向上，最終將解決所有各層問題。注意：在對(duì)問題劃分層次時(shí)應(yīng)該保證總層次數(shù)是有限的，這是在有限步驟內(nèi)解決問題的必要條件。上面這種特殊的采用分治法解決問題的過程稱為遞歸。7.3.1 遞歸Factorial(0)Factorial(n)=n×Factorial(n-1)int

Factorial(intn)longFactorial(intn){if(n==1)return1;elsereturnn*Factorial(n-1);}int

Factorial(intn)進(jìn)入退出

n=1Factorial←1Factorial(n-1)5！5×Factorial(4)遞推①2×1回歸②3×2回歸③4×6回歸④5×24回歸⑤1204×Factorial(3)遞推②3×Factorial(2)遞推③2×Factorial(1)遞推④Factorial(1)=1遞推⑤回歸①7.3.1 遞歸[例7.9]編寫程序求斐波那契（Fibonacci）數(shù)列的第n項(xiàng)。問題的提出源于兔子問題：一對(duì)兔子每?jī)稍路敝骋粚?duì)兔子，設(shè)第n月兔子對(duì)數(shù)F(n)，則F(n)=F(n-1)+F(n-2)，即第n月兔子對(duì)數(shù)等于上月兔子對(duì)數(shù)加上新生兔子對(duì)數(shù)，新生兔子對(duì)數(shù)正好是前個(gè)月兔子對(duì)數(shù)，故有：

F(0)=0 F(1)=1

F(n)=F(n-1)+F(n-2)longFibonacii(intn){

switch(n){case0:return0;case1:return1;

default:returnFibonacii(n-1)+Fibonacii(n-2);}}voidmain(){

cout<<Fibonacii(10)<<endl;}7.3.2 迭代longFactorial(intn){

intVi_1=1,Vi=0;

for(inti=1;i<=n;i++){Vi=i*Vi_1;Vi_1=Vi;}returnVi;}Factorial(0)Factorial(n)=n×Factorial(n-1)F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)longFibonacii(intn){