تاریخچه ی:
روابط بازگشتی اولیه
||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]
#@^