الگوریتم بازگشتی شمارش تعداد درخت با n گره

[mahdi bg]

سلام
الگوریتم بازگشتی شمارش تعداد درخت با n گره
رو میخواستم
فقط الگوریتم رو هو بگین کافیه
ممنون

[whitehat]

شما کافیه یکی از پیمایش های درخت را بروش بازگشتی پیاده سازی کنید، تابع شما باید تعداد فرزندان نود فعلی را برگرداند ، شرط خروج زمانی است که به نود برگ می رسیم و تابع باید صفر برگرداند. برای هر نود ابتدا زیر درخت چپ و سپس زیر درخت راست را پیمایش کنید و جوابهای بدست آمده را با هم جمع کنید

[mahdi bg]

سلام
تنها چیزی که می دونونیم این که درخت ما n تا گره داره
تابعی که با دونستن n گره , تعداد درخت رو بده
مثلا 1 گره 1 درخت
2 گره 2 درخت
3 گره 6 درخت و ...

[whitehat]

تابعی که با دونستن n گره , تعداد درخت رو بده
دوست عزیز اگه شما می خواهید ببینید با n گره چند درخت می توانید بسازید باید با استفاده از فرمول Cayley (http://en.wikipedia.org/wiki/Cayley%27s_formula) آنرا پیدا کنید و نیازی به پیمایش ندارید.
موفق باشید

[mahdi bg]

سلام
قبلش از توجه هتون ممنون
ولی صورت سوالی که من دارم اینه
"تابعی به صورت بازگشتی بنویسید که تعداد درخت های موجود با
N گره را پیدا کند"

فکر نکنم منظور سوال استفاده از فرمول فوق باشه
راستش رو بخواهید چند وقته روش فکر می کنم و خودم هم هنوز
این که دقیقا چی میخواد ؛ نمی دونم

کسی پیشنهاد دیگه ای نداره ممنون

[404_3140]

خب مگه بازگشتی نوشتنش کاری جز این داره:؟


int f(int x){
if(x==1)
return 1;
if(x%2==0)
return 0;
int ans=0;
for(int i=1;i<x;i+=2)
ans+=f(i)*f(x-1-i);
return ans;
}