تالار گفتمان مانشت

محاسبه کدام تابع با روش برنامه ریزی پویا می تواند میزان محاسبات مورد نیاز را نسبت به روش بازگشتی بیش از بقیه کاهش دهد؟
[tex]F(n)=\sum_{i=1}^{n-1} F(i)[/tex]
[tex]F(n)=aF(n-1) b[/tex]
[tex]F(n)=aF(n-1) bF(n-2)[/tex]
[tex]F(n)=aF(\left \lfloor n/2 \right \rfloor) bF(\left \lceil n/2 \right \rceil)[/tex]

به نظر من اولی میشه چون به ازای هر n باید n-1 تابع بازگشتی دیگه حل کنیم یعنی یه درخت با درجه n-1 که فکر کنم از مرتبه n^n باشه وقتی با پویا حل کنیم اول f(1) رو حساب میکنیم و توی A[1 میریزیم (آرایه) بعد از روی اون f(2) رو حساب میکنیم و الی آخر مرتبش میشه
n-1+n-2+.....+1 =n(n-1)/2

(28 دى 1389 11:52 ق.ظ)afagh1389 نوشته شده توسط: [ -> ]به نظر من اولی میشه چون به ازای هر n باید n-1 تابع بازگشتی دیگه حل کنیم یعنی یه درخت با درجه n-1 که فکر کنم از مرتبه n^n باشه وقتی با پویا حل کنیم اول f(1) رو حساب میکنیم و توی A[1 میریزیم (آرایه) بعد از روی اون f(2) رو حساب میکنیم و الی آخر مرتبش میشه
n-1+n-2+.....+1 =n(n-1)/2

آفاق خانم از TeX استفاده نمایید. ببینید چقدر کاربردش آسونه و خوانایی رو افزایش می‍ده!
[tex]n-1 n-2 ... 1 = \frac{n(n-1))}{n}[/tex]

در مورد این سولات باید خوب دقت کنید که کدوم تابع بازگشتی بیشتر زیر مسائل یکسان تولید میکنه زیر در مسائلی که به کمک برنامه نویسی پویا حل میشه هر زیر مسئله ای که حل میشه در مکانی از حافظه ذخیره میشه تا اگه به زیر مسئله سبیه اون برخورد کردیم دوباره اونو حل نکنیم‌، با توجه به این توضیح بدترین حالت مورد اوله‌، مورد دوم هم توی هر سطح a تا زیر مسئله شبیه هم تولید میکنه که بهتر از مورد اوله‌، مرد اخر هم تقزیبا خوبه و بهتر از مورد اول و دومه زیرا a+b تا زیر مسئله شبیه هم تولید میکنه‌، اما مورد سوم از همه بهتره توی سطح اول b تا زیر مسئله به انداره n-2 و a تا مسئله به اندازه n-1 که توی سطح بعد همین زیر مسائل با اندازه n-1 هر کدومشون b تا زیر مسئله با اندازه n-1 تولید میکنند در نتیجه همین مورد سوم بیشترین زیر مسائل شبیه هم رو تولید میکنه

(28 دى 1389 02:38 ب.ظ)امیدوار نوشته شده توسط: [ -> ]در مورد این سولات باید خوب دقت کنید که کدوم تابع بازگشتی بیشتر زیر مسائل یکسان تولید میکنه زیر در مسائلی که به کمک برنامه نویسی پویا حل میشه هر زیر مسئله ای که حل میشه در مکانی از حافظه ذخیره میشه تا اگه به زیر مسئله سبیه اون برخورد کردیم دوباره اونو حل نکنیم‌، با توجه به این توضیح بدترین حالت مورد اوله‌، مورد دوم هم توی هر سطح a تا زیر مسئله شبیه هم تولید میکنه که بهتر از مورد اوله‌، مرد اخر هم تقزیبا خوبه و بهتر از مورد اول و دومه زیرا a+b تا زیر مسئله شبیه هم تولید میکنه‌، اما مورد سوم از همه بهتره توی سطح اول b تا زیر مسئله به انداره n-2 و a تا مسئله به اندازه n-1 که توی سطح بعد همین زیر مسائل با اندازه n-1 هر کدومشون b تا زیر مسئله با اندازه n-1 تولید میکنند در نتیجه همین مورد سوم بیشترین زیر مسائل شبیه هم رو تولید میکنه

ذخیره سازی در حافظه در مسائل بازگشتی می تونه مورد استفاده قرار بگیره. در روش پویا ذخیره سازی صورت نمی گیره. اگر هم منظورتون ذخیره سازی در ثبات هاست که اون در اداره کامپایلر هست و ارتباطی به الگوریتم اش نداره

نخیر بی جی بو جی جان !!! اتفاقا تو الگوریتم های پویاست که ذخیره سازی صورت می گیره .

من با پارسانا موافقم چون مثلا فیبوناچی رو با استفاده از ذخیره در آرایه بدست میاریم.

ما زمانی از پویا استفاده میکنیم که خوب خیلی مایلیم از جواب های قبلی استفاده کنیم یا یه دلیل خودمونی هم بگم اینکه زیرمسئله‌ها دیر رشد میکنند درست مثل گزینه های 2 و3 من باشم بین 2 و3 شک میکنم اما مطمئنا 3 رو انتخاب میکنم
تو مورد اول ما از n تا تابع مستقل استفاده می کنیم و حلقه که تموم شد برنامه به پایان میرسه.
در مورد 4 هم باید بگم این اصل تقسیم و غلبه هستش و بیشتر نخودیه
اما بین 2 و3 3 زیر مسائل بیشتر شبیه هم داره و اگه درخت رو رسم کنیم می بینم که چقدر وابسته به جواب های قبلیه حالا ضرایب a,b ثابت هست و مهمترین مورد خود n هستش

نه توی گزینه 1 توابع مستقل نیست یه چیزی تو مایه فیبوناچی فقط به جای دو عدد قبلی n-1 عدد قبلی رو جمع میزنه!