PDA

View Full Version : سوال نمودار درختی تابع بازگشتی(کنکوری)



babakgm
پنج شنبه 14 آذر 1387, 15:06 عصر
با توجه به برنامه زیر مقدار bin 6.4 کدام است؟


int bin(int n,int k)

if (k = =0 |n==k) l
retrun 1
else
return bin(n-1,k-1)+bin(n-1,k);l



جواب 15 میشود و نمودار درختی زیر به صورت زیر استhttp://hbsystem.persiangig.com/untitled.JPG
اما سوال من چگونه جواب سوال 15 شده چرا نمودار درختی ار برگ bin 4.3 یا bin 4.4 ادامه پیدا نکرده؟ یا چرا bin 3.2 جوابش 3 شده؟ در صورتی که bin 4.4 یک شده

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

الهام 1366
پنج شنبه 14 آذر 1387, 22:51 عصر
bin4.4 رو محاسبه نمي كنه چون n==k ميشه و از حلقه خارج ميشه . با توجه به
(if (k = =0 |n==k وقتي n==k ميشه 1 رو return ميكنه.
در مورد اينكه چرا bin4.3 رو محاسبه نميكنه : به نظرم براي اينه كه جوابشو در مرحل قبل به دست آورده. bin4.3 به bin3.2+bin3.3تبديل ميشه كه جوابشو قبلا به دست آورده 3+1=4
اين درخت داراي زير مسايل مشترك تكراري مثل دنباله فيبونانچي. اول درخت رو مي كشي بعد از پايين شروع به پر كردن ميكني.

whitehat
جمعه 15 آذر 1387, 10:32 صبح
جواب دوستمان کاملا صحیح است، همیشه در مسائل کنکوری سعی کنید فقط مواردی را پیدا کنید که آنها را ندارید. وقتی مثلا مقدار تابع 4و3 را دارید پس نیازی ندارید دوباره درخت را بسط دهید. راه حل تشریحی این مسئله یک درخت با پنج سطح به شکل زیر است

bin(6,4)=bin(5,3)+bin(5,4)
--
1) bin(5,3)=bin(4,2)+bin(4,3)
1) bin(5,4)=bin(4,3)+bin(4,4)
--
2) bin(4,2)=bin(3,1)+bin(3,2)
2) bin(4,3)=bin(3,2)+bin(3,3)

2) bin(4,3)=bin(3,2)+bin(3,3)
2) bin(4,4)=1
--
3) bin(3,1)=bin(2,0)+bin(2,1)
3) bin(3,2)=bin(2,1)+bin(2,2)

3) bin(3,2)=bin(2,1)+bin(2,2)
3) bin(3,3)=1

3) bin(3,2)=bin(2,1)+bin(2,2)
3) bin(3,3)=1
--
4) bin(2,0)=1
4) bin(2,1)=bin(1,0)+bin(1,1)

4) bin(2,1)=bin(1,0)+bin(1,1)
4) bin(2,2)=1

4) bin(2,1)=bin(1,0)+bin(1,1)
4) bin(2,2)=1
--
5) bin(1,0)=1
5) bin(1,1)=1

5) bin(1,0)=1
5) bin(1,1)=1

5) bin(1,0)=1
5) bin(1,1)=1