سلام دوستان
من درس طراحی الگوریتم مبحث معادلات بازگشتی و غیر بازگشتی رو دارم
میشه بگین از کجا بدونیم یه معادله ای
۱- همگن است
۲- ناهمگن است
۳- خطی است
۴ - غیر خطی است
لطفا با مثال توضیح بدین ممنون
تا اونجایی که من می دونم منظور از همگن و ناهمگن بودن اینه که اگه جملات دارای روابط بازگشتی رو یه طرف ببری طرف دیگت چیزی باقی نمونه. یعنی همه جملاتت جمله های بازگشتی باشن مثل این:
[tex]T(n)=T(n-1) 5*T(n-2)[/tex]
می بینی اگه همرو یه سمت ببری (جملات بازگشتی رو) طرف دیگت صفر می مونه پس این همگنه حالا مثالهای پایین رو ببین
[tex]T(n)=T(n-1) 5T(n-2)-1[/tex]
[tex]T(n)=T(n-1) 5T(n-2) 3^{n}[/tex]
[tex]T(n)=T(n-1) 5T(n-2)-cos(n) 2[/tex]
می بینی که تو معادلات ناهمگن جملات اضافی دیگه هم هست که حلش سختر از معادلات همگنه. بعضیاش قابل حله و برای حلش فرم خاصی وجود داره.
معادلات خطی هم منظورش اینه که آیا جملات بازگشتی ما خطی هستند یا نه مثلا این خطیه
[tex]T(n)=T(n-1) 5T(n-2) 3[/tex]
می بینی که جملات بازگشتی یعنی T ها به فرم ضرب یه عدد با اون جملست که به معنای خطی بودنه اما تو غیر خطی به این فرم نیست یعنی جملات بازگشتی Tها در یه جمله دیگه ضرب شده یا به تون رسیده و ... مثلا
[tex]T(n)=T(n-1)^{2} 4[/tex]
[tex]T(n)=T(n-1)*T(n-2)[/tex]
من متوجه نشدم چطوری یعنی یه سمت ببری
خوب الان از کجا بدونیم معادله های زیر (همگن ، ناهمگن ، خطی ، یا غیر خطی )هستن
![[تصویر: 172281_1_1379084521.png]](https://img.manesht.ir/172281_1_1379084521.png)
از دوستان یکی منو کمک کنه
من توضیح دادم دقت نکردی. گفتم اون جمله هایی که t دارن رو ببر یه سمت. مگه معادله دو سمت نداره چپ و راست. همه جملات t رو ببر سمت چپ و بقیه سمت راست. اگه سمت راستت صفر بود یعنی همگنه درغیر این صورت ناهمگن. مثل معادله اول که میشه
[tex]t(n)-2t(n-1) 2t(n-2)=0[/tex]
که همگنه چون طرف راست صفره
معادله دومم همگنه مثل بالایی سمت راست صفر میشه. بعد بردن جملات t به سمت چپ
معادله سوم و چهارم ناهمگنن چون غیر جملات بازگشتی t جملات دیگه ای هم دارن n به اضافه دو به توان n و سه به توان n .
معادلاتی خطی هستند که اگر جملات بازگشتیت (t ها) ضریبشون فقط عدد بود میشن خطی
اینجا همه معادلات خطی هستند. چون همه ضریب t ها عدد هستند.
برای معادله یک: ۱و۲- و ۲
برای دومی: ۱و۵-و۸و۴-
سومی: ۱و۲-
چهارمی: ۱ و -۲
اینجا هیچکدوم از جملات t به توان نرسیدند یا مثلا در یه جمله دیگه ضرب نشدند که بشن غیرخطی.
اگه ببینی ضریب همشون فقط عدده پس خطین
در ضمن نوشتی tn فکر کنم منظورت n زیرنویسه یعنی در t که ضرب نشده. اون n اه منظور جمله n ام هست.
ممنون ازت داداش فهمیدم
معادله ۴ رو که بالا نوشتم حل میکنی و کمی توضیح میدی البته زیر دیپلم یاد بده
(۲۸ فروردین ۱۳۹۲ ۰۴:۵۵ ب.ظ)vahidir نوشته شده توسط: ممنون ازت داداش فهمیدم
معادله ۴ رو که بالا نوشتم حل میکنی و کمی توضیح میدی البته زیر دیپلم یاد بده
سلام
ببین دوست عزیز اول دو تا یادآوری و نکته :
[tex]\sum_{i=1}^{n}i=1 2 3 4 5 \cdots n=\frac{n(n 1)}{2}[/tex]
[tex]\sum_{i=0}^{n}a^i=a^0 a^1 a^2 \cdots a^n=\frac{a^{n 1}-1}{a-1}[/tex]
پس طبق این دو نکته میتوانیم نتیجه بگیریم که :
[tex]\sum_{i=2}^{n}i=(\sum_{i=1}^{n}i)-1=2 3 4 5 \cdots n=\frac{n(n 1)}{2}-1[/tex]
همچنین داریم :
[tex]\sum_{i=2}^{n}a^i=(\sum_{i=0}^{n}a^i)-a^0-a^1=a^2 a^3 a^4 \cdots a^n=\frac{a^{n 1}-1}{a-1}-a^0-a^1[/tex]
حال به حل رابطه بازگشتی : [tex]T_n=T_{n-1} n 2^n[/tex] میپردازیم و فرض میکنیم : [tex]T_1=1[/tex]
با توجه به رابطه بازگشتی میتوان چنین نوشت [tex]T_n-T_{n-1}=n 2^n[/tex] و آن را مکرر بسط داد.
[tex]T_n-T_{n-1}=n 2^n[/tex]
[tex]T_{n-1}-T_{n-2}=n-1 2^{n-1}[/tex]
[tex]T_{n-2}-T_{n-3}=n-2 2^{n-2}[/tex]
[tex]T_{n-3}-T_{n-4}=n-3 2^{n-3}[/tex]
[tex]\vdots[/tex]
[tex]T_{2}-T_{1}=2 2^{2}[/tex]
حال اگر تمامی این بسط ها را با هم جمع کنیم خواهیم داشت :
[tex]T_n-T_1=(n 2^n) (n-1 2^{n-1}) \cdots (2 2^2)=\sum_{i=2}^{n}i \sum_{i=2}^{n}2^i[/tex]
حال با توجه به نکته ابتدایی که خدمتتان گفتم داریم :
[tex]T_n-T_1=\sum_{i=2}^{n}i \sum_{i=2}^{n}2^i=(\frac{n(n 1)}{2})-1 (\frac{2^{n 1}-1}{2-1})-2^0-2^1\Rightarrow T_n=\frac{n(n 1)}{2} {2^{n 1}-4}[/tex]