第五講-遞推與遞歸

第五講遞推與遞歸主要內(nèi)容遞推及其應(yīng)用遞歸及其應(yīng)用

第五講遞推與遞歸遞推是通過(guò)數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡(jiǎn)單運(yùn)算，以充分發(fā)揮計(jì)算機(jī)擅長(zhǎng)重復(fù)處理的特點(diǎn)。遞歸是將復(fù)雜的操作分解為簡(jiǎn)單操作的多次重復(fù)，一般用函數(shù)調(diào)用完成。

遞推關(guān)系是一種簡(jiǎn)潔高效的常見(jiàn)數(shù)學(xué)模型。

如：Fibonacci數(shù)列問(wèn)題。遞推特點(diǎn)：在遞推問(wèn)題中，每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)（或后面的若干個(gè)數(shù)據(jù)項(xiàng)）有一定的關(guān)聯(lián)，這種關(guān)聯(lián)一般通過(guò)“遞推關(guān)系式”表示。11.1遞推遞推過(guò)程：從初始的一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)出發(fā)，通過(guò)遞推關(guān)系式逐步推進(jìn)，從而得到最終結(jié)果。其中：初始的若干數(shù)據(jù)項(xiàng)稱為“邊界”。

11.1遞推11.1遞推例如：Fibonacci數(shù)列問(wèn)題

已知：F(1)=0，F(xiàn)(2)=1，若：

n>2，則F(n)=F(n-1)+F(n-2)注意：

1）每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)（或后面的若干個(gè)數(shù)據(jù)項(xiàng)）有一定的關(guān)聯(lián)-----遞推關(guān)系式。

2）從初始的一個(gè)或若干數(shù)據(jù)項(xiàng)出發(fā)，通過(guò)遞推關(guān)系式逐步推進(jìn)，從而得到最終結(jié)果。11.1遞推注意：3）遞推必須有“邊界”。4）解決遞推類(lèi)型問(wèn)題有三個(gè)重點(diǎn)：如何建立正確的遞推關(guān)系式；遞推關(guān)系有何性質(zhì)；遞推關(guān)系式如何求解?；A(chǔ)，重點(diǎn)11.1遞推按照推導(dǎo)問(wèn)題的方向，遞推分為：順推法：從初始數(shù)據(jù)開(kāi)始推理。

例如：n=0時(shí)，n!=1；

n>1時(shí)，n!=n*(n-1)!倒推法：從結(jié)果數(shù)據(jù)開(kāi)始推理。例如：n!=n*(n-1)!；

邊界：n=0，n!=1例1：猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半又一個(gè)。第2天又把剩下的桃吃了一半又一個(gè)，以后每天都吃前一天剩下的桃子的一半又一個(gè)，到第10天猴子想吃時(shí)，只剩下一個(gè)桃子。問(wèn)：猴子第1天一共摘了多少桃子?分析：已知條件：第10天剩下1個(gè)桃子；隱含條件：每一次前一天的桃子個(gè)數(shù)等于后一天桃子的個(gè)數(shù)加1的2倍。逆向思維：從后往前推，可用倒推法求解。#include<stdio.h>voidmain(){ inti,a=1; for(i=9;i>=1;i--) a=(a+1)*2; printf("a=%d\n",a);}例1：逆推法---求解猴子吃桃子例2：猴子分食桃子1)五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分食。2)半夜里，一只猴子偷偷起來(lái)，把桃子均分成五堆后，發(fā)現(xiàn)還多一個(gè)，它吃掉這桃子，并拿走了其中一堆。3)第二只猴子醒來(lái)，又把桃子均分成五堆后，還是多了一個(gè)，它也吃掉這個(gè)桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。問(wèn)：五只猴子采得一堆桃子數(shù)最少應(yīng)該有幾個(gè)呢？逆推法算法分析：

先要找第N只猴子和其面前桃子數(shù)的關(guān)系。如果從第1只開(kāi)始往第5只找，不好找，但如果思路一變，從第N到第1去，可得出下面的推導(dǎo)式：第N只猴

第N只猴前桃子數(shù)目

5

s5=x 4

s4=s5*5/4+1 3

s3=s4*5/4+1 2

s2=s3*5/4+1 1

s1=s2*5/4+1

通過(guò)遞推，求出s1即可例2：猴子分食桃子---逆推法注意：其中的s1、s2、s3、s4、s5必須是整數(shù)//例2：猴子分食桃子---逆推法#include<stdio.h>voidmain(){ intx,s,k,i; x=6;//最少的初值

k=0;//整除標(biāo)志

while(k!=4) { s=x; k=0; for(i=4;i>=1;i--) {if(s%4==0)k++;elsebreak; s=s*5/4+1; } x=x+5; } printf("s=%d\n",s);}11.1.2遞推設(shè)計(jì)實(shí)例例11.1：母牛的故事

問(wèn)題描述：有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個(gè)年頭開(kāi)始，每年年初也生一頭小母牛。編程實(shí)現(xiàn)：在第n年的時(shí)候，共有多少頭母牛？例11.1：母牛的故事---順推法

設(shè)數(shù)組f(i)表示第i年的母?？倲?shù)，則第n年的母?？倲?shù)為f(n)。

f(n)與兩個(gè)值有關(guān)在本年之前就已經(jīng)出生的母牛數(shù)目在本年新出生的小母牛數(shù)目。1）本年之前就已經(jīng)出生的母牛數(shù)目，實(shí)際上就是前一年的母牛總數(shù)----f（n-1）。2）由于每一頭母牛每年只生育一頭小母牛，所以在本年新出生的小母牛數(shù)目，實(shí)際上是到今年可以生育的母牛的數(shù)目。3)而每頭小母牛從第四個(gè)年頭才開(kāi)始生育，所以今年可以生育的母牛的數(shù)實(shí)際上就是三年前的母?？倲?shù)，即為f（n-3）。例11.1：母牛的故事---順推法遞推公式：

f(n)=f(n-1)+f(n-3)（n>=4）第一、二、三年的母?？倲?shù)是直接可知的:f(1)=1；

f(2)=2;f(3)=3；遞推邊界｝也可以從最簡(jiǎn)單開(kāi)始，找規(guī)律：

若數(shù)組f(i)表示第i年的母牛總數(shù)，則第n年的母?？倲?shù)為f(n)。

n=1f(n)=1n=2f(n)=2

n=3f(n)=3n=4f(n)=3+1=f[3]+f[1]=4

n=5f(n)=f(4)+f(2)

n=6f(n)=f(5)+f(3)

n=7f(n)=f(6)+f(4)

規(guī)律：

f(n)=f(n-1)+f(n-3)(n>=4)例11.1：母牛的故事---順推法#include<stdio.h>voidmain(){_int64f[50];//_int64---定義大整數(shù)

inti,n;scanf("%d",&n);f[1]=1;f[2]=2;f[3]=3;for(i=4;i<=n;i++){f[i]=f[i-3]+f[i-1];printf("%I64d\n",f[i]);//%I64d—大整數(shù)輸入/輸出格式

}}問(wèn)題描述：在2×n的長(zhǎng)方形方格中，用n個(gè)1×2的骨牌鋪滿方格。問(wèn)：輸入n，輸出鋪放方案的總數(shù)？例如：n=3時(shí)，有2×3方格骨牌的鋪放方案有三種方法，如下圖所示：例11.2骨牌問(wèn)題---順推法長(zhǎng)度為n時(shí)的骨牌鋪放方案？從最簡(jiǎn)單的情況開(kāi)始尋找問(wèn)題解決的規(guī)律？---順推以f(i)表示n=i時(shí)的鋪放方案數(shù)目。當(dāng)n=1時(shí)，只有1種鋪法，即f(1)=1，如下左圖所示：當(dāng)n=2時(shí)，只有2種鋪法，即f(2)=2，如下右圖所示。例11.2骨牌問(wèn)題---順推法n=3時(shí)骨牌的鋪放方案有3種方法，f(3)=3如下圖:例11.2骨牌問(wèn)題---順推法這3種鋪放方法可以采用如下的步驟分析得到：n=3時(shí)，第一塊骨牌的鋪法只有2種可能，橫鋪或者豎鋪，即：（1）橫鋪方式：在第一格橫放一個(gè)骨牌，此時(shí)剩余兩格，在兩格內(nèi)鋪放骨牌有f(2)種鋪法；（2）豎鋪方式：在第一、二格豎放兩個(gè)骨牌，此時(shí)剩余一格，在一格內(nèi)鋪放骨牌有f(1)種鋪法；

f(3)=f(2)+f(1)=2+1=3。

對(duì)于一般的n值，其第一塊骨牌的鋪法也只有兩種可能，橫鋪或者豎鋪:

例11.2骨牌問(wèn)題---順推法（1）橫鋪方式：若第一格橫放一個(gè)骨牌，此時(shí)剩余n-1格，在n-1格放n-1個(gè)骨牌有f(n-1)種鋪法；（2）豎鋪方式：若第一、二格豎放兩格骨牌，此時(shí)剩余n-2格，在n-2格放n-2個(gè)骨牌有f(n-2)種鋪法；…………因此，n塊骨牌的鋪法是首塊骨牌橫鋪方式的鋪法與豎鋪方式的鋪法之和。即：f(n)=f(n-1)+f(n-2)邊界：f(1)=1，f(2)=2例11.2骨牌問(wèn)題---順推法遞推公式#include<stdio.h>intmain(){inti,n,f[20];

f[0]=1;f[1]=2;//邊界

scanf("%d",&n);for(i=2;i<n;i++){f[i]=f[i-1]+f[i-2];//遞推

printf("%d\n",f[i]);}}例11.2骨牌問(wèn)題#include<stdio.h>voidmain(){inti,n;

__int64f[50];

f[0]=1;f[1]=2;//邊界scanf("%d",&n);for(i=2;i<n;i++)

f[i]=f[i-1]+f[i-2];//遞推printf("%I64d\n",f[n-1]);}例11.2骨牌問(wèn)題---順推法問(wèn)題描述：

設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走1級(jí)，也可走2級(jí)，也可走3級(jí)。問(wèn)：求從底層開(kāi)始走完全部樓梯的有多少種走法。例如，當(dāng)n=3時(shí)，走法如下：

1+1+11+22+13

思考：上樓問(wèn)題n=3，共有4種走法

n的值

走法f(n) 1

1 2

2 3

4

47

從遞推的思想出發(fā)，可以設(shè)想，從第4項(xiàng)開(kāi)始，每1項(xiàng)等于前面3項(xiàng)的和。上樓問(wèn)題---算法分析f(n)=f(n-1)+f(n-2)+f(n-3)-----遞推公式

f(1)=1,f(2)=2,f(3)=4--------遞推邊界#include<stdio.h>//上樓問(wèn)題voidmain(){intx,n,i,a,b,c; scanf("%d",&n); a=1;b=2;c=4;

if(n==1)x=1; elseif(n==2)x=2; elseif(n==3)x=4;for(i=4;i<=n;i++){x=a+b+c;a=b;b=c;c=x;}

printf("%d",x);}例11.3錯(cuò)排信件問(wèn)題描述：某人寫(xiě)了n封信和n個(gè)信封，所有的信都裝錯(cuò)了信封。要求：若所有的信都裝錯(cuò)信封，共有多少種不同情況？例11.3錯(cuò)排信件找規(guī)律：對(duì)n封信以及n個(gè)信封各自按照從1…….n進(jìn)行編號(hào)；

f(n)-----n個(gè)編號(hào)的信放在n個(gè)編號(hào)的信封，各不對(duì)應(yīng)的方法數(shù)；f(n-1)----n-1個(gè)編號(hào)的信放在n-1個(gè)編號(hào)位置的信封，各不對(duì)應(yīng)的方法數(shù)。例11.3錯(cuò)排信件找規(guī)律：第一步:把第n封信放在第k個(gè)信封（k≠n），不對(duì)應(yīng)的共有n-1種方法；第二步:放編號(hào)為k的信，有兩種情況：

1）放編號(hào)為k的信放到第n個(gè)信封，則對(duì)于剩下的n-2封信，需要放到剩余的n-2個(gè)信封且各不對(duì)應(yīng)，就有f(n-2)種方法；

2）放編號(hào)為k的信不放到位置n，對(duì)于這n-1封信，放到剩余的n-1個(gè)信封且各不對(duì)應(yīng)，有f(n-1)種方法；結(jié)論：

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

特例：f（1）=0，f（2）=1------邊界例11.3錯(cuò)排信件#include<stdio.h>voidmain(){inti,n,f[20];f[1]=0;f[2]=1;scanf("%d",&n);for(i=3;i<=n;i++) {f[i]=(i-1)*(f[i-2]+f[i-1]);printf("%d\n",f[i]);}}例11.4馬踏過(guò)河卒----選講棋盤(pán)上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如下圖中的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)（如下圖中的C點(diǎn)和P1，P2，……，P8）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過(guò)20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的，C≠A且C≠B。編程：輸入n，m，計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。例11.4馬踏過(guò)河卒---選講馬踏過(guò)河卒是一道很老的題目，一些程序設(shè)計(jì)比賽中也經(jīng)常出現(xiàn)過(guò)這一問(wèn)題的變形。一看到這種類(lèi)型的題目容易讓人想到用搜索來(lái)解決，但盲目的搜索僅當(dāng)n,m=15就會(huì)超時(shí)。可以試著用遞推來(lái)進(jìn)行求解。根據(jù)卒行走的規(guī)則，過(guò)河卒要到達(dá)棋盤(pán)上的一個(gè)點(diǎn)，只能有兩種可能：從左邊過(guò)來(lái)（左點(diǎn)）或是從上面過(guò)來(lái)（上點(diǎn)），所以根據(jù)加法原理，過(guò)河卒到達(dá)某一點(diǎn)的路徑數(shù)目，就等于其到達(dá)其相鄰的上點(diǎn)和左點(diǎn)的路徑數(shù)目之和，因此可用逐列（或逐行）遞推的方法求出從起點(diǎn)到終點(diǎn)的路徑數(shù)目。障礙點(diǎn)（馬的控制點(diǎn)）也完全適用，只要將到達(dá)該點(diǎn)的路徑數(shù)目設(shè)置為0即可。例11.4馬踏過(guò)河卒---選講用二維數(shù)組元素f[i][j]表示到達(dá)點(diǎn)（i，j）的路徑數(shù)目；用g[i][j]表示點(diǎn)（i，j）是否是對(duì)方馬的控制點(diǎn)；若g[i][j]=0表示不是對(duì)方馬的控制點(diǎn)，g[i][j]=1表示是對(duì)方馬的控制點(diǎn)。則可以得到如下的遞推關(guān)系式：

f[i][j]=0當(dāng)g[i][j]=1f[i][0]=f[i-1][0]當(dāng)i＞0,g[i][j]=0f[0][j]=f[0][j-1]當(dāng)j＞0,g[i][j]=0f[i][j]=f[i-1][j]+f[i][j-1]

當(dāng)i＞0,j＞0,g[i][j]=0

遞推邊界：f[0][0]=1#include<stdio.h>//馬踏過(guò)河卒intmain(){inti,j,n,m,f[20][20],g[20][20],x,y;scanf("%d%d%d%d",&n,&m,&x,&y);for(i=1;i<=n;i++) for(j=1;j<=m;j++)f[i][j]=0;for(i=0;i<=n;i++) for(j=0;j<=m;j++)g[i][j]=0;g[x][y]=1;g[x-1][y-2]=1;g[x+1][y-2]=1;g[x-2][y-1]=1;g[x+2][y-1]=1;g[x-2][y+1]=1;g[x+2][y+1]=1;g[x-1][y+2]=1;g[x+1][y+2]=1;for(i=1;i<=n;i++) if(g[i][0]!=1)f[i][0]=1; elsefor(;i<=n;i++) f[i][0]=0;for(j=1;j<=m;j++) if(g[0][j]!=1)f[0][j]=1;

elsefor(;j<=m;j++)f[0][j]=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(g[i][j]==0) f[i][j]=f[i-1][j]+f[i][j-1];

printf("%d\n",f[n][m]);

return0;}例11.4馬踏過(guò)河卒—改進(jìn)為了更簡(jiǎn)潔地表示馬的控制點(diǎn)，可以引入兩個(gè)一維數(shù)組，分別用來(lái)統(tǒng)計(jì)從馬的初始位置可以橫向移動(dòng)的位移與縱向移動(dòng)的位移。程序的改進(jìn)如下：#include<stdio.h>intmain(){intdx[9]={0,-2,-1,1,2,2,1,-1,-2};intdy[9]={0,1,2,2,1,-1,-2,-2,-1};intn,m,x,y,i,j;intf[20][20]={0},g[20][20]={0};

scanf("%d%d%d%d",&n,&m,&x,&y); g[x][y]=1;例11.4馬踏過(guò)河卒for(i=1;i<=8;i++)if((x+dx[i]>=0)&&(x+dx[i]<=n)&&(y+dy[i]>=0)&&(y+dy[i]<=m))

g[x+dx[i]][y+dy[i]]=1;for(i=1;i<=n;i++)if(g[i][0]!=1)f[i][0]=1;elsefor(;i<=n;i++) f[i][0]=0;for(j=1;j<=m;j++)if(g[0][j]!=1)f[0][j]=1;elsefor(;j<=m;j++) f[0][j]=0; for(i=1;i<=n;i++)for(j=1;j<=m;j++) if(g[i][j]==1)f[i][j]=0; elsef[i][j]=f[i-1][j]+f[i][j-1];printf("%d\n",f[n][m]);return0;}

遞推應(yīng)用：王小二切餅，要求每2條線都有交點(diǎn)。問(wèn)：切第n刀后，餅被分為多少塊？

找規(guī)律：王小二切餅，要求每2條線都有交點(diǎn)。n=0;p(0)=1;n=1;p(1)=2;n=2;p(2)=4;n=3;p(3)=7;n=4;p(4)=11;規(guī)律：p(n)=p(n-1)+n#include<stdio.h>

//用遞推求解---切餅問(wèn)題intmain() { intn,i;intp[100];p[0]=1; scanf("%d",&n); for(i=1;i<=n;i++) {p[i]=p[i-1]+i; printf("%d\n",p[i]); } return0;}遞推思考輸出楊暉三角形的前10行。楊暉三角形的前5行如左下圖所示。問(wèn)題分析：觀察左上圖不太容易找到規(guī)律，但如果將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)楊輝三角形其實(shí)就是一個(gè)二維表（數(shù)組）的下三角部分。#include<stdio.h>//打印楊輝三角形voidmain(){inti,j，a[10][10];for(i=0;i<10;i++)a[i][0]=1;for(i=0;i<10;i++)for(j=i+1;j<10;j++) a[i][j]=0;for(i=1;i<10;i++) for(j=1;j<=i;j++) a[i][j]=a[i-1][j-1]+a[i-1][j];for(i=0;i<10;i++) {for(j=0;j<=i;j++)printf("%4d",a[i][j]);printf("\n"); }}遞推小結(jié)1）遞推是從已知條件開(kāi)始；2）遞推必須有明確的通用公式；3）遞推必須是有限次運(yùn)算。11.2遞歸遞歸的定義：在一個(gè)函數(shù)的定義中又直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解。11.2遞歸遞歸思想：

把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、易解決的同一問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，并且小到一定程度可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。遞歸優(yōu)點(diǎn)：只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。用遞歸算法編寫(xiě)的程序結(jié)構(gòu)清晰，具有很好的可讀性。遞歸缺點(diǎn)：通過(guò)直接的遞歸過(guò)程和函數(shù)實(shí)現(xiàn)起來(lái)，有時(shí)效率很差（用遞歸函數(shù)去求1000!）。遞歸算法適用在三個(gè)場(chǎng)合1)數(shù)據(jù)的定義形式是遞歸的，如求n!；2)數(shù)據(jù)之間的邏輯關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）是遞歸的，如樹(shù)、圖等的定義和操作；3)某些問(wèn)題雖然沒(méi)有明顯的遞歸關(guān)系或結(jié)構(gòu)，但問(wèn)題的解法是不斷重復(fù)執(zhí)行一種操作，只是問(wèn)題規(guī)模由大化小，直至某個(gè)原操作（基本操作）就結(jié)束。例如：漢諾塔問(wèn)題。遞歸設(shè)計(jì)的要件在函數(shù)中必須有直接或間接調(diào)用自身的語(yǔ)句；(2)

在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口（或遞歸邊界）。編寫(xiě)遞歸算法程序時(shí)，首先要對(duì)問(wèn)題的以下三個(gè)方面進(jìn)行分析：決定問(wèn)題規(guī)模的參數(shù)。需要用遞歸算法解決的問(wèn)題，其規(guī)模通常都是比較大的，在問(wèn)題中決定規(guī)模大小（或問(wèn)題復(fù)雜程度）的量有哪些？問(wèn)題的邊界條件及邊界值。在什么情況下可以直接得出問(wèn)題的解？--問(wèn)題的邊界條件及邊界值。解決問(wèn)題的通式。把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小、易解決的同一問(wèn)題，需要通過(guò)哪些步驟或等式來(lái)實(shí)現(xiàn)？---解決遞歸問(wèn)題的難點(diǎn)，把這些步驟或等式確定下來(lái)。遞歸設(shè)計(jì)實(shí)例1------哈諾（Hanoi）塔問(wèn)題：1)相傳在古代印度的Bramah廟中，有位僧人整天把三根柱子上的金盤(pán)倒來(lái)倒去，原來(lái)他是想把64個(gè)一個(gè)比一個(gè)小的金盤(pán)從一根柱子上移到另一根柱子上去。2)移動(dòng)規(guī)則：每次只允許移動(dòng)一只盤(pán)，大盤(pán)不得落在小盤(pán)上面。3)如以每秒移動(dòng)一只盤(pán)子，按照上述規(guī)則將64只盤(pán)子從一個(gè)柱子移至另一個(gè)柱子上，所需時(shí)間約為5800億年。先從最簡(jiǎn)單的情況開(kāi)始分析，理出思路。1、在A柱上只有一只盤(pán)子，假定盤(pán)號(hào)為1，這時(shí)只需將該盤(pán)從A搬至C，一次完成，記為:

move1#fromAtoCABC12、在A柱上有2

只盤(pán)子，1為小盤(pán)，2為大盤(pán)。第（1）步將1號(hào)盤(pán)從A移至B，這是為了讓2號(hào)盤(pán)能動(dòng)；

move1#fromAtoB;第（2）步將2號(hào)盤(pán)從A移至C；

move2#fromAtoC;第（3）步再將1號(hào)盤(pán)從B移至C；

move1#formBtoC;ABC213、在A柱上有3只盤(pán)子，從小到大分別為1號(hào)，2號(hào)，3號(hào)第（1）步：將1號(hào)盤(pán)和2號(hào)盤(pán)視為一個(gè)整體；先將二者作為整體從A移至B，給3號(hào)盤(pán)創(chuàng)造能夠一次移至C的機(jī)會(huì)。這一步記為move(2,A,C,B)

含義：將上面的2只盤(pán)子作為整體從A借助C移至B。第（2）步：將3號(hào)盤(pán)從A移至C，一次到位。記為

move3#fromAtoC第（3）步：處于B上的作為一個(gè)整體的2只盤(pán)子，再移至C。這一步記為 move(2,B,A,C)

含義：將2只盤(pán)子作為整體從B借助A移至C。 move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213移動(dòng)3個(gè)盤(pán)子的分解：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)ABC2134、從題目的約束條件看，大盤(pán)上可以隨便摞小盤(pán)，相反則不允許。在將1號(hào)和2號(hào)盤(pán)當(dāng)整體從A移至B的過(guò)程中move(2,A,C,B)實(shí)際上是分解為以下三步

第（1）.1步：move1#formAtoC;

第（1）.2步：move2#formAtoB;

第（1）.3步：move1#formCtoB;

經(jīng)過(guò)以上步驟，將1號(hào)和2號(hào)盤(pán)作為整體從A

移至B，為3號(hào)盤(pán)從A

移至C

創(chuàng)造了條件。同樣，3號(hào)盤(pán)一旦到了C，就要考慮如何實(shí)現(xiàn)將1號(hào)和2號(hào)盤(pán)當(dāng)整體從B

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

也要分解為三步：

第（3）.1步：move1#formBtoA;

第（3）.2步：move2#formBtoC;

第（3）.3步：move1#formAtoC;5、move(2,A,C,B)

是將2只盤(pán)子從A

搬至B，但沒(méi)有

C

不行，因?yàn)榈冢?）.1步就要將1#盤(pán)從A

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

移至B，然后再把1#盤(pán)從C

移至B。

注意：在move(2,A,C,B)中，

C是一個(gè)橋梁用。move(n,A,B,C)分解為3步：(1)move(n-1,A,C,B)

：將n-1只盤(pán)子作為一個(gè)整體從A經(jīng)C移到B；(2)

輸出n：AtoC：將n號(hào)盤(pán)從A移到C，是直接可解結(jié)點(diǎn)；(3)

move(n-1,B,A,C)：將n-1只盤(pán)子作為一個(gè)整體從B經(jīng)A移到C。---------遞歸

實(shí)現(xiàn)move(n-1,A,C,B)要分為3步：第1步：將n-2只盤(pán)子作為一個(gè)整體從A經(jīng)B到C--------move(n-2,A,B,C)；第2步：第n-1號(hào)盤(pán)子從A直接移至B，即n-1:AtoB；第3步：將n-2只盤(pán)子作為一個(gè)整體從C經(jīng)A移至B---------move(n-2,C,A,B)；//m表示盤(pán)子數(shù)目;

a，b，c表示柱子標(biāo)號(hào)voidmove(intm,chara,charb,charc){

if(m==1) //如果1個(gè)盤(pán)子，則為直接可解結(jié)點(diǎn)

{step++; //步數(shù)加1

printf("\n[%d]move1#from%cto%c\n",step,a,c);

}

else

{move(m-1,a,c,b); //遞歸調(diào)用move(m-1)

//直接可解結(jié)點(diǎn),輸出移盤(pán)信息

step++; //步數(shù)加1

printf("\n[%d]move%d#from%cto%c\n",step,m,a,c);

move(m-1,b,a,c); //遞歸調(diào)用move(m-1) }}

#include<iostream>//用遞歸求解Hanoi問(wèn)題intstep=0; //整型全局變量，移動(dòng)步數(shù)intmain(){intn;printf("請(qǐng)輸入盤(pán)數(shù)n=");scanf("%d",&n);

printf("在3根柱子上移%d只盤(pán)的步驟為:",n);move(n,'A','B','C');return0;}

該題是2000年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下：

1）一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面積也只容得下一只青蛙落腳。2）有一隊(duì)青蛙從小到大編號(hào)：1，2，…，n。3）初始時(shí)：青蛙只能趴在左岸的石頭L上，按編號(hào)一個(gè)落一個(gè)，小的落在大的上面。不允許大的在小的上面。遞歸設(shè)計(jì)實(shí)例2該題是2000年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下：4）在小溪中有S個(gè)石柱，有y片荷葉，規(guī)定溪中的石柱如有多只青蛙也是大在下、小在上，而且必須編號(hào)相鄰；5）對(duì)于荷葉只允許一只青蛙落腳，不允許多只落在其上；6）對(duì)于右岸的石柱R，與左岸的石柱L一樣允許多個(gè)青蛙落腳，但須一個(gè)落一個(gè)，小的在上，大的在下，且編號(hào)相鄰；7）當(dāng)青蛙從左岸的L上跳走后就不允許再跳回來(lái)；同樣，從左岸L上跳至右岸R，或從溪中荷葉、溪中石柱跳至右岸R上的青蛙也不允許再離開(kāi)。問(wèn)：在已知溪中有

s根石柱和

y片荷葉的情況下，最多能跳過(guò)多少只青蛙？思路：先從柱子和荷業(yè)較少的情況開(kāi)始分析，對(duì)多個(gè)因素作分解，找出規(guī)律。1、定義函數(shù)

Jump(s,y)——最多可跳過(guò)河的青蛙數(shù)其中：

s——河中柱子數(shù)

y——荷葉數(shù)2、河中無(wú)柱子：S=0，即Jump(0,y)①y=1時(shí)，河中有一片荷葉，起始時(shí)L上有兩只青蛙，1#在2#上面。第一步：1#跳到荷葉上；第二步：2#從L直接跳至R上；第三步：1#再?gòu)暮扇~跳至R上。

結(jié)論：Jump(0,1)=2；//河中有1片荷葉，能過(guò)2只青蛙。左岸L右岸R荷葉③①②②當(dāng)y=2時(shí)河中有兩片荷葉時(shí)，起始時(shí)：1#，2#，3#-----------共3只青蛙落在L上，第一步：1#從L跳至葉1上，第二步：2#從L跳至葉2上，第三步：3#從L直接跳至R上，第四步：2#從葉2跳至R上，第五步：1#從葉1跳至R上

結(jié)論：

Jump(0,2)=3；//河中有2片荷葉，能過(guò)3只青蛙。左岸L右岸R荷葉2荷葉1④2、河中無(wú)柱子：S=0，即Jump(0,y)①②③⑤小結(jié)：

Jump(0,1)=2；

-------能跳過(guò)2只青蛙

Jump(0,2)=3；

--------能跳過(guò)3只青蛙思考：

Jump(0,3)=?Jump(0,4)=?

Jump(0,y)=?歸納法：Jump(0,y)=y+1含義：沒(méi)有石柱時(shí)，過(guò)河青蛙數(shù)==荷葉數(shù)+13、河中有石柱Jump(S,y)=？一個(gè)最簡(jiǎn)單情況：S=1、y=1時(shí)：1#青蛙從L－>Y；2#青蛙從L－>S；1#青蛙從Y－>S；3#青蛙從L－>Y；4#青蛙從L－>R； 左岸L右岸R荷葉Y石柱S3#青蛙從Y－>R；1#青蛙從S－>Y；2#青蛙從S－>R；1#青蛙從Y－>R；結(jié)論：Jump(1,1)=42*Jump(0,1)=2*2 ①②③④⑤⑥⑦⑧⑨參照漢諾塔問(wèn)題將借助一個(gè)石柱(s=1)、一個(gè)荷葉(y=1)的青蛙跳躍問(wèn)題分成五個(gè)步驟：第一步：借助荷葉將左岸上面的若干青蛙（此時(shí)是1#與2#兩只）跳到石柱上暫存；第二步：左岸下一只青蛙（此時(shí)是3#）跳到荷葉上；第三步：左岸再下一只青蛙（此時(shí)是4#）跳到右岸；第四步：荷葉暫存的青蛙（3#

）跳到到右岸；第五步：石柱上暫存青蛙（1#、2#）借助荷葉完成到跳到右岸。以上的石柱如果看成右岸(步驟1)或左岸（步驟2）的話，進(jìn)一步的分析，還可以將上述五個(gè)步驟分成以下兩個(gè)階段：第一、五兩步實(shí)際上完成的就是青蛙借助一個(gè)荷葉跳躍的過(guò)程，并且這兩步的對(duì)象是同一批青蛙，青蛙個(gè)數(shù)是Jump(0,1)。第二、三、四步實(shí)際上完成的也是青蛙借助一個(gè)荷葉跳躍的過(guò)程，青蛙個(gè)數(shù)是Jump(0,1)。所以：Jump(1,1)的值是Jump(0,1)+Jump(0,1)

即：Jump(1,1)=2*Jump(0,1)；對(duì)于借助s個(gè)石柱、y個(gè)荷葉的青蛙跳躍過(guò)程也可以類(lèi)似的歸納出來(lái)，這個(gè)實(shí)現(xiàn)步驟可以分成七個(gè)步驟：第一步：借助所有荷葉以及其余石柱將左岸上面的若干青蛙跳到第一個(gè)石柱上暫存；第二步：左岸余下的青蛙借助其它可用的石柱以及所有荷葉跳到其它石柱上；第三步：左岸再余下的青蛙跳到所有荷葉上；第四步：左岸再下一只青蛙完成到右岸的直接跳躍------最大1只第五步：荷葉暫存的青蛙完成到右岸的跳躍；第六步：除了第一個(gè)外其余石柱上暫存青蛙完成到右岸的跳躍；第七步：第一個(gè)石柱上暫存的青蛙借助其余石柱以及所有荷葉完成到右岸的跳躍；如果以上的石柱在跳躍過(guò)程中可以看成右岸或左岸，這七個(gè)步驟也可以簡(jiǎn)化成兩個(gè)階段：第一、七兩步實(shí)際上是青蛙借助s-1個(gè)石柱以及y個(gè)荷葉，完成從左岸到第一個(gè)石柱，再到右岸的跳躍的過(guò)程，而這兩步的對(duì)象是同一批青蛙，青蛙個(gè)數(shù)是Jump(s-1,y)。第二步到第六步完成的是左岸的青蛙借助剩余的n-1個(gè)石柱以及所有y個(gè)荷葉跳躍到右岸的過(guò)程，青蛙個(gè)數(shù)是Jump(s-1,y)。結(jié)論：Jump(s,y)是Jump(s-1,y)+Jump(s-1,y)。

即：Jump(s,y)=2*Jump(s-1,y)；注意：當(dāng)石柱數(shù)目為0是不需要遞歸的，此時(shí)跳躍的青蛙數(shù)目為荷葉數(shù)目+1。即遞歸的結(jié)束條件為：Jump(0,y)=y+1;LRYS2876543S1214321例如：荷葉數(shù)是1、石柱數(shù)是2的Jump(2,1)==2*Jump(1,1)=

8intJump(ints,inty)//青蛙過(guò)河—遞歸函數(shù)

{ intk;

if(s==0)

//s=0表示無(wú)石柱,

則為直接可解結(jié)點(diǎn)

k=y+1;

else //

如果

r不為0

,

則要

Jump(r-1,z)

k=2*Jump(s-1,y);

return(k); } #include<stdio.h>voidmain(){ints,y,sum; //s為河中石柱數(shù),y為荷葉數(shù)

printf("請(qǐng)輸入石柱數(shù)s=");

scanf("%d",&s); printf("請(qǐng)輸入荷葉數(shù)y=");

scanf("%d",&y);

sum=Jump(s,y);

printf("Jump(%d,%d)=%d\n",s,y,sum);} 漢諾塔游戲與青蛙跳河的不同1）初始位置、結(jié)束位置不同；2）在漢諾塔游戲中，所搬盤(pán)子總數(shù)n的值決定第一個(gè)盤(pán)子是搬到B、還是搬到C；3）在青蛙跳河中，青蛙總數(shù)n的值不決定第一個(gè)青蛙搬到那個(gè)石柱上。選擇排序、冒泡排序的排序思路比較簡(jiǎn)單，但是排序效率較低，不能滿足需求（比如在OJ或比賽題目中）。效率更高的排序方法呢？快速排序是利用分治遞歸技術(shù)實(shí)現(xiàn)的一種高效的方法。分治法簡(jiǎn)而言之就是“分而治之”，即把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后分解成的子問(wèn)題可以直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。遞歸設(shè)計(jì)實(shí)例3---快速排序?qū)⒁蠼獾妮^大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。分治法思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對(duì)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。分治法思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。快速排序的思想快速排序是基于分治遞歸的思想來(lái)實(shí)現(xiàn)的：1）設(shè)要排序的數(shù)組是a[0]……a[n-1]；2）任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)；3）將所有比關(guān)鍵數(shù)據(jù)小的數(shù)都放到它前面（左），所有比關(guān)鍵數(shù)據(jù)大的數(shù)都放到它后面（右）-----------這個(gè)過(guò)程稱為一趟快速排序。4）對(duì)關(guān)鍵數(shù)據(jù)前、后的數(shù)據(jù)再分別進(jìn)行一趟快速排序，直到參加排序的數(shù)字是一個(gè)為止。一趟快速排序的算法步驟如下：

1）設(shè)置兩個(gè)變量i、j，排序初：i=0，j=n-1；2）以a[0]作為關(guān)鍵數(shù)據(jù)，即key=a[0]；3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索（j=j-1），找到第一個(gè)小于key的值a[j]，將其值賦給a[i]；4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索（i=i+1），找到第一個(gè)大于key的a[i]，將其值賦給a[j]；5）重復(fù)第3）、4）步，直到i==j，此時(shí)將key暫存的值賦給a[i]（或a[j]）；注意：一趟快速排序完成，其結(jié)果是以key作為軸心數(shù)據(jù)，把數(shù)組的原數(shù)據(jù)分為2部分。比key小的數(shù)據(jù)放在key的前面（左），比key大的數(shù)據(jù)放在key的后面（右）。5261734a[0]a[1]a[2]a[3]a[4]a[5]a[6]key52617345>45>25<65>35>15<7一趟快速排序的算法舉例1（從小到大）：ij5這兩個(gè)序列如何排序？?jī)蓚€(gè)小區(qū)間的排序問(wèn)題與原問(wèn)題的性質(zhì)相同，但是規(guī)模更小的問(wèn)題，所以可以用分治遞歸的策略來(lái)完成。50458036156072922578ija[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]key=50過(guò)程1：從后面的元素（j所指）與key進(jìn)行比較，如果a[j]>=key，j往前移動(dòng)（j--），繼續(xù)比較下一個(gè)a[j]，直到遇到小于key的元素停止。將此時(shí)的小于key的a[j]賦值給前面的元素a[i]，即：

a[i]=a[j]，同時(shí)i后移（i++），指向下一個(gè)元素。7825一趟快速排序的算法舉例2（從小到大）：50458036156072922578ija[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]key=50過(guò)程2：從前面的元素（i所指）與key進(jìn)行比較，如果a[i]<=key，i往后移動(dòng)（i++），繼續(xù)比較下一個(gè)a[i]，直到遇到大于key的元素停止。將此時(shí)的大于key的a[i]賦值給前面的元素a[j]，即：a[j]=a[i]，同時(shí)j前移（j--），指向下一個(gè)元素。78254580一趟快速排序的算法舉例2（從小到大）：

50458036156072922578ija[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]key=50重復(fù)上述過(guò)程1與過(guò)程2兩個(gè)步驟，直到下標(biāo)i與下標(biāo)j指向同一元素（即i==j）為止。當(dāng)i==j時(shí)，i(或j)所指的位置就是初始選作關(guān)鍵數(shù)據(jù)key應(yīng)該存放的位置，把key放入該位置?！?一趟快速排序的過(guò)程7825458092jjj726015ii3650一趟快速排序的算法舉例2（從小到大）：

通過(guò)一趟快速排序過(guò)程，以50作為劃分關(guān)鍵元素，把一個(gè)無(wú)序的序列做了重新的元素調(diào)整，變成：

其中在50之前存放的元素都小于等于50，在50之后的存放元素都大于等于50。25，45，15，36,50,60，72，92，80，78一趟快速排序的算法舉例2（從小到大）：

疑問(wèn)：

1）這個(gè)序列還不是一個(gè)完全有序的序列；

2）我們的目標(biāo)是所有元素的排序。25，45，15，36,60，72，92，80，7850,這不是一個(gè)有序的序列但，如果把50之前的4個(gè)元素的排好序，以及元素50之后的5個(gè)元素的排好序，就可得到所有10個(gè)元素的有序序列了。這兩個(gè)序列如何排序？這兩個(gè)區(qū)間的排序問(wèn)題與原問(wèn)題相比較是性質(zhì)相同，但規(guī)模更小的問(wèn)題，所以可以用分治遞歸的策略來(lái)完成。一趟快速排序的算法舉例2（從小到大）：

遞歸不能無(wú)限進(jìn)行下去，當(dāng)劃分的區(qū)間只包含一個(gè)元素時(shí)，該區(qū)間自身一定是一個(gè)有序的區(qū)間，不再做遞歸.-------------遞歸終止的條件。排序的遞歸函數(shù)要以待排序序列的邊界作為參數(shù)，使每次遞歸調(diào)用時(shí)完成不同區(qū)間的排序。假設(shè)以參數(shù)L與參數(shù)r分別作為區(qū)間的左右邊界，

當(dāng)L==r時(shí)表示區(qū)間只有一個(gè)元素，不需要再遞歸。遞歸程序思路如下：當(dāng)左邊界L＜右邊界r時(shí)，作如下操作：1）執(zhí)行一趟快速排序過(guò)程，以i為界形成兩個(gè)子序列，i前所有元素都小于a[i]，i之后的所有元素都大于a[i]；2）對(duì)i之前的區(qū)間做遞歸調(diào)用，左邊界不變，右邊界為i-1；3）對(duì)i之后的區(qū)間做遞歸調(diào)用，左邊界為i+1，右邊界不變。#include<stdio.h>voidqsort(inta[],intL,intr)//從小到大快速排序{ intkey=a[L],i=L,j=r;

//以第一個(gè)數(shù)為一趟快速排序的樞軸元素

if(L>=r)return;//遞歸終止

while(i<j) {while(i<j&&a[j]>key)j--; a[i]=a[j];while(i<j&&a[i]<key)i++; a[j]=a[i]; }

a[i]=key;

qsort(a,L,i-1);//左半?yún)^(qū)間遞歸調(diào)用

qsort(a,i+1,r);//右半?yún)^(qū)間遞歸調(diào)用}voidmain(){inti,a[10]; printf("input10int:"); for(i=0;i<10;i++)scanf("%d",&a[i]);

qsort(a,0,9);//調(diào)用快速排序函數(shù)

for(i=0;i<10;i++)printf("%d",a[i]);

printf("\n");}

快速排序的應(yīng)用排序與查找是最常用的數(shù)據(jù)操作利用分治遞歸的方法可以有效提高排序的效率----------快速排序利用同樣的方法，也可以提高查找的效率：

----------找第k小的數(shù)

----------二分查找（折半查找）例：找第k小的數(shù)輸入n個(gè)數(shù)，找出其中第k(0<k<n)小的數(shù)常用方法：先對(duì)數(shù)組做排序，再找第k個(gè)位置的元素；排好前k個(gè)元素的順序，找到第k小的元素；

--------思路簡(jiǎn)單，但時(shí)間開(kāi)銷(xiāo)大怎么辦？利用類(lèi)似快速排序的思想------分治遞歸

快速排序的啟示一趟快速排序的結(jié)果，以30為軸心，分成兩個(gè)序列，30之前的元素均不大于30，30之后的元素均不小于30.如果需要整個(gè)序列排序，只需對(duì)兩個(gè)子序列分別做遞歸調(diào)用即可?，F(xiàn)在的目標(biāo)是找到其中第k小的元素，有何關(guān)系？30126225803850427016key=30lowhigh16low12low62highhighhighhighhighhigh704250388025low30快速排序的啟示例如：k=4，即要找第4小的元素，有什么發(fā)現(xiàn)？

low==4

high==4如何來(lái)判定？

low==k

high==k30126225803850427016key=30161262high704250388025low30快速排序的啟示如果k=2，怎么辦？在low位置之前的序列進(jìn)行查找性質(zhì)相同但規(guī)模更小的問(wèn)題，可遞歸求解如何表示？如果函數(shù)原型為find(a[],L,r,k)則遞歸調(diào)用形式為：find(a[],L,low-1,k)30126225803850427016161262high704250388025low30快速排序的啟示如果k=7，又怎么辦？在low位置之后的序列進(jìn)行查找性質(zhì)相同但規(guī)模更小的問(wèn)題，可遞歸求解如果函數(shù)原型為find(a[],L,r,k)，k=2時(shí)的遞歸調(diào)用形式為：find(a[],L,low-1,k)，

K=7時(shí)，可寫(xiě)為find(a[],low+1,r,k)30126225803850427016161262high704250388025low30#include<stdio.h>intfind(inta[],intL,intr,intk)//查找第k小數(shù){ intx=a[L],low=L,high=r;//以第一個(gè)數(shù)為樞軸元素

while(low<high) {while(low<high&&a[high]>x)high--;a[low]=a[high];while(low<high&&a[low]<x)low++;a[high]=a[low]; } a[low]=x;if(low==k)returna[low];//遞歸終止

elseif(low>k)find(a,L,low-1,k); //左半?yún)^(qū)間遞歸調(diào)用

elsefind(a,low+1,r,k);//右半?yún)^(qū)間遞歸調(diào)用

returna[k];}

voidmain(){inti,b,a[11];printf("intput10int:");for(i=1;i<11;i++) scanf("%d",&a[i]);

b=find(a,1,10,3);printf("\nb=%d\n",b);}二分查找二分查找：采用跳躍式方式查找，先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。通過(guò)一次比較，將查找區(qū)間縮小一半，再在小區(qū)間查找------二分查找或折半查找。二分查找是一種高效的查找方法，它可以明顯減少比較次數(shù)，提高查找效率。二分查找的數(shù)據(jù)序列必須是有序的序列。二分查找的步驟（升序?yàn)槔〢、取得有序序列的中間位置的數(shù)據(jù)，與待查找的數(shù)據(jù)進(jìn)行比較，如果兩者相等表示找到，查找結(jié)束；B、如果兩者不相等，則存在兩種可能：

（1）中間位置的元素大于待查找的數(shù)據(jù)元素，說(shuō)明如果該元素存在，只可能在中間位置之前的半個(gè)區(qū)間，到前半?yún)^(qū)間做遞歸查找；（2）中間位置的元素小于待查找的數(shù)據(jù)元素，說(shuō)明如果該元素存在，只可能在中間位置之后的半個(gè)區(qū)間，到后半?yún)^(qū)間做遞歸查找；重復(fù)以上A、B過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到區(qū)間不存在為止，此時(shí)查找不成功，查找結(jié)束。二分查找的情況經(jīng)一次查找-----找到的情況；經(jīng)多次查找-----找到的情況；找不到的情況。1、查找一次就找到的情況（查找的元素為45）：10152636456072808596lowhighkey=45low

指示查找區(qū)間的下界;high

指示查找區(qū)間的上界;mid=(low+high)/2。mid45二分查找的情況2、查找多次后找到的情況（以查找元素26為例）：10152636456072808596lowhighkey=26low

指示查找區(qū)間的下界;high

指示查找區(qū)間的上界;mid=(low+high)/2。mid45mid15low26mid二分查找的情況3、查找失敗的情況（以查找元素30為例）：10152636456072808596lowhighkey=30low

指示查找區(qū)間的下界;high

指示查找區(qū)間的上界;mid=(low+high)/2。mid45mid15low26midlow36high二分查找的情況#include<stdio.h>//二分查找intBinsearch(inta[],intL,intr,intkey)//在有序表a[L..r]中進(jìn)行二分查找，成功時(shí)返回找到的值，失敗時(shí)返回-1{ intlow=L,high=r,mid;//置當(dāng)前查找區(qū)間上、下界的初值

if(L<=r)//當(dāng)前查找區(qū)間a[L..r]非空

{mid=low+(high-low)/2;

if(a[mid]==key)

returna[mid];//查找成功返回

if(a[mid]>key)returnBinsearch(a,low,mid-1,key);//繼續(xù)在左半?yún)^(qū)間a[low..mid-1]中遞歸查找

elsereturnBinsearch(a,mid+1,high,key);//繼續(xù)在右半?yún)^(qū)間a[mid+1..high]中遞歸查找

}

return-1;//當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗}voidqsort(inta[],intL,intr)//快速排序{intx=a[L],i=L,j=r;//以第一個(gè)數(shù)為一趟快速排序的樞軸元素

if(L>=r)return;//遞歸終止

while(i<j) {while(i<j&&a[j]>=x)j--; a[i]=a[j]; while(i<j&&a[i]<=x)i++; a[j]=a[i]; } a[i]=x; qsort(a,L,i-1);//左半?yún)^(qū)間遞歸調(diào)用

qsort(a,i+1,r);//右半?yún)^(qū)間遞歸調(diào)用}intmain()//主函數(shù){ inti,n,key,a[10001]; printf("輸入元素個(gè)數(shù)："); scanf("%d",&n);printf("輸入%d個(gè)數(shù)：",n); for(i=0;i<n;i++) scanf("%d",&a[i]); qsort(a,0,n-1);//快速排序

printf("\n%d個(gè)數(shù)據(jù)排序結(jié)果：",n); for(i=0;i<n;i++) printf("%d",a[i]); printf("\n輸入要找的數(shù)值："); scanf("%d",&key);printf("%d\n",Binsearch(a,0,n-1,key));//輸出為-1，表示沒(méi)找數(shù)據(jù)

return0;}用遞歸實(shí)現(xiàn)回溯算法—選講回溯法也叫試探法，每次試著往前走，一直走到不通，然后撤回，重新試探。用遞歸實(shí)現(xiàn)回溯算法的幾個(gè)重要因素(1)狀態(tài):

作為遞歸的值參；(2)邊界條件:

作為遞歸的結(jié)束條件；(3)遞歸范圍:

作為循環(huán)的初值和終值；(4)約束條件:

滿足解的條件；(5)最優(yōu)性要求：滿足最優(yōu)解的條件?！纠?1.9】八皇后問(wèn)題是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。問(wèn)：8個(gè)皇后有多少種擺法？處于同一行、同一列或同一斜線：八皇后問(wèn)題-----一個(gè)解

QQQQQQQQ八皇后---問(wèn)題分析在8×8的棋盤(pán)上擺放8個(gè)皇后，要保證所有皇后不能在同一行、同一列以及同一對(duì)角線上，應(yīng)該采用試探的方式，即：“試著擺著往后走，碰壁后回頭重新擺”的策略。定義函數(shù)queen(i)----試探擺放第i行上的皇后；在第i行上擺放的皇后應(yīng)該在1—8中的某一列，此時(shí)要檢測(cè)擺放的安全性；由于8個(gè)皇后是逐行擺放的，因此不會(huì)存在一行擺放多個(gè)皇后的情況，不需考慮同行皇后的攻擊問(wèn)題；帶來(lái)攻擊的可能是在同列以及同一對(duì)角線上出現(xiàn)--安全性檢查。①同一列的攻擊情況的處理：數(shù)組q[i]表示第i

行上的皇后所在的列位置;若j==q[i]表示第i

行上皇后放在第j列。為了測(cè)試該列是否可以放皇后，定義標(biāo)記數(shù)組c[j]；

c[j]=0-----表示第j列之前已有皇后，不能再放；

c[j]=1-------表示第j列之前未有皇后，可以放皇后，并且放完之后使c[j]的賦值為0，表示以后不能再放。八皇后問(wèn)題---安全性檢查②同一對(duì)角線攻擊情況的處理：要考慮在第i行第j列所在的對(duì)角線的安全性，首先要表示出（i，j）位置所在的兩條對(duì)角線的特點(diǎn)。經(jīng)過(guò)（i，j）的兩條對(duì)角線的特征：

1）從左上到右下一條對(duì)角線上每個(gè)位置的行下標(biāo)與列下標(biāo)之差是同一個(gè)常數(shù);右圖：左上到右下的對(duì)角線滿足i–j=-1，

2)從左下到右上的一條對(duì)角線上的每個(gè)位置的行下標(biāo)與列下標(biāo)之和是同一常數(shù)。右圖：左下到右上的對(duì)角線滿足i+j=7。八皇后問(wèn)題---安全性檢查②同一對(duì)角線攻擊情況的處理：定義從左上到右下對(duì)角線L----標(biāo)記數(shù)組

\；定義從左下到右上對(duì)角線R----標(biāo)記數(shù)組

/

；L[i–j+9]、R[i+j]的值為0----表示對(duì)角線上已經(jīng)有皇后，不能再放；L[i–j+9]、R[i+j]的值為1----表示對(duì)角線兩條對(duì)角線上沒(méi)有皇后，可以放一個(gè)，并且放完之后要使兩個(gè)數(shù)組元素的賦值為0，表示以后不能再放。綜合：在棋盤(pán)上位置（i，j）放皇后的安全條件表述為：Flag=c[j]&&L[i–j+9]&&R[i+j]；為了能夠正確利用三個(gè)標(biāo)記數(shù)組，應(yīng)該在使用之前進(jìn)行合理的初始化：①

數(shù)組c[j]---表示列---數(shù)組元素初始化為1，j=1，2，…，8；②數(shù)組L[k]---表示\---數(shù)組元素初始化為1，k=i–j+9，k=2，3，……，16；③數(shù)組R[m]---表示/---數(shù)組元素初始化為1，m=i+j，m=2，3，……，16；（3）如果在（i，j）上，對(duì)應(yīng)三個(gè)標(biāo)記數(shù)組的元素值全為1，說(shuō)明該位置（i，j）現(xiàn)在是安全的，就可以將皇后放在（i，j）的位置上---第i個(gè)皇后放在第j列，再做下面工作：①用q數(shù)組存放皇后，賦值q[i]=j，表示第i行皇后放在第j列；②三個(gè)標(biāo)記數(shù)組對(duì)應(yīng)元素狀態(tài)改變，表示對(duì)應(yīng)位置變?yōu)椴话踩?----不能再放皇后；即：c[j]=0；L[i–j+9]=0；R[i+j]=0；（3）如果在（i，j）上，對(duì)應(yīng)三個(gè)標(biāo)記數(shù)組的元素值全為1，說(shuō)明該位置（i，j）現(xiàn)在是安全的，就可以將皇后放在（i，j）的位置上---第i個(gè)皇后放在第j列，再做下面工作：③檢查i的值是否為8，如果為8，表明已經(jīng)放完8個(gè)皇后，這時(shí)方案總數(shù)計(jì)數(shù)加1，輸出此種方案下每行的皇后在棋盤(pán)上的位置；否則，未到8個(gè)，還要讓皇后數(shù)i加1，再試著放下一行的皇后，要遞歸調(diào)用函數(shù)queen(i+1)。④由于是尋求所有的方案，當(dāng)一個(gè)方案輸出之后，要回溯。即將先前放的皇后從棋盤(pán)取走，看看是否還有另一處位置也可存放。取走皇后時(shí)，要將原來(lái)由于擺放該皇后使得三個(gè)標(biāo)記數(shù)組的元素值的改變撤銷(xiāo)，即恢復(fù)該位置的安全狀態(tài)。#include<stdio.h>//八皇后問(wèn)題intnum;//統(tǒng)計(jì)方案數(shù)目intq[9];//記錄每行皇后所在的列號(hào)intc[9];//標(biāo)記當(dāng)前列是否安全，值取0（不安全）或1(安全)intL[17];//標(biāo)記左上到右下的對(duì)角線是否安全，值取0（不安全）或1(安全)intR[17];//標(biāo)記左下到右上的對(duì)角線是否安全，值取0（不安全）或1(安全)voidqueen(inti){intj,k;for(j=1;j<=8;j++)