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