منو
 صفحه های تصادفی
چشمک زن
امتیاز تنباکو
معادله شرودینگر
معجزه
هوش مصنوعی I
واژه نامه آبشناسی
امام جواد علیه السلام و معرفی امامان پس از خود
بازي هاي كامپيوتري
گرافهای اویلری
برگ
 کاربر Online
765 کاربر online
تاریخچه ی: روابط بازگشتی اولیه

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!روابط بازگشتی
---
!!روابط بازگشتی اولیه
آنچه در مباحث قبل درباره دنباله‌ها خواندیم، در حقیقت حالت خاصی از روابط بازگشتی به شمار می‌آید.
همان طور که پیشاپیش گفته شد رابطه‌ای را بازگشتی می‌نامیم که در آن برای محاسبه هر عنصر نیاز به مقادیر تعدادی از عناصر قبلی آن داشته باشیم و براساس آنها بیان شده باشد.
نقطه مقابل رابطه بازگشتی رابطه صریح می‌باشد که در آن با دانستن شماره عنصر مستقیماً مقدار آن توسط تابع صریح آن پیدا می‌گردد.
رابطه بازگشتی را به صورت کلی به صورت
@@{TEX()} {u_n=F(u_{n-1},u_{n-2},\cdots )} {TEX}@@
بیان می‌کنند (اگر {TEX()} {u_i} {TEX}ها عناصر دنباله مزبور باشند).
---
!!رابطه بازگشتی مرتبه 2
به رابطه‌ای به صورت:
@@{TEX()} {x_n=px_{n-1}+qx_{n-2} \qquad (q\neq 0) \ , \ p \in Q} {TEX}@@
رابطه بازگشتی از مرتبه 2 می‌گویند.
دقت کنید {TEX()} {p} {TEX}و {TEX()} {q} {TEX}ضرایب ثابت در این رابطه می‌باشند و اگر چه {TEX()} {q\neq 0} {TEX} است ولی اگر {TEX()} {q} {TEX}را مساوی صفر بگیریم دنباله به یک تصاعد هندسی تبدیل می‌شود.
به طور کلی یک راه برای پیداکردن جواب صریح ((معادلات بازگشتی)) که آن را «حل کردن رابطه بازگشتی»‌ می‌نامند، نخست حدس‌زدن فرم جواب {TEX()} {x_n} {TEX} است.
در این سوال بدون آنکه به شما بگویم چگونه و چرا جوابی به شکل {TEX()} {x_n={\lambda}^n} {TEX} را در نظر می‌گیریم و سعی می‌کنیم {TEX()} {\lambda} {TEX} مناسب را بیابیم تا در رابطه
@@{TEX()} {x_n=px_{n-1}+qx_{n-2}} {TEX}@@
صدق ‌کند.
اگر {TEX()} {\lambda} {TEX} صدق کند خواهیم داشت:
@@{TEX()} {{\lambda}^n=p{\lambda}^{n-1}+q{\lambda}^{n-2}} {TEX}@@
@@{TEX()} {\Rightarrow {\lambda}^2=p\lambda+q} {TEX}@@
@@{TEX()} {\Rightarrow {\lambda}^2-p\lambda-q=0} {TEX}@@
این ((معادله)) را معادله مشخصه آن رابطه می‌نامیم.
@@{TEX()} {\Rightarrow \ {\lambda}_1,{\lambda}_2=\frac{-b\pm \sqrt{\Delta}}{2a}} {TEX}@@
که صرف‌نظر از محاسبه {TEX()} {{\lambda}_1} {TEX} و {TEX()} {{\lambda}_2} {TEX} خواهیم داشت:
@@{TEX()} {x_n=u{\lambda}_1^n+v{\lambda}_2^n} {TEX}@@
آنچه تاکنون آمد اساس حل ((روابط بازگشتی همگن)) و ناهمگن خواهد بود.
---
!!نکته
اگر {TEX()} {{\lambda}_1={\lambda}_2} {TEX} باشد ( ((ریشه مضاعف)) ) آنگاه معادله آیا به صورت
@@{TEX()} {x_n=a{\lambda}_1^n+b{\lambda}_2^n=(a+b){\lambda}_1^n} {TEX}@@
در خواهد آمد؟
خیر. در این صورت جواب صریح معادله به صورت زیر خواهد بود.
@@{TEX()} {x_n=(a+bn){\lambda}^n} {TEX}@@
در رابطه نهایی گفته شده همان طور که دیده می‌شود کماکان {TEX()} {a} {TEX}و {TEX()} {b} {TEX}مجهول‌اند که با مقدارهای اولیه {TEX()} {x_n} {TEX}، می‌توان آنها را پیدا کرد.
!!مثال
داریم
@@{picture=img/daneshnameh_up/d/d5/com0027a.jpg} @@
معادله را حل کنید.
__حل.__
@@{TEX()} {x_n={\lambda}^n \ \Rightarrow \ {\lambda}^n=2{\lambda}^{n-1}+{\lambda}^{n-2} \ \Rightarrow \ {\lambda}^2=2{\lambda}+1 \ \Rightarrow \ {\lambda}^2-2{\lambda}-1=0} {TEX}@@
که با حل این دستگاه {TEX()} {a} {TEX}و {TEX()} {b} {TEX}بدست آمده و در نتیجه رابطه صریح نیز حساب خواهد شد.
قبل از آنکه بیشتر وارد جزئیات حل روابط بازگشتی بشویم به سراغ روابط بازگشتی ساده‌تر می‌رویم.
---
!!مثال
به چند طریق می‌توان صفحه‌ای{TEX()} {2\times n} {TEX}را با موزاییک‌های {TEX()} {2\times 1} {TEX}فرش کرد؟
__حل.__
این مسأله بسیار ساده‌ای است که ممکن است آن را دیده باشید. اگر جدول {TEX()} {2\times n} {TEX} را بتوان{TEX()} {f_n} {TEX} روش مختلف با موازییک‌های{TEX()} {2\times n} {TEX}فرش کرد به راحتی می‌توان ثابت کرد که{TEX()} { f_n=f_{n-1}+f_{n-2}} {TEX} . به این ترتیب اگر در ستون {TEX()} {n} {TEX}ام جدول یک موزاییک{TEX()} {2 \times 1} {TEX} به صورت عمودی گذاشته شود، جدولی{TEX()} {2 \times (n-1)} {TEX}می‌ماند که باید موزاییک‌های{TEX()} {2 \times 1} {TEX} فرش شود که به{TEX()} { f_{n-1} } {TEX} طریق ممکن است. در غیر این صورت دو ستون {TEX()} {n} {TEX}و{TEX()} { n – 1 } {TEX} ام با دو موزاییک {TEX()} {2 \times 1} {TEX} افقی پوشانده شده‌اند. که جدولی{TEX()} {2 \times (n-2)} {TEX}می‌ماند که باید با موزاییک‌های{TEX()} {2 \times 1} {TEX} فرش شود که به {TEX()} {f_{n-2}} {TEX} طریق ممکن است. پس در کل تعداد روش‌های فرش کردن جدول{TEX()} {2 \times n} {TEX} با موزاییک‌های {TEX()} {2 \times 1} {TEX} برابر است با{TEX()} { f_{n-1}+f_{n-2} } {TEX}، یعنی{TEX()} { f_n =f_{n-1}+f_{n-2} } {TEX}. این رابطه، دنباله معروفی را مشخص می‌کند که با مقادیر اولیه {TEX()} {f_0=0} {TEX} و {TEX()} {f_1=1} {TEX} ((دنباله فیبوناچی)) نام دارد.
دقت می‌کنیم که رابطه{TEX()} { f_n = f_{n-1}+f_{n-2} } {TEX}هر عضو دنباله را بر حسب اعضای قبلی بیان می‌کند، مثلاً برای پیدا کردن {TEX()} {f_2} {TEX}می‌توان از رابطه{TEX()} { f_2 = f_0+f_1} {TEX} استفاده کرد و به دست‌ آورد: {TEX()} { f_2 = 0 + 1 = 1} {TEX}. حال به همین ترتیب با جمع{TEX()} { f_1} {TEX} و {TEX()} {f_2} {TEX}می‌توان {TEX()} {f_3} {TEX}را به دست آورد. ضمناً برای ساختن دنباله باید دو عضو اول آن را داشته باشیم تا با استفاده از آنها {TEX()} {f_2} {TEX}و {TEX()} {f_3} {TEX}و همین طور تا {TEX()} {f_n} {TEX}مشخص صوند. حل رابطه بازگشتی به این معناست که ما هر عضو دنباله {TEX()} {f_n} {TEX}را بدون استفاده از اعضای قبلی و مستقل از آن اعضا بیان کنیم،
#@
@#16:
---
!!مثال
{TEX()} {n} {TEX}سکه یکسان 50 تومانی داریم. فرض می‌کنیم{TEX()} {x_n} {TEX}تعداد روش‌هایی باشد که این {TEX()} {n} {TEX}سکه را در دو ردیف افقی روی هم چنان مرتب کنیم که هر سکه در ردیف بالا، دقیقاً در زیر آن قرار گرفته باشند.
مانند:
::{picture=img/daneshnameh_up/9/92/com0027b.jpg}::
برای محاسبه {TEX()} {x_n} {TEX}رابطه بازگشتی بدست آورید.
__حل.__
در ردیف پائین سمت چپ‌ترین سکه را اگر در نظر بگیریم، دو حالت داریم. یا بالا و سمت راست آن سکه‌ای قرار دارد یا نه، که اگر قرار داشته باشد، بجز این دو سکه{TEX()} { n-2} {TEX} سکه دیگر قرار دارند که مستقلاً به{TEX()} { x_{n-2} } {TEX} طریق می‌توانند چیده شوند و اگر قرار نداشته باشد، {TEX()} { n -1} {TEX} سکه درسمت راست آن مستقلاً به{TEX()} { x_{n-1} } {TEX} طریق می‌توانند چیده شوند.
یعنی{TEX()} { x_n = x_{n-1} + x_{n-2} } {TEX}
که این رابطه همان رابطه بازگشتی فیبوناچی است که بعداً بیشتر به آن خواهیم پرداخت. ضمناً در مثال بالا
@@{picture=img/daneshnameh_up/e/ec/com0027c.jpg}{TEX()} { x_1 = 1} {TEX}@@
@@{picture=img/daneshnameh_up/3/3b/com0027d.jpg}{TEX()} { x_2 = 1} {TEX}@@
---
!!مثال
مطلوب است تعیین ((رابطه بازگشتی)) برای تعداد دنباله‌های صفر و یک به طول {TEX()} {n} {TEX}که هیچ دو صفر متوالی ندارند.
__حل__
می‌خواهیم رابطه بازگشتی مناسب برای آن بدست آوریم
فکر می‌کنید این بار باید چگونه بشماریم.
همان‌طور که تاکنون تجربه کسب کرده‌اید، باید به نحوی سایر مسئله را با حذف تعدادی عناصر کوچکتر کرد. در این مثال نیز سمت چپ‌ترین عدد را در نظر می‌گیریم.
اگر جواب مسئله را{TEX()} {S_n} {TEX} بگیریم داریم:
::{picture=img/daneshnameh_up/5/56/com0027e.jpg}::
اگر 1 باشد، آنگاه{TEX()} { n-1 } {TEX} رقم سمت راست آن مستقلاً به {TEX()} {S_{n-1}} {TEX}طریق می‌توانند بنشینند و اگر صفر باشد آنگاه الزاماً رقم دوم یک می‌باشد (چرا؟)
پس {TEX()} { n-2 } {TEX} رقم باقیمانده مستقلاً به{TEX()} {S_{n-2}} {TEX} طریق می‌توانند مقادیر بپزیرند. پس در کل داریم
@@{TEX()} { S_n = S_{n-1} + S_{n-2} } {TEX}@@
و چه زیبا که دوباره به رابطه بازگشتی فیبوناچی رسیدیم
@@{TEX()} { S_1 = 2 \qquad 0 , 1} {TEX}@@
@@{TEX()} { S_2 = 3 \qquad 11 , 10 , 01} {TEX}@@
ولیکن این‌بار عناصر شروع با مقادیر رابطه فیبوناچی تفاوت دارند.
رابطه فیبوناچی به همین جا ختم نمی‌شود؛ به طور کلی در مبحث گسسته این رابطه به دفعات ظاهر می‌شود.
---
!!مثال
در جزیره‌ای تعدادی خرگوش داریم. اگر{TEX()} {S_n} {TEX} را تعداد خرگوش‌ها در سال {TEX()} {n} {TEX}بگیریم، در هر سال خرگوش های بالغ جفت‌گیری کرده و به ازای هر خرگوش بالغ یک نوزاد خرگوش به دنیا می‌آید. نوزادان نیز یک سال طول می‌کشد تا به سن بلوغ برسند. اگر در سال اول تنها یک جفت خرگوش بالغ داشته باشیم، رابطه {TEX()} {S_n} {TEX}را بدست آورید.
__حل.__
تعداد خرگوش‌های سال {TEX()} {n} {TEX}ام برابر است با تعداد خرگوش‌های سال قبل آن به علاوه تعداد بچه‌هایی که به تازگی به دنیا آمده‌اند که این تعداد برابر با تعداد خرگوش‌های بالغ سال قبل بوده و آن هم برابر با کل خرگوش‌های دوسال قبل آن می‌باشد و این یعنی
@@{TEX()} {S_n=S_{n-1}+S_{n-2}} {TEX}@@
و چه زیبا که بازهم به رابطه‌ای معادل با رابطه فیبوناچی ولی با مقادیر اولیه متفاوت رسیدیم.
@@{TEX()} { S_1 = 2} {TEX}@@
@@{TEX()} { S_2 = 4} {TEX}@@
پس از این همه مثال‌هایی که جواب آنها مشابه فیبوناچی می‌بود زمان آن رسیده که سعی کنیم رابطه فیبوناچی را حل کنیم.
اگر چه بعداً حل این گونه روابط را مفسلاً می‌خوانیم ولیکن داریم:
به طور کلی جمله {TEX()} {n} {TEX}ام فیبوناچی را با{TEX()} { F_n } {TEX} نمایش می‌دهند
@@{TEX()} { F_n = F_{n-1} + F_{n - 2} } {TEX} @@
@@{TEX()} { F_1 = F_2 = 1} {TEX}@@
مانند قبل این بار فرض می‌کنیم
{TEX()} {r} {TEX}اعداد ثابت {TEX()} {F_n=r^n} {TEX}
@@{TEX()} {\Rightarrow r^n=r^{n-1}+r^{n-2}} {TEX}@@
@@{TEX()} {\Rightarrow r^2=r+1} {TEX}@@
@@{TEX()} {\Rightarrow r^2-r-1=0} {TEX}@@
@@{picture=img/daneshnameh_up/e/ec/com0027f.jpg} @@
@@{TEX()} { \Rightarrow F_n=ar_1^n+br_2^n} {TEX}@@
@@{TEX()} {\Rightarrow F_n=a \Big( \frac{1+\sqrt{5}}{2} \Big)^n +b \Big( \frac{1-\sqrt{5}}{2} \Big)^n} {TEX}@@
@@ {picture=img/daneshnameh_up/9/9c/com0027g.jpg}@@
@@{TEX()} {\ \Rightarrow a=\frac{1}{\sqrt{5}} \ , \ b= -\frac{1}{\sqrt{5}}} {TEX}@@
@@{TEX()} { \Rightarrow \ F_n=\frac{1}{\sqrt{5}} \Big( \Big( \frac{1+\sqrt{5}}{2} \Big) ^n - \Big( \frac{1-\sqrt{5}}{2} \Big) ^n \Big)} {TEX}@@
اگر از حل این رابطه بازگشتی احساس خوبی پیدا نکردید نگران نباشید.
حل کلی این معادلات جلوتر گفته خواهد شد و اکنون تنها خواستم ذهن شما را درگیر کنم. «ولیکن خداییش حال کردید؟! دیدید فیبوناچی هم رابطه صریح داره اونم با این همه ((رادیکال))، اولش که به ذهن آدم نمی‌رسه».

---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0046.pdf]
---
!همچنین ببینید
*((حل روابط بازگشتی همگن ))
*((حل روابط بازگشتی ناهمگن ))
#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:11 ]   4   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [08:32 ]   3   زینب معزی      v  c  d  s 
 سه شنبه 14 شهریور 1385 [11:52 ]   2   زینب معزی      v  c  d  s 
 سه شنبه 14 شهریور 1385 [11:42 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..