專業(yè)課參考-語言程序設(shè)計

編譯：神秘的后臺共84頁第2

頁變量的存儲類型與作用域變量的數(shù)據(jù)類型

char型

int型

float型

double型總結(jié)：數(shù)據(jù)類型決定為變量分配的內(nèi)存單元的長度，數(shù)據(jù)的存在形式。（從程序設(shè)計角度，決定了可以表示的數(shù)的范圍）問題：1.何時為變量分配存儲單元？

2.

變量分配在何地？3.變量何時生？何時死，生存時誰可用？共84頁第3

頁變量的存儲類型與作用域變量的數(shù)據(jù)類型問題：何時為變量分配存儲單元？回答：編譯時(靜態(tài)分配)

/運行時(動態(tài)分配)問題：變量分配在何地？回答：堆棧(臨時區(qū))

/數(shù)據(jù)區(qū)/寄存器問題：變量何時生？何時死，生存時誰可用？回答：變量的生存期是指變量從產(chǎn)生到消亡的整個過程。函數(shù)/程序

變量的作用域是指程序中可以引用變量的有效范圍。函數(shù)/文件/程序共84頁第4

頁變量存貯類型有四種--存貯類型說明符自動變量（auto）靜態(tài)變量（static）外部變量（extern）寄存器變量（register）變量說明的一般形式存貯類型說明符

類型說明符變量名稱；變量的存儲類型與作用域共84頁第5

頁變量的存儲類型與作用域-自動變量自動變量：auto

最常見的一類變量。例如： autointa; autofloatpi;

auto

可以省略。說明 1.說明自動變量必須在某個函數(shù)內(nèi)部。 2.函數(shù)的形參是自動變量。共84頁第6

頁變量的存儲類型與作用域-自動變量作用域

自動變量作用域在所說明的函數(shù)內(nèi)部。實質(zhì)上是一個函數(shù)內(nèi)部的局部變量。生存期

在函數(shù)被調(diào)用時才在堆棧中分配產(chǎn)生，函數(shù)返回時消失；變量值僅限于說明它的函數(shù)，其它函數(shù)中不能存取。

由于自動變量具有局部性，所以在兩個不同的函數(shù)中可使用同名的變量而互不影響。共84頁第7

頁變量的存儲類型與作用域-自動變量例8-9.C：分析程序打印結(jié)果：#include<stdio.h>main(){intx=1;/*函數(shù)main中的自動變量x*/voidf1(),f2();f1(); f2(x);/*分別調(diào)用函數(shù)f1和f2*/printf("x=%d\n",x);}voidf1(void){intx=3;/*函數(shù)f1中的自動變量x*/printf("x=%d\t",x);}voidf2(x)intx;/*函數(shù)f2中的形參x也是自動變量*/{printf("x=%d\t",++x);/*x加1*/}例C8-9共84頁第8

頁變量的存儲類型與作用域-寄存器變量寄存器變量：register 寄存器變量可以提高程序運行速度。 由于受硬件寄存器長度的限制，寄存器變量只能是char、int或指針型。register說明符只能說明函數(shù)中的變量和函數(shù)的形參。 寄存器是與機器硬件密切相關(guān)，不同的CPU，寄存器的數(shù)目不一樣，通常為2到3個，若在一個函數(shù)中說明多于2到3個寄存器變量，編譯程序會自動地將它們變?yōu)樽詣幼兞?。?4頁第9

頁變量的存儲類型與作用域-寄存器變量作用域

在所說明的函數(shù)內(nèi)部。實質(zhì)上是一個函數(shù)內(nèi)部的局部變量。生存期

在函數(shù)被調(diào)用時才在

CPU中分配產(chǎn)生，函數(shù)返回時消失；變量值僅限于說明它的函數(shù)，其它函數(shù)中不能存取。共84頁第10

頁變量的存儲類型與作用域-外部變量定義在所有函數(shù)之外的全局變量。 可被所有的函數(shù)訪問，函數(shù)之間可通過外部變量傳遞數(shù)據(jù)。

int

x=0;

/*說明外部變量x*/main(){...}共84頁第11

頁變量的存儲類型與作用域-外部變量例C8-10.C:分析程序運行結(jié)果intx=0;/*說明外部變量x*/main(){voidaddone(),subone();x=1;/*為外部變量x賦值*/

printf("xbeginsis%d\n",x);addone();subone();subone();addone();addone();printf("xwindsupas%d\n",x);}voidaddone(void){x++;/*使用外部變量x*/printf("add1tomake%d\n",x);}voidsubone(void){x

--;/*使用外部變量x*/printf("substract1tomake%d\n",x);}共84頁第12

頁變量的存儲類型與作用域-外部變量作用域

在所說明的程序。實質(zhì)上是一個程序的全局變量。程序中的所有函數(shù)均可引用。生存期

在函數(shù)編譯時由編譯器在數(shù)據(jù)區(qū)中分配永久的存儲單元。共84頁第13

頁外部變量與自動變量的區(qū)別 1.外部變量在編譯時由編譯系統(tǒng)在數(shù)據(jù)段分配永久性的存儲空間； 自動變量則是在函數(shù)每次被調(diào)用時才在堆棧中分配臨時性的存儲空間，是動態(tài)分配產(chǎn)生的。 2.外部變量如果沒有賦初值，則為0；自動變量沒有賦初值，則值不定。變量的存儲類型與作用域-外部變量共84頁第14

頁實例 程序1：

#include<stdio.h> main() {intx;

/*自動變量*/

printf(”x=%d”,x): } 程序2：

#include<stdio.h>

intx;/*外部變量*/

main() {printf(”x=%d”,x): }變量的存儲類型與作用域-外部變量共84頁第15

頁在不同的文件中使用外部變量和函數(shù)對于大系統(tǒng)而言，可將一個程序分割為多個文件，通過工程文件，可以將整個系統(tǒng)連為一個整體。一個函數(shù)要在一個文件中，不能分割。如果外部變量的說明與使用在同一個文件中，則在該文件的函數(shù)中使用外部變量時，可直接使用。當外部變量的說明與使用在不同的文件，要使用在其它文件中說明的外部變量，就必須在使用該外部變量之前，使用“extern”存儲類型說明符進行變量“外部”說明。變量的存儲類型與作用域-外部變量共84頁第16

頁在不同的文件中使用外部變量和函數(shù)(續(xù)) extern僅說明變量是“外部的”，以及它的類型，并不真正分配存儲空間。在將若干個文件連接生成一個完整的可運行程序時，系統(tǒng)會將不同文件中使用的同一外部變量連在一起，使用同一個系統(tǒng)分配的存儲單元。

當被調(diào)用的函數(shù)在另一個文件中時，在調(diào)用該函數(shù)時，無論被調(diào)用的函數(shù)是什么類型，都必須用extern說明符說明被調(diào)用函數(shù)是“外部函數(shù)”。變量的存儲類型與作用域-外部變量共84頁第17

頁在不同的文件中使用外部變量和函數(shù)(續(xù))變量的存儲類型與作用域-外部變量c8_303.prjc8_303a.cc8_303b.cc8_303a.cc8_303b.c

TC環(huán)境→project→projectname填項目文件名c8_303.prj，編譯后生成c8_303a.obj和c8_303b.obj，然后連接生成c8_303.exe。c8_303a.objc8_303b.obj其他obj文件c8_303.exe共84頁第18

頁例C8-10.C:下列程序由兩個文件組成，請分析運行結(jié)果。/*文件一*/

intx=10;/*定義外部變量x和y*/inty=10;voidadd(void){y=10+x;x*=2;}main(){externvoidsub();/*說明sub是void型的外部函數(shù)*/

x+=5;add();sub();/*分別調(diào)用函數(shù)*/

printf("x=%d;y=%d\n",x,y);}/*文件二*/

voidsub(void)/*函數(shù)sub定義在另一個文件中*/{extern

intx;/*說明在另一個文件中的外部變量x*/

x-=5;}變量的存儲類型與作用域-外部變量共84頁第19

頁靜態(tài)變量：static

外部靜態(tài)變量：說明在所有函數(shù)之外的變量。

內(nèi)部靜態(tài)變量：說明在函數(shù)內(nèi)部的變量。作用域

外部靜態(tài)變量在所說明的文件，是屬于當前一個文件的全局變量，在當前文件的所有函數(shù)中均可引用。

內(nèi)部靜態(tài)變量在所說明的函數(shù)，是屬于當前一個函數(shù)的全局變量。生存期

在編譯時由編譯器在數(shù)據(jù)區(qū)中分配永久的存儲單元。變量的存儲類型與作用域-靜態(tài)變量共84頁第20

頁靜態(tài)變量與外部變量的相同點：具有永久的存儲空間；由編譯器進行初始化。外部靜態(tài)變量與外部變量的區(qū)別：外部靜態(tài)變量僅在定義它的當前文件有效，而外部變量作用于整個程序。內(nèi)部靜態(tài)變量與外部靜態(tài)變量的區(qū)別：內(nèi)部靜態(tài)變量作用于定義它的當前函數(shù)。內(nèi)部靜態(tài)變量與自動變量的區(qū)別：內(nèi)部靜態(tài)變量占用永久性的存儲單元，每次調(diào)用時能延續(xù)變量上次的值，保持數(shù)據(jù)的連續(xù)性；自動變量不能。變量的存儲類型與作用域-靜態(tài)變量共84頁第21

頁例C4_4401.C:分析下列程序的運行結(jié)果。 /*文件一*/

staticintx=2;/*說明外部靜態(tài)變量x*/inty=3;/*說明外部變量y*/externvoidadd2();/*說明外部函數(shù)add2*/voidadd1();

main(){add1();add2();add1();add2();printf("x=%d;y=%d\n",x,y);}voidadd1(void)/*定義函數(shù)add1*/{x+=2;y+=3;printf("inadd1x=%d\n",x);}/*文件二*/

staticintx=10;/*說明外部靜態(tài)變量x*/voidadd2(void)/*定義函數(shù)add2*/{externinty;/*說明另一個文件中的外部變量y*/x+=10;y+=2;printf("inadd2x=%d\n",

x);}變量的存儲類型與作用域-靜態(tài)變量共84頁第22

頁例C4_4402.C:分析下列程序的運行結(jié)果。#include<stdio.h>main(){voidinc1(),inc2();inc1();inc1();inc1();inc2();inc2();inc2();}voidinc1(){intx=0;/*說明自動變量x并賦初值*/

x++;printf("ininc1x=%d\n",x);}voidinc2(){staticintx=0;/*說明內(nèi)部靜態(tài)變量x并初始化*/

x++;printf("ininc2x=%d\n",

x);}變量的存儲類型與作用域-靜態(tài)變量共84頁第23

頁變量初始化與賦初值的區(qū)別 對于自動變量和寄存器變量：變量的初始化要在運行時，由賦值操作進行。在剛進入一個函數(shù)時，函數(shù)中自動變量和寄存器變量的值是不定的。 對于外部變量和靜態(tài)變量，變量初始化工由編譯完成。編譯時為外部變量和靜態(tài)變量分配永久性的存儲單元并進行初始化。運行程序時，外部變量和靜態(tài)變量已有初值。變量的存儲類型與作用域-變量初始化共84頁第24

頁在函數(shù)中說明自動變量或寄存器變量時，可使用這樣的語句：

main(){intx=3;registerinty=4;...} 這不是給自動變量或寄存器變量初始化，是在運行時執(zhí)行賦值操作為自動變量或寄存器變量賦初值?！?-5變量的存儲類型與作用域-變量初始化共84頁第25

頁在函數(shù)中說明外部變量或靜態(tài)變量時，可使用這樣的語句：

intx1=2,x2;staticinty=3;main(){staticintz=10;......} 這時編譯程序會自動為x1、x2、y和z進行初始化。不需要程序在運行時再做賦值操作了。 對于象變量x2在說明時沒指定初值的外部變量或靜態(tài)變量，編譯系統(tǒng)自動將初值置為0?！?-5變量的存儲類型與作用域-變量初始化共84頁第26

頁性能自動變量外部變量外部靜態(tài)內(nèi)部靜態(tài)寄存器變量記憶能力無有有有無多個函數(shù)共享否可可否否在不同文件共享性否可否否否未顯示賦值的取值不定０００不定變量初始化程序控制編譯器編譯器編譯器程序控制數(shù)組與結(jié)構(gòu)初始化有

可可可否作用域當前函數(shù)整個程序文件函數(shù)當前函數(shù)§8-5變量的存儲類型與作用域-存儲類型小結(jié)你中有我，我中有你共84頁第28

頁

你站在橋上看風景，

看風景人在樓上看你，

明月裝飾了你的窗子，

你裝飾了別人的夢。 ——卞之琳遞歸共84頁第29

頁遞歸的概念

遞歸是一種常用的程序設(shè)計技術(shù)，在一個程序中，若存在程序自己調(diào)用自己的現(xiàn)象就形成了遞歸。 如果函數(shù)funA在執(zhí)行過程又調(diào)用函數(shù)funA自己，則稱函數(shù)funA為直接遞歸。 如果函數(shù)funA在執(zhí)行過程中先調(diào)用函數(shù)funB，函數(shù)funB在執(zhí)行過程中又調(diào)用函數(shù)funA，則稱函數(shù)funA為間接遞歸。遞歸共84頁第30

頁例C8-11.C：用遞歸方法求階乘n!。遞歸定義

f(n)=1當n=1時

f(n)=n*f(n-1)當n>1時程序?qū)崿F(xiàn) facto(intn){intr;if(n==1)r=1;elser=n*facto(n-1);/*遞歸*/

return(r);}遞歸-遞歸程序的執(zhí)行過程共84頁第31

頁主函數(shù)第一次調(diào)用第二次

第三次

第四次

n=4p=facto(4)

調(diào)用└─→n=4

r=4*facto(3)

調(diào)用└─→n=3

r=3*facto(2)

調(diào)用└─→n=2

r=2*facto(1)└─→n=1

return(1)┌←─────┘返回

r=2*1=2

return(2)┌←─────┘返回

r=3*2=6

return(6)┌←─────┘返回

r=4*6=24

return(24)┌←──────┘返回

p=24facto(intn){intr;if(n==1)r=1;elser=n*facto(n-1);return(r);}遞歸返回過程遞歸調(diào)用過程遞歸-遞歸程序的執(zhí)行過程共84頁第32

頁遞歸-遞歸程序的執(zhí)行過程遞歸調(diào)用的執(zhí)行過程facto(n)intn;{intr;if(n==1)r=1;elser=n*facto(n-1);

return(r);}facto(intn

){intr;if(n==1)

r=1;else{r=facto(n-1);r=n*r;}return(r);}等價于當n=1時f(n)=1當n>1時f(n)=n*f(n-1)共84頁第33

頁遞歸-遞歸程序的執(zhí)行過程facto(intn){intr;if(n==1)

r=1;else{r=facto(n-1);r=n*r;}return(r);}facto(intn)intr;if(n==1)facto(intn){intr;if(n==1)

r=1;else{r=facto(n-1);r=n*r;}return(r);}r=facto(n-1)facto(intn)intr;if(n==1)facto(intn){intr;if(n==1)

r=1;else{r=facto(n-1);r=n*r;}return(r);}r=facto(n-1)facto(intn){intr;if(n==1)

r=1;else{r=facto(n-1);r=n*r;}return(r);}facto(intn)facto(intn)intr;intr;if(n==1)if(n==1)r=facto(n-1)r=1return(1)r=n*r=2*1return(2)return(6)r=n*r=3*2r=n*r=4*6return(24)1調(diào)用234調(diào)用調(diào)用321返回返回返回N=4N=3N=2N=1共84頁第34

頁遞歸算法與遞推算法比較10！=10*9！9！=9*8！8！=8*7！7！=7*6！6！=6*5！5！=5*4！4！=4*3！3！=3*2！2！=2*1！1！=1*0！遞歸-遞歸1=11=22=66=2424=120120=720720=50405040=4032040320=362880362880=3628800

1！=12！=1*2=23！=2*3=64！=6*4=245！=24*5=120

6！=120*6=720

7！=720*7=5040

8！=5040*8=403209！=40320*9=36288010！=362880*10=3628800共84頁第35

頁例C8-12.C：采用遞歸方法計算x的n次方。遞歸定義

f(x,n)=1

當n=0時

f(x,n)=xn=x*f(x,n-1) 當n>0時程序

power(intx,intn){if(n==0)return(1);/*遞歸結(jié)束條件*/

elsereturn(x*power(x,n-1));}遞歸-下一個實例例C8-12共84頁第36

頁遞歸的基礎(chǔ)

語言本身支持遞歸調(diào)用。 變量存儲類型（自動變量）的特點，保證了在每次遞歸調(diào)用的過程中，變量可以保持相對獨立性，不會發(fā)生相互干擾。對遞歸的認識 所有的遞歸問題一定可用非遞歸算法實現(xiàn)。 一些問題本身已經(jīng)蘊涵了遞歸關(guān)系且結(jié)構(gòu)復(fù)雜，用非遞歸算法可能會使程序結(jié)構(gòu)非常復(fù)雜，采用遞歸算法實現(xiàn)，可使程序簡潔，提高程序的可讀性。 遞歸會增加存儲空間和執(zhí)行時間上的開銷。遞歸-討論共84頁第37

頁遞歸問題的分類數(shù)值性遞歸問題非數(shù)值性遞歸問題

對于不同類型的問題,可以采用不同的解決方法。編寫遞歸程序的關(guān)鍵建立遞歸模型 問題的遞歸定義（遞歸描述）是編寫遞歸程序的基礎(chǔ)。遞歸結(jié)束條件 是保證遞歸可以正常結(jié)束的前提。遞歸-編寫遞歸程序的一般方法共84頁第38

頁數(shù)值型問題的遞歸求解一般方法 從數(shù)學公式入手：推出問題的遞歸定義；確定問題的邊界條件；再得到問題的遞歸算法和遞歸結(jié)束條件例C8-13：求自然數(shù)1到n之和。 建立問題的遞歸定義：

f(n)=1 當n=1時

f(n)=n+f(n-1)當n>1時

程序：add(intn){if(n==1)return(1);/*遞歸結(jié)束條件*/

if(n>1)return(n+add(n-1));}遞歸結(jié)束條件遞歸算法遞歸-編寫數(shù)值型遞歸程序例C8-13共84頁第39

頁例C8-14：求菲波那奇序列：1，1，2，3，5，8，13，21，34，…… 建立問題的遞歸定義：

f(n)=1

當n=1或n=2

時

f(n)=f(n-1)+f(n-2)

當n>2

時

程序：f(intn){ if(n==1||n==2)return(1);/*

結(jié)束條件

*/

if(n>2)return(f(n-1)+f(n-2)); elsereturn(-1);/*返回-1表示出錯*/}遞歸結(jié)束條件遞歸算法遞歸-編寫數(shù)值型遞歸程序例C8-14共84頁第40

頁例C8-15：計算楊輝三角型：111121133114641

……

……

……

……

……

……

……遞歸-編寫數(shù)值型遞歸程序 建立問題的遞歸定義計算第x

行的第y

個值：c(x,y)=1x>=0，y=1或y=x+1c(x,y)=c(x-1,y-1)+c(x-1,y)其它0行，1列1行，2列4行，4列共84頁第41

頁例C8-15：打印楊輝三角型：

遞歸數(shù)學模型：

c(x,y)=1x>=0，y=1或y=x+1 c(x,y)=c(x-1,y-1)+c(x-1,y)其它遞歸-編寫數(shù)值型遞歸程序例C8-15程序：intc(intx,inty)/*求第x行y列的值*/{if(x>=0&&((y==1)||(y==x+1)))return1;

elsereturnc(x-1,y-1)+c(x-1,y);}共84頁第42

頁例C8-16.C：下列程序的功能是計算函數(shù)px的值：

px(x,n)=x-x2+x3-x4+......(-1)n-1xnn>0 已知程序：

doublepx(doublex,intn){if(n==1)return(

);

elsereturn(x*

);} 請?zhí)顚戇m當?shù)恼Z句，使之成為正確的程序。遞歸-編寫數(shù)值型遞歸程序共84頁第43

頁分析：

px(x,n)=x-x2+x3-x4+......(-1)n-1xnn>0

=x*(1-x+x2-x3+......(-1)n-1xn-1

)=x*(1-

(x-x2+x3-......(-1)n-2xn-1

)) =x*(1-px(x,n-1))

可將非遞歸定義形式轉(zhuǎn)化為等價的遞歸定義：

px(x,n)=

x

當n=1

時

px(x,n)=x*(1-px(x,n-1))

當n>1

時程序：doublepx(doublex,intn){if(n==1)return(

);

elsereturn(x*

);}

x(1-px(x,n-1))遞歸-編寫數(shù)值型遞歸程序共84頁第44

頁非數(shù)值型問題的遞歸求解一般方法①化簡：分析在最簡情況下問題的求解方法。求解方法一定是非遞歸算法，且十分簡單。②

分解：將一般問題分解為兩個(或多個)小問題，且每個分解后的小問題與原問題相似，具有相同的性質(zhì)，只是問題的規(guī)模有所縮小。③建立模型：將每個分解出的小問題看作一個整體，建立用小問題解決一般問題的算法。④

由①

可以產(chǎn)生遞歸結(jié)束條件，由③可以推出遞歸算法。 思路類似于“數(shù)學歸納法”遞歸-編寫非數(shù)值型遞歸程序共84頁第45

頁例C8-17：反序輸出整數(shù)n(n>=0)。問題分析： 1. 若n為1位整數(shù)（0≤n≤9）：則直接輸出。 2. 將任一個整數(shù)n

(****+)(n>=10)分為兩部分：

◆個位(+)

◆除個位以外的其余部分(****) 3. 將分解后的兩部分分別看成整體，則原問題：

①輸出n的個位(+)

②

反序輸出

n的除個位以外的其余部分(****) 由1推出遞歸終止條件。 由3得到遞歸算法。遞歸-編寫非數(shù)值型遞歸程序共84頁第46

頁1

2

3

4551

2

3441

23312211遞歸-編寫非數(shù)值型遞歸程序遞歸算法描述：

若：整數(shù)n只有1位數(shù)字

則：輸出該整數(shù)n；

否則：輸出n的個位；

反序輸出n的除個位以外的其余部分。遞歸n/10printn(n)共84頁第47

頁程序：printn(intn){if(0<=n&&n<=9)

printf(”%d”,n);else{

printf(”%d”,n%10);

/*輸出個位*/

printn(n/10);/*遞歸*/}}遞歸-編寫非數(shù)值型遞歸程序例C8-17共84頁第48

頁例C8-18：輸出高度為n的等邊三角形。當n=3

時： * *** *****程序填空 main() {inti,n; scanf("%d",&n);

for(i=1;i<=n;i++)

{

prt(’

’,n-i);/*左側(cè)空格*/ prt(’*’,2*i-1);/*中間*號*/ printf("\n");

} }遞歸-編寫非數(shù)值型遞歸程序共84頁第49

頁輸出子函數(shù)prt：voidprt(charc,intn){if(n>0){printf(”%c”,c);

_________;}}問題分析：

函數(shù)prt的功能是：輸出n個字符c。 如果n>0，則：

輸出1個字符；

輸出其余n-1

個字符； 否則：

結(jié)束遞歸-編寫非數(shù)值型遞歸程序prt(c,n-1)共84頁第50

頁遞歸-編寫非數(shù)值型遞歸程序漢諾塔問題據(jù)說在約十九世紀末歐洲的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構(gòu)成的塔。 游戲的目的是將最左邊Ａ桿上的圓盤，借助最右邊的Ｃ桿，全部移到中間的Ｂ桿上，條件是一次僅能移動一個盤，且不允許大盤放在小盤的上面。64片初始桿中間桿目的桿1

n18,446,744,073,709,551,615次1844億億次。每次1微秒，需要60萬年共84頁第51

頁第1步，將問題簡化。假設(shè)A桿上只有2個圓盤，即漢諾塔有2層，N＝2。遞歸-編寫非數(shù)值型遞歸程序A桿C桿B桿移動方法：1.將上面小片移到C桿上。2.將下面的大片由A桿移到B桿上。3.將C桿上的小片移到B桿上。分析： 對A桿上的全部N個圓盤從小到大順序編號，最小的圓盤為1號，次之為2號……則最下面的圓盤的編號為N。共84頁第52

頁A桿C桿B桿遞歸-編寫非數(shù)值型遞歸程序第2步，對于一個有N(N>1)個圓盤的漢諾塔，將N個圓盤分為兩部分：上面的N-1個圓盤和最下面的N號圓盤。將“上面的N-1個圓盤”看成一個整體。第3步，為解決

N

個圓盤的漢諾塔，可按如下方式進行操作： ①將A桿上面的N-1個盤子，借助B桿，移到C桿上； ②將A桿上剩下的

N號盤子移到B桿上； ③將C桿上的N-1個盤子，借助A桿，移到B桿上共84頁第53

頁 整理分析：把第1步中化簡問題的條件作為遞歸結(jié)束條件，將第3步分析得到的算法作為遞歸算法。 定義函數(shù)movedisc(n，fromneedle，toneedle，usingneedle)。將fromneedle桿上的N個圓盤，借助usingneedle桿，移動到toneedle

桿上。移動N個圓盤的遞歸算法描述如下：movedisc(n，fromneedle，toneedle，usingneedle){if(n==1)將

n

號圓盤從

fromneedle上移到

toneedle;

else{①movedisc(n-1，fromneedle，usingneedle，toneedle)②將

n

號圓盤從

fromneedle上移到toneedle;③movedisc(n-1，usingneedle，toneedle，fromneedle)

}}遞歸-編寫非數(shù)值型遞歸程序共84頁第54

頁程序C8-19.Cinti=0;/*移動圓盤數(shù)量計數(shù)器*/main(){unsignedn;scanf("%d",&n);

movedisc(n,’a’,’b’,’c’);/*將A上的N個圓盤借助C將移動到B上*/

printf("\tTotal:%d\n",i);}movedisc(n,fromneedle,toneedle,usingneedle)unsignedn;charfromneedle,toneedle,usingneedle;{if(n==1)printf("%2d-(%2d):%c==>%c\n",++i,n,fromneedle,toneedle);

else{

movedisc(n-1,fromneedle,usingneedle,toneedle);printf("%2d-(%2d):%c==>%c\