2005noi冬令營吳夢游先生

1《夢游先生》題目描述 給定一個2n×2n（0≤n≤15）的方格矩陣，夢游先生從起點(1,1)出發(fā)，遍歷完畢所有方格以后到達(dá)終點(1,2n)，遍歷規(guī)則如下： 1）n=0時，起點即是終點。 2）n>0時，夢游先生將矩陣劃分成4個2n–1× 2n–1的子矩陣，它在徹底遍歷完畢其中一個 子矩陣以后才會開始下一個子矩陣的遍歷?，F(xiàn)在的問題是，給定整數(shù)x,y（1≤x,y≤2n）問你夢游先生在第幾步跨入方格(x,y)?說明：起點（1,1）算作夢游先生的第0步。2

n=0時，遍歷路線如圖：n=1時，遍歷路線如圖：n=2時，遍歷路線如圖：1212

12341234例如：113n=3時，遍歷路線如圖：

12345678123456784

n起點終點總方格數(shù)

0（1，1）（1，1）11（1，1）（1，2）42（1，1）（1，4）163（1，1）（1，8）644（1，1）（1，16）2565（1，1）（1，32）10246（1，1）（1，64）40965

方格矩陣

2nx2n

P(n)---終點的列號

p12481632640123456Sum(n)---總方格數(shù)

sum1416642561024409601234566

search(n,x,y)在2n×2n矩陣中，從起點（1，1）到點（x,y）的移動步數(shù)。尋找search(n,x,y)與search(n-1,x,y)的關(guān)系

7

n=2n=1A1234y12y1122a3x4CBDxbcd

8

1234n=21a點x<=p[n-1]2y<=p[n-1]3(x,y)----(2,1)4n=112A點1（x,y)----(1,2)2search(2,2,1)search(1,1,2)9

對于search(n,x,y),if(x<=p[n-1]&&y<=p[n-1])returnsearch(n-1,y,x)10

1234對于b點，從（1，1）到1（4，2）的步數(shù)，可等2效為n=1時從（1，1）3到（2，2）（即B點）4的步數(shù)，再加上4。

這時須將坐標(biāo)改為12x=x-p[n-1]

1y=y211對于search(n,x,y),if(x>p[n-1]&&y<=p[n-1])returnsearch(n-1,x-p[n-1],y)+sum(n-1);12

1234對于c點，從（1，1）到1（4，3）的步數(shù)，可等2效為n=1時從（1，1）3到（2，1）（即C點）4的步數(shù)，再加上8。

這時須將坐標(biāo)改為

12x=x-p[n-1]1y=y-p[n-1]213

對于search(n,x,y),if(x>p[n-1]&&y>p[n-1])returnsearch(n-1,x-p[n-1],y–p[n-1])+2*sum(n-1);141234對于d點，從（1，1）到1（1，3）的步數(shù)，可等2效為n=1時從（1，1）3到（2，2）（即D點）4的步數(shù)，再加上12。

這時須將坐標(biāo)改為

12x=p[n]+1-y1y=p[n-1]+1-x215

對于search(n,x,y),if(x<=p[n-1]&&y>p[n-1])returnsearch(n-1,p[n]+1-y,p[n-1]+1-x)+3*sum(n-1);16#include<iostream>usingnamespacestd;intm=0;intnn=0,xx=0,yy=0,p[20],sum[20];voidinit(){ //cout<<"n="; cin>>nn; //cout<<"x="; cin>>xx; //cout<<"y="; cin>>yy; p[0]=1;sum[0]=1; for(inti=1;i<=4;i=i+1) { p[i]=(p[i-1]<<1); sum[i]=p[i]*p[i]; }}17intsearch(intn,intx,inty){ if(n==0)return0;if((x<=p[n-1])&&(y<=p[n-1])) returnsearch(n-1,y,x);if((x<=p[n-1])&&(y>p[n-1])) return(search(n-1,p[n]+1-y,p[n-1]+1-x)