計算概論習題課

計算概論

(IntroductiontoComputing)習題課指針與遞歸指針指針的基本概念

地下工作者阿金接到上級指令，要去尋找打開密電碼的密鑰，這是一個整數。幾經周折，才探知如下線索，密鑰藏在一棟三年前就被貼上封條的小樓中。一個風雨交加的夜晚，阿金潛入了小樓，房間很多，不知該進哪一間，正在一籌莫展之際，忽然走廊上的電話鈴聲響起。藝高人膽大，阿金毫不遲疑，抓起聽筒。只聽一個陌生人說：“去打開211房間，那里有線索”。阿金疾步上樓，打開211房門，用電筒一照，只見桌上赫然6個大字：地址1000。阿金眼睛一亮，迅速找到1000房間，取出重要數據66，完成了任務。

P單元P所指向的地址

1000

66

地址211地址10001000…66…2111000P指針變量的類型，是指針所指向的變量的類型，而不是自身的類型指針的值是某個變量的內存地址指針變量——用來存放另一變量地址的變量指針的基本概念定義含義int*p;p是指向整型數據的指針變量

inta[n];定義數組a，元素類型為int，元素個數是nint*p[n];p是指針數組，包含n個指針變量，每一個指針變量可以指向整型數據

適用于多字符串操作

int(*p)[n];p是指向數組的行指針，數組有n個整型數 int*p[4];intscore[3][4];p=score;適用于多維數組

intf();f是函數，返回值是intint*p();p是函數，返回值是指針，指向整型數據

int(*p)();p是函數指針變量，可以指向返回int數據類型的函數的入口地址。

int**p;p是指針變量，指向一個指向整型數據的指針指針的定義小結空類型指針void*void*p，表示p是空類型指針，它可以指向任何數據類型?？疹愋椭羔樑c其他類型指針之間賦值時，應進行強制類型轉換。例、char*p1;

void*p2;

p1=(char*)p2;

p2=(void*)p1;指向指針的指針：適合高速運算int*p;inta[3];p=a;p(動態(tài)數組)a(靜態(tài)數組)指針的定義小結空指針的使用小結int*p=NULL;表示指針不指向任何內存地址.防止其指向任何未知的內存區(qū)域避免產生難以預料的錯誤發(fā)生.把指針初始化為

NULL

是好習慣.在stdio.h中，NULL被定義為0：

#defineNULL0習慣上，不使用p=0，而使用p=NULL指針變量p可以與NULL作比較，例：if(p==NULL)注意：空指針不指向任何數據，與p未賦值不同。當p未賦值時，其值是不確定的，而空指針的值是確定數0指針運算小結1、指針變量加/減運算p++、p--、p+i、p-i、p+=i、p-=i加1表示指向下一個數據。2、指針變量賦值

p=&a;變量a的地址賦給p，即指針p指向a

p=array;數組array首地址賦給p

p=&array[i];數組元素array[i]的地址賦給p

p=max;函數max的入口地址賦給p

p1=p2;指針p2的值賦給指針p1，即p1、p2所指的數據相同。3、指針變量相減。

當p1、p2指向同一個數組的元素，指針相假p2-p1等于p1、p2間的元素個數。

注意：指針相加無意義。指針與數組01234&a[0]&a[1]&a[2]&a[3]&a[4]&a[1]&a[2]&p1&p2p1p2P1和p2分別指向a[1],a[2]，這里&——取地址運算符*——指針運算符（間接訪問運算符）*p1——間接訪問p1所指向的內存單元，當然是輸出a[1]的值*p2——間接訪問p2所指向的內存單元，當然是輸出a[2]的值指針與數組(1)p=a;這里數組名作為數組的起始地址，即a[0]的地址。數組名是一個常量指針

因此p=a等效于p=&a[0];(2)p=p+1;如p指向a[0],則p=p+1之后，p指向a[1](3)如果p=a等效于p=&a[0];

則p=a+4等效于p=&a[4];a[0]a[1]a[2]a[3]a[4]*p*(p+1)*(p+2)*(p+3)*(p+4)pp+1p+2pp+1p+2等效指針與字符串（字符數組）//***************************************//*主要功能：指針（字符串從右到左輸出）*

//***************************************#include<stdio.h>//預編譯命令intmain(){//主函數 charshuzi[]="987654321";//定義數組，

//賦初值為數字字符串 char*p=&shuzi[8];//讓指針p指向shuzi[8]元素，

//該處是字符‘1’ do //直到型循環(huán) { //循環(huán)體開始 printf(“%c”,*p); //輸出由p指向的一個字符

p--; //讓p減1 } //循環(huán)體結束 while(p>=shuzi); //當p>=shuzi時，繼續(xù)循環(huán) printf(“\n”);//換行

return0；}指針數組概念元素為指針的數組稱之為指針數組對比一般數組單元中裝的是數據指針數組單元中裝的是地址

指針數組指針數組的定義和初始化例

intar0[]={0,1,2};//定義一般數組

intar1[]={1,2,3};//定義一般數組

intar2[]={2,3,4};//定義一般數組

int*p[]={ar0,ar1,ar2};//定義指針數組地址

數組名就是地址指針數組

012

指針數組p&ar0[0]&ar0[1]&ar0[2]&p[0]&ar0&p[1]&ar1123&p[2]&ar2&ar1[0]&ar1[1]&ar1[2]

234&ar2[0]&ar2[1]&ar2[2]指針使用的注意事項1、若指針p指向數組a，雖然p+i與a+i、*(p+i)與*(a+i)意義相同，但仍應注意p與a的區(qū)別(a代表數組的首地址，是不變的；p是一個指針變量，可以指向數組中的任何元素)inta[10];*p;for(p=a;a<(p+10);a++)printf("%d",*a)；是否正確？指針使用的注意事項2、指針變量可以指向數組中的任何元素，注意指針變量的當前值。因此：使用指針時，應特別注意避免指針訪問越界本例中第二次for循環(huán)p已經越過數組的范圍但編譯器不能發(fā)現該問題避免指針訪問越界是程序員自己的責任main(){int*p,i,a[10];

p=a;

for(i=0;i<10;i++)

scanf("%d",p++);

printf("\n");

for(i=0;i<10;i++,p++)

printf("%d",*p);}指針使用的注意事項3、指針使用的幾個細節(jié)。設指針p指向數組a（p=a），則：p++（或p+=1），則：*p=？*p++表示什么意義？*(p++)與*(++p)的分別表示什么意義？(*p)++表示什么意義？約瑟夫環(huán)問題描述有

n個人，編號為

1,2,...,n,站成一圈。沿著圈順序數，每到第m個人就把他殺掉，這樣一直進行下去，直到只剩下一個人，那個人就活下來。約瑟夫很聰明，他總會想辦法站到一個合適的位置上，使得自己能夠成為最后一個，從而活下來。例如：n=6，

m=5時，被殺的順序是5,4,6,2,3，而

1最終活下來。

給定n,m,求出最后留下的人的編號位置12345612346123612313startendstartendstartendendstartstartend約瑟夫環(huán)1。使用數組，刪除人移動數組2。使用數組，刪除人用一個標記表示，不用移動數據12345612346123612313startendstartendstartendendstartstartend123456startendstartendstartendendstartstartend1234-16123-1-16123-1-1-11-13-1-16約瑟夫環(huán)一直到最后剩一個人1---標號x,記為number上一層的number

number=(number+m)%2一般化表示，對有i個人的序列，序號為number[i]=(number[i-1]+m)%iSourcecode#include<stdio.h>intmain(){ intn,m,i=0,j=0; inta[MAX]; printf("Pleaseinputn(<=1000):"); scanf("%d",&n); printf("Pleaseinputm:"); scanf("%d",&m); for(intk=0;k<n;k++){ a[k]=k;}

while(n>1)

{

j=(i+m-1)%n; for(intk=j;k<n;k++) a[k]=a[k+1]; i=j; n--;

} printf("JosephshouldstandatNo.%d\n",a[0]+1); return0;}約瑟夫環(huán)數學解法，復雜度低n個人的序列1234……m-1mm+1…..n殺掉一個人的序列1234……m-1m+1…..n重排序列m+1….n12….m-1x’序號重新編號序列—n-1人序列123….n-1

x序號x’=(m+x)%n…….最后剩1個人1約瑟夫環(huán)—續(xù)假設有

k個好人和

k個壞人。在圈上前

k個是好人，后

k個是壞蛋?，F在讓你來確定一個最小的

m使得所有的壞蛋被殺掉后，才開始殺第1個好人。輸入輸入有若干個k。

最后1個值是0。假設

0<k<14。輸出對應每個輸入的k，輸出相應的m。樣例輸入樣例輸出

340530約瑟夫環(huán)—殺人問題問題分析1)求最小的m值可以用枚舉的方法： 即依次看m=1，2，3，…時，是否滿足條件。2)枚舉的過程就是依次殺掉圈上的一半的人，并判斷該人是否是好人，如果是好人，則當前的m不滿足條件，否則m滿足條件。3)一共有2k個人。4)k可以取1，2，3，…,13?？梢砸淮嗡愠鏊邢鄳膍，存在一個數組中，這樣每次讀入一個k，就輸出相應的m。Sourcecode#include<stdio.h>intkill_bad_man(inta[],intm,intk){inti;for(i=1;i<=k;i++){a[i]=(a[i-1]+m-1)%(2*k-i+1);if(a[i]<k)return0;}return1;}voidmain(){inta[14],k,m;scanf(“%d”,&k);m=k;a[0]=0;

while(!kill_bad_man(a,m,k))m++;printf(“%d”,m);}約瑟夫環(huán)—殺人問題數學解法，復雜度低N個人的序列1234……m-1mm+1…..n殺掉一個人的序列1234……m-1m+1…..n重排序列m+1…n12…m-1x’序號重新編號序列—n-1人序列123…n-mn-m+1n-m+2….n-1

x序號由此得到：x’=(m+x)%n

(0實際編號為n)m+1m+2m+3…m+n-mm+n-m+1m+n-m+2…m+n-1…….最后剩k個人

遞歸遞歸調用函數返回值類型

函數名

（[參數1類型

參數名1，

參數2類型

參數名2，……]）多個返回值？？？調用過程中輸入參數變化/不變遞歸函數遞歸調用函數出口voidrecursive（parameters）{recursive（parameters）函數出口}遞歸調用用遞歸算法求n!定義：函數fact(n)=n! fact(n-1)=(n-1)!

則有 fact(n)=nfact(n-1)

已知 fact(1)=1intfact(intn){ if(n>1)

{ returnn*fact(n-1);

} else

{ return1;

}}下面畫出了調用和返回的遞歸示意圖intfact(intn){ return(n>1?n*fact(n-1):1);}從圖可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剝一顆圓白菜，從外向里，一層層剝下來，到了菜心，遇到1的階乘，其值為1，到達了遞歸的邊界。然后再用fact(n)=n*fact(n-1)這個普遍公式，從里向外倒推回去得到fact(n)的值遞推與遞歸漢諾塔問題相傳在古代印度的Bramah廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現，如以每秒移動一只盤子的話，按照上述規(guī)則將64只盤子從一個柱子移至另一個柱子上，所需時間約為5800億年漢諾塔問題1、在A柱上只有一只盤子，假定盤號為1，這時只需將該盤從A搬至C，一次完成，記為

move1#fromAtoC(演示)ABC1漢諾塔問題2、在A柱上有二只盤子，1為小盤，2為大盤第（1）步將1號盤從A移至B，這是為了讓2號盤能動；第（2）步將2號盤從A移至C；第（3）步再將1號盤從B移至C；ABC21漢諾塔問題3、在A柱上有3只盤子，從小到大分別為1號，2號，3號第（1）步將1號盤和2號盤視為一個整體；先將二者作為整體從A移至B，給3號盤創(chuàng)造能夠一次移至C的機會。這一步記為move(2,A,C,B)意思是將上面的2只盤子作為整體從A借助C移至B。第（2）步將3號盤從A移至C，一次到位。記為

move3#fromAtoC第（3）步處于B上的作為一個整體的2只盤子，再移至C。這一步記為

move(2,B,A,C)意思是將2只盤子作為整體從B借助A移至C。move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213漢諾塔問題4、從題目的約束條件看，大盤上可以隨便摞小盤，相反則不允許。在將1號和2號盤當整體從A移至B的過程中move(2,A,C,B)實際上是分解為以下三步 第（1）.1步：move1#formAtoC; 第（1）.2步：move2#formAtoB; 第（1）.3步：move1#formCtoB;漢諾塔問題經過以上步驟，將1號和2號盤作為整體從A

移至B，為3號盤從A

移至C

創(chuàng)造了條件。同樣，3號盤一旦到了C，就要考慮如何實現將1號和2號盤當整體從B

移至C的過程了。實際上move(2,B,A,C)

也要分解為三步： 第（3）.1步：move1#formBtoA; 第（3）.2步：move2#formBtoC; 第（3）.3步：move1#formAtoC;漢諾塔問題5、看move(2,A,C,B)

是說要將2只盤子從A

搬至B，但沒有

C

是不行的，因為第（1）.1步就要將1#盤從A

移到C，給2#盤創(chuàng)造條件從A

移至B，然后再把1#盤從C

移至B。看到這里就能明白借助C

的含義了。因此，在構思搬移過程的參量時，要把3個柱子都用上。Sourcecode#include<stdio.h>

voidmove(charx,chary)

{

printf("%c-->%c\n",x,y);

}

voidhanoi(intn,intA,intB,intC)

{

if(n==1)

{

move(A,C);

}

else

{

hanoi(n-1,A,C,B);

move(A,C);

hanoi(n-1,B,A,C);

}

}

voidmain()

{

intm;