基于遞歸的技術(shù)

第二部分

基于遞歸的技術(shù)

基于遞歸的技術(shù)歸納法無(wú)重疊子問(wèn)題重疊子問(wèn)題Ch5歸納法5.1引言如果我們知道如何求解規(guī)模為n-1的問(wèn)題，那么我們的任務(wù)就化為如何把解法擴(kuò)展到規(guī)模為n的問(wèn)題5.2選擇排序?qū)?shù)組a[1…n]按從小到大順序排序用歸納法：假設(shè)我們已經(jīng)知道如何對(duì)n-1個(gè)數(shù)排序，則：要對(duì)a[1…n]排序（1）求a[1…n]的最小值a[j];(2)a[1]a[j];(3)對(duì)a[2…n]排序算法5.1

selectionSort(inta[],intn){sort(a,1,n);//對(duì)a[1...n]排序}

sort(inta[],int

i,intn){（1）j=min(a,i,n);//求a[i…n]中最小值的下標(biāo)j;(2)a[i]a[j];(3)if(i+1<n)sort(a,i+1,n);}討論（1）算法5.1a

Sort(inti){（1）j=min(a,i,n);//求a[i…n]中最小值的下標(biāo)j;(2)a[i]a[j];(3)if(i+1<n)Sort(i+1);}以上程序有什么問(wèn)題？以上函數(shù)中，數(shù)組a的首地址，和數(shù)組元素個(gè)數(shù)n，從何而來(lái)？方法一：用參數(shù)傳遞，如算法5.1

Sort(int

a[],int

i,intn)方法二：把數(shù)組a和n定義為全局變量，則在函數(shù)Sort(inti)中可以使用。方法三：定義類，把a(bǔ)和n作為類的成員變量，函數(shù)Sort(inti)做為類的成員函數(shù)。問(wèn)題：如何在一個(gè)已有序的序列a[1...n]中插入一個(gè)新元素x，使其仍然有序？簡(jiǎn)單！首先檢查是否有足夠空間，然后，用一個(gè)for循環(huán)實(shí)現(xiàn)新元素的插入，.......5.3插入排序24810X=66用歸納法思想：假設(shè)我們已經(jīng)知道如何對(duì)n-1個(gè)元素排序，則要對(duì)a[1…n]排序（1）對(duì)a[1...n-1]排序；（2）將a[n]插入a[1...n-1]的適當(dāng)位置上，使其仍然有序。要對(duì)a[1…i]排序（1）對(duì)a[1...i-1]排序；（2）將a[i]插入a[1...i-1]的適當(dāng)位置上，使其仍然有序。算法5.2sort(inta[],inti){//本函數(shù)對(duì)a[1...i]排序

if(i>1){sort(a,i-1);//對(duì)a[1...i-1]排序

insert(a,i-1,a[i]););//將a[i]插入已排好序的a[1...i-1]中

}}如果不要”if(i>1)“這個(gè)遞歸進(jìn)行的條件這個(gè)程序運(yùn)行時(shí)會(huì)出現(xiàn)什么癥狀？5.4整數(shù)冪設(shè)計(jì)一個(gè)求x的n次冪的算法方法一：對(duì)x用迭代自乘n次

for(i=1,fact=1;i<=n;i++)fact=fact*x;其時(shí)間復(fù)雜度為Θ(n)能否設(shè)計(jì)一個(gè)更高效的算法？用歸納法分析：假設(shè)已經(jīng)知道如何求xn/2

令如果n是偶數(shù)，那么xn=(xm)2;否則xn=(xm)2x算法5.3Exp(floatx,intn)//求xn{Power(x,n);}Power(floatx,intm){

（1）如果m==0則返回y=1;

否則（2）y=Power(x,m/2)(3)y=y*y;(4)如果m為奇數(shù)，則y=xy;

（5）返回y;}算法5.3apower(floatx,intm){if(m==0)return1;else{y=power(x,m/2)y=y*y;if(m%2!=0)y=xy;returny;}}算法5.3bpower(floatx,intm){if(m==0)return1;y=power(x,m/2)y=y*y;if(m%2!=0)y=xy;returny;}討論（2）算法5.3b和算法5.3c哪個(gè)是錯(cuò)誤的，如何改寫？算法5.3cPower(floatx,intm){if(m==0)y=1;y=Power(x,m/2)y=y*y;if(m%2!=0)y=x*y;returny;}這個(gè)程序運(yùn)行時(shí)會(huì)出現(xiàn)什么癥狀？方法二：重復(fù)平方法(1)令n的二進(jìn)制數(shù)是dkdk-1...d0。(2)y賦初值1，(3)從左到右掃描二進(jìn)制數(shù)字:

如果當(dāng)前的二進(jìn)制數(shù)字為0，則y=y*y;

否則，y=y*y*x請(qǐng)用213驗(yàn)證本算法！13=(1101)2d3=1,d2=1,d1=0,d0=113=1

×23+1

×22+0

×21+1X13=x23×

x22×

x1

（需8次乘法）

=(((x)2

x)2)

2x

（需5次乘法）1326232120111013=2*6+1=2*(2*3+

0)+

1=

2*(2*(2*1+1)+

0)+

1=2*(2*(2*(2*0+1)+1)+

0)+

1高低13=(1101)2

d3=

1,d2=

1,d1=

0,d0=1,13=1

×23+1

×22+0

×21+1

×20X13=((x2

x)2)

2x

（需5次乘法）(2)y賦初值1，(3)從左到右掃描二進(jìn)制數(shù)字:

如果當(dāng)前的二進(jìn)制數(shù)字為0，則y=y*y;

否則，y=y*y*xd3=

1：y=1*1*x=x;d2=1

：y=x*x*x=x3;d1=

0

：y=x3*x3=x6;d0=1

：y=x6*x6*x

=x13;算法5.4Exp(floatx,intn){y=1;

將n用二進(jìn)制數(shù)dkdk-1...d0表示。

for(j=k;j>=0;j--){y=y*y;

if(dj==1)y=y*x;}returny;}5.6生成排列先講一個(gè)故事，三個(gè)小孩玩“毛毛蟲(chóng)游戲”，為了公平，她們要不停的換次序，要嘗試完所有的排列，有多少種排列，四個(gè)人呢？五個(gè)人呢？方法一:指定排頭法問(wèn)題：對(duì)于數(shù)1,2,...,n生成所有的排列分析：可用數(shù)組存儲(chǔ)這n個(gè)元素。初始狀態(tài)下,a[i]=i,i=1…n若n=3,則有

（1）1為排頭的所有排列：123、132（2）2為排頭：213、231（3）3為排頭：213、231123對(duì)n個(gè)數(shù)的情況，歸納分析如下：

假定可以生成n-1個(gè)數(shù)的所有排列，那么就可以擴(kuò)展生成n個(gè)數(shù)的排列。方法如下：（1）生成數(shù)2,3,...,n的所有排列，并在每個(gè)排列前加上數(shù)1；（2）生成數(shù)1,3,...,n的所有排列，并在每個(gè)排列前加上數(shù)2；

........

（i）生成數(shù)2,...i-1,1,i+1,..,n的所有排列，并在每個(gè)排列前加上數(shù)i；

.........

（n）生成數(shù)2,...,n-1,1的所有排列，并在每個(gè)排列前加上數(shù)n；數(shù)組P的初始狀態(tài):1,2,....,n（1）生成數(shù)2,3,...,n的所有排列，并在每個(gè)排列前加上數(shù)1；perm(2,n)

（2）生成數(shù)1,3,...,n的所有排列，并在每個(gè)排列前加上數(shù)2；

{s1：將p[1]與p[2]交換；P:2,1,3,...,ns2：perm(2,n);s3：將p[1]與p[2]再交換回來(lái)；P:1,2,3,...,n}........

（i）生成數(shù)2,...i-1,1,i+1,..,n的所有排列，并在每個(gè)排列前加上數(shù)i；

{s1：將p[1]與p[i]交換；P:i,2,...i-1,1,i+1,..,ns2：perm(2,n);s3：將p[1]與p[i]再交換回來(lái)；P:1,2,3,...,n}

算法5.4Permutation(intn){for(i=1;i<=n;i++)P[i]=i;Perm(1,n);//生成1到n的所有排列}

Perm(int

m,intn)//生成P[m]到P[n]的全排列

{如果m==n，輸出P[1...n];//遞歸到葉子結(jié)點(diǎn)，得到一個(gè)排列，返回上一層否則

{forj=mton{互換P[j]和P[m]；//讓P[j]當(dāng)排頭

//生成P[m+1...n]的所有排列

Perml(m+1,n);

互換P[j]和P[m]；//讓P[j]回到原位

}}}生成1,2,3,4的所有排列forj=3to4{互換P[j]和P[3]；

Perml(4,4);互換P[j]和P[3]；}Perm(3,4)forj=1to4{互換P[j]和[1]；Perm(2,4);互換P[j]和P[1]；}Perm(1,4)P:1234forj=2to4{互換P[j]和P[2]；

Perml(3,4);互換P[j]和P[2]；}Perm(2,4)If(m=n)輸出P[1...n]Perm(4,4)Perm(1,4):forj=1to4

j=1:P[1]與P[1]互換

1234

Perm(2,4):

forj=2to4j=2:P[2]與P[2]互換

1234

Perm(3,4)：forj=3to4j=3：

P[3]與P[3]互換

12

34Perml(4,4)：輸出1234P[3]與P[3]互換

j=4：

P[4]與P[3]互換：

12

43Perml(4,4)：輸出1243

P[4]與P[3]互換：1234

j=3:P[3]與P[2]互換

13

2

4

Perm(3,4)：forj=3to4j=3：

P[3]與P[3]互換

13

2

4Perml(4,4)：輸出1324；

P[3]回位；P[3]與P[3]互換：

j=4：

P[4]與P[3]互換

1342Perml(4,4)：輸出1342

；

P[4]回位；P[4]與P[3]互換：

j=4:輸出：1432

、1423

請(qǐng)寫出其前6個(gè)排列1233232輸出123輸出12323213133131輸出213輸出231131212輸出321輸出31221213211為排頭：23123方法二:填補(bǔ)空位法問(wèn)題：對(duì)于數(shù)1,2,...,n生成所有的排列分析：可用數(shù)組a[1…n]代表n個(gè)空位。初始狀態(tài)下,a[i]=0,i=1…n若n=3,則有

（1）3站在第一個(gè)空位的所有排列：

312、321（2）3站在第二個(gè)空位的所有排列：

132、231（3）3站在第三個(gè)空位的所有排列：

123、213000030300003算法5.6Permutation2(intn){for(i=1;i<=n;i++)P[i]=0;Perm2(n);//生成1到n的所有排列}Perm2(intm){//n、n-1…m+1都已找好位置，用1…m填補(bǔ)數(shù)組P的m個(gè)空位如果m=0,則說(shuō)明n、n-1…1都已找好位置，輸出一個(gè)排列否則對(duì)當(dāng)前每一個(gè)空位（共m個(gè)）：（1）指定m放入其中一個(gè)；（2）用1…m-1填補(bǔ)數(shù)組P的剩余m-1個(gè)空位

Perm2(intm){//n、n-1…m+1都已找好位置，用1…m填補(bǔ)數(shù)組P的m個(gè)空位

if(m==0)輸出一個(gè)排列p[1…n]//n、n-1…1都有位置了

else//否則，為m找位置

for(j=1;i<=n;j++)//掃描所有位置

if(p[j]==0)//對(duì)當(dāng)前每一個(gè)空位

{

p[j]=m;//指定m放入其中一個(gè)；

perm2(m-1)//用1…m-1填補(bǔ)數(shù)組P的剩余m-1個(gè)空位

p[j]=0;//m離開(kāi)j位置，嘗試別的位置，j位置置空

}}課下練習(xí)組合：從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合，例如OR={1,2,3,4},n=4,r=3，則組合為：{1,2,3};{1,2,4};{1,3,4};{2,3,4}.5.7尋找多數(shù)元素問(wèn)題：有整型數(shù)組a[1...n],如果整數(shù)x在數(shù)組a中出現(xiàn)的次數(shù)多于半數(shù)，則x稱為多數(shù)元素。方法一：計(jì)算每一個(gè)元素出現(xiàn)的次數(shù)

O(n2)方法二：排序，然后求在中間位置的元素出現(xiàn)的次數(shù)O(nlogn)歸納法分析此問(wèn)題觀察結(jié)論5.1：在原序列中去除兩個(gè)不同的元素后，那么在原序列中的多數(shù)元素在新序列中還是多數(shù)元素。例1：1，2，2，3，2，2，3顯然2是多數(shù)元素去除1，2，在2，3，2，2，3中2仍是多數(shù)元素去除1，3，在2，3，2，2，3中2更是多數(shù)元素但是，在新序列中是多數(shù)元素的，在原序列中不一定是多數(shù)元素。例2：1，3，2，3，2，2，3顯然沒(méi)有多數(shù)元素去除1，3，在2，3，2，2，3中2成了多數(shù)故在觀察結(jié)論5.1的支持下，能得到多數(shù)元素的候選者尋找多數(shù)元素候選者的過(guò)程：（1）計(jì)數(shù)器count置1，另c=A[1];(2)從A[2]開(kāi)始向后掃描，forj=2ton

若a[j]與c相等，則count++;

若a[j]與c不等，則count—

若count==0,則對(duì)A[j+1...n]尋找多數(shù)元素候選者（遞歸調(diào)用自身）。尋找候選者算法(1)Candidate(i