صفحه‌ها: ۱ ۲
پیچیدگی t(n)=t(n-1)+t(n-2)+2 چی میشه ؟ لطفا با راه حل بگید.
این سوال دو جور هست
۱- تو بازگشتی بدند
۲-مرتبه زمانی بخواند
من دومی رو توضیح میدم
بگو عزیز
خب وقتی مرتبه بخواهند نیاز به مقادیر اولیه نیست ولی اگه حل رابطه بازگستی مدنظر بود مقادیر اولیه میخواستیم که اونم راحته
اما مرتبه زمانی به صورت زیر بدست می اید
![[تصویر: 148035_1_1379087281.jpg]](https://img.manesht.ir/148035_1_1379087281.jpg)
بدست اوردن مرتبه راهای زیادی داره هرکس با تمرین میتونه قلقش بیاد دستش که کی از چه راهی استفاده کنه
بقیه هم نظر بدن آیا درسته ؟
چون مرتبه میخواهیم لازم نیست دقیق حلش کنیم (مگر اینکه صورت سوال بگه)
یکی از روش های که جواب دقیق نمیده ولی جواب تقریب درست میده روش درخت بازگشت هست
ما در بدترین حالت فرض میکنیم دو شاخه درخت(T(n-1 باشند که میشه دوتا (T(n-1 در اینصورت باتوجه به فرمول ساده ای که هست بقیش راحت بدست میاد
در بهترین حالت هم فرض میکنیم دو شاخه درخت(T(n-2 باشند که میشه دوتا (T(n-2
یجور دیگه هم میتونم حلش کنم
از طریق بازگشتی حلش کنی چطور؟
خب فکر میکنی یک مساله که جوابش بشه این رابطه بازگشتی پیدا میکنی از رو اون مساله مقادیر اولیه رو پیدا میکنی و طبق روابط بازگشتی حلش میکنی
تو راهیان ارشد گفته:
الف)متجانس:
[tex]t(n)=at(n-1) bt(n-2)[/tex]
اینو که میشه با معادله مشخصه حل کرد:
[tex]t(n)=c_{1}x_{1}^{n} c_{2}x_{2}^{n}[/tex]
ب)نا متجانس:
[tex]t(n)=at(n-1) bt(n-2) cF(n)[/tex]
گفته باید طرفین رو در ضریبی ضرب کنیم تا معادله ی بازگشتی مرتبه ی ۲ حاصل شود.
در رابطه ی اول n را به n+1 تبدیل کنیم تا معادله سوم حاصل شود.
معادله ی دوم را از سوم کم می کنیم.
تا رابطه به صورت مرتبه ی دوم متجانس بدست بیاید و نهایتا آنرا طبق قوانین مربوط حل می کنیم.
===
اما من بلد نیستم
اگه کسی با این روش بلده حل کنه بذاره
من با فرض ثابت بودن عدد ۲ حل کردم و تو مساله هم از ۲ صرف نظر کردم
ما همیشه از اعداد ثابت تو درخت بازگشت صرف نظر میکنیم حتی اگه ۱۰۰۰ هم بود برامون اینجا مهم نیست چون ما تابع نمایی داریم!!!!!! روش فکر کن سوال داشتی بپرس
ببین اینجا رابطه بازگشتی داریم که بافرض نبودن ۲ میشه رابطه بازگشتی درجه دوم هست که وقتی حلش میکنی نمایی میشه
دوستان عزیز که لطف می کنید جواب میذارید دستتون درد نکنه، اما من فقط مقدار رو نمیخوام،جواب رو با راه حل و اثبات کامل میخوام. اونم راه حلش رو بالا آوردم . یکی با راه حل خودم توضیح بده.
درسته اصلا حواسم نبود این دنباله فیبوناچی هست که یک ۲ اضافه داره.
تابع مشخصه برای قسمت همگن [tex]r^{2}-r-1=0[/tex] دو ریشه داره
[tex]r=\frac{1 \sqrt{5}}{2}[/tex]
و
[tex]r=\frac{1-\sqrt{5}}{2}[/tex]
قسمت ناهمگن هم به این شکل هست [tex](r-1)[/tex]
جواب کلی
[tex]t(n)=c1(\frac{1 \sqrt{5}}{2})^{n} c2(\frac{1 \sqrt{5}}{2})^{n} c3(1)^{n}[/tex]
با چی حل کردی؟ فصل بازگشتی پوران(یوسفی)؟ رابطه ی نا همگن ؟(f(n)<>0 ؟ )
اقسمت اول جوایتون قطعن درسته ولی قسمت ناهمگن جای بحث داره کسی میتونه رو این قسمت نوضیح بزاره
اقا حل کنید من امروز امتحان زبان داشتم ذهنم خسته هست بعدن جئواباتون رو میخونم
موفق باشید
(۱۹ آذر ۱۳۹۱ ۱۱:۵۷ ب.ظ)csharpisatechnology نوشته شده توسط: با چی حل کردی؟ فصل بازگشتی پوران(یوسفی)؟ رابطه ی نا همگن ؟(f(n)<>0 ؟ )
با استفاده از معادله مشخصه .تو همه کتابها هست.
تو پوران هم کامل هست حل این نوع بازگشتی ها.
من با استفاده از پوران یادش گرفتم و راه حل کاملشو تا چند لحظه دیگه میذارم.