The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

導(dǎo)航

<

2010年4月

>

日

一

二

三

四

五

六

28

29

30

31

1

5

11

26

27

28

29

30

1

2

3

4

5

6

7

8

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評(píng)論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關(guān)燈問題

搜索

閱讀排行榜

評(píng)論排行榜

POJ 1095 卡特蘭數(shù)+dfs

感覺和上次codeforce的第四題有點(diǎn)像，雖然沒做出來，呵呵。
看來枚舉左右子樹這一招還是蠻常用的。其實(shí)我本來想練下卡特蘭數(shù)的，結(jié)果變成練DFS了。
注意遞歸求解左右孩子時(shí)的那兩個(gè)參數(shù)，一定要先加上1，否則就不對(duì)了。

#include<stdio.h>

long long a[20];

long long b[20];

//定理：n個(gè)結(jié)點(diǎn)能形成的二叉樹總數(shù)為卡特蘭數(shù) C(2n,n)/(n+1) 或者由遞推公式Ci+1=2*(2*i+1)/(i+2)*Ci

//設(shè)計(jì)figure(n)，n代表這棵樹整體的偏移量

//分別算出其左右子樹各自的偏移量，遞歸求解即可

//由于先遞歸左兒子，輸出順序與題意相符

void figure(int n)

{

int t,i,j;

if(n==1){printf("X");return;}

j=0;

while(true) if(b[++j]>=n) break;

n=n-b[j-1];//j代表有幾個(gè)結(jié)點(diǎn)，n此時(shí)代表在這些結(jié)點(diǎn)下的序號(hào)

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

{

t=a[i]*a[j-1-i];

if(t>=n) break;

else n=n-t;

}

if(i!=0) //i是此時(shí)左子樹掛的節(jié)點(diǎn)數(shù)

{

printf("(");

figure(b[i-1]+1+(n-1)/a[j-1-i]);//初始的時(shí)刻，只需要增加1，左子樹的偏移量就增加1，而之后的部分，需要右子樹變換a[j-i-1]次，左子樹的偏移量才增加1

printf(")");

}

printf("X");

if(i!=j-1)

{

printf("(");

figure(b[j-2-i]+1+(n-1)%a[j-1-i]);

printf(")");

}

int main()

{

int n;

int i,j;

a[0]=1;

a[1]=1;

b[1]=1;

b[0]=0;

for(i=2;i<20;i++)

{

a[i]=2*(2*(i-1)+1)*a[i-1]/(i+1) ;//卡特蘭數(shù)遞推公式

b[i]=b[i-1]+a[i];

}

while(scanf("%d",&n)&&n)

{

solve(n);

printf("\n");

}

return 0;

}

posted on 2010-04-13 17:33 abilitytao 閱讀(2150) 評(píng)論(5) 編輯收藏引用

評(píng)論

# re: POJ 1095 卡特蘭數(shù)+dfs 2010-04-13 19:37 abilitytao

srand(time(NULL))
是以當(dāng)前到1970年的時(shí)間間隔的秒數(shù)為種子，time(NULL),指不需要保存一個(gè)時(shí)間對(duì)象
通常情況下可以Time tTime;然后time(&tTime)來將這個(gè)時(shí)間獲取到。

而rand()是以剛才生成的種子為基礎(chǔ)來產(chǎn)生一個(gè)隨機(jī)數(shù)，每調(diào)用一次產(chǎn)生一個(gè)數(shù)，貌似如果期間沒有再次調(diào)用srand來生成種子，rand()是接著前面的序列來產(chǎn)生下一個(gè)數(shù)。（個(gè)人想法）
因?yàn)椋?
srand(time(NULL))；
int x = rand();
int y = rand();
x和y的值不一樣。而：
srand(time(NULL));
int x = rand();
srand(time(NULL));
int y = rand();
則是相同，因?yàn)楹笠环N使用了同一個(gè)種子（運(yùn)行期間時(shí)間很短，返回的秒數(shù)相同）回復(fù) 更多評(píng)論

# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 09:49 yoyo

I can understand a[i] stores catalan number when there are i nodes.
but what is b[] used for?

Thanks,
yoyo 回復(fù) 更多評(píng)論

# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 10:59 abilitytao

@yoyo
b[i]=a[1]+a[2]+...a[i]; 回復(fù) 更多評(píng)論

# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 11:19 yoyo

@abilitytao
:-) I can know it from code, while no idea what's the purpose of b[i] = a[1]+...a[i]

Thanks for quick replying.

yoyo 回復(fù) 更多評(píng)論

# re: POJ 1095 卡特蘭數(shù)+dfs 2010-04-16 17:50 abilitytao

@yoyo
the intention is to find the node number of the the tree that you want.
you are not chinese? or you can understand it through my notes by Chinese. 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理