رابطه بازگشتی — از صفر تا صد (+ دانلود فیلم آموزش رایگان)

۲۱۱۰۹ بازدید
آخرین به‌روزرسانی: ۰۱ آبان ۱۴۰۲
زمان مطالعه: ۱۱۴ دقیقه
رابطه بازگشتی — از صفر تا صد (+ دانلود فیلم آموزش رایگان)

رابطه بازگشتی معادله‌ای است که اصطلاحاً از بازگشت برای ربط دادن عبارات موجود در یک دنباله یا عناصر یک آرایه استفاده می‌کند. این رابطه راهی برای تعریف یک دنباله یا آرایه برحسب عبارات خودش است. روابط بازگشتی (Recurrence Relations) کاربردهای فراوانی در زمینه‌های مختلف ریاضیات دارند؛ از جمله:

997696
محتوای این مطلب جهت یادگیری بهتر و سریع‌تر آن، در انتهای متن به صورت ویدیویی نیز ارائه شده است.

روابط بازگشتی وقتی مورد استفاده قرار می‌گیرند که ارائه یک رویکرد جامع برای حل مسئله دشوار باشد. اگرچه یافتن و محاسبه عبارات با استفاده از عبارات قبلی کاری ایده‌آل نیست، اما این رویکرد را می‌توان به عنوان جایگزینی کارآمد برای محاسبات در نظر گرفت.

گاهی می‌توان یک رابطه بازگشتی را با تعریف جملات یک دنباله برحسب اندیس‌های آن و نه جملات قبلی حل کرد. با این کار می‌توان به یک فرم بسته برای هر جمله از دنباله رسید که ما را از استفاده از فرایندهای تکراری بی‌نیاز می‌کند.

تشکیل رابطه بازگشتی

روابط بازگشتی برای کاهش مسائل پیچیده به یک فرایند تکراری مبتنی بر نسخه‌های ساده‌تر مسئله به کار می‌روند. جورچین برج هانوی (Tower of Hanoi) مسئله‌ای معروف است که روابط بازگشتی در حل آن کاربرد دارند.

جورچین برج هانوی از سه میله عمودی و چندین صفحه (دیسک) دایره‌ای با اندازه‌های مختلف تشکیل شده است. هر صفحه یک سوراخ در مرکز دارد تا به راحتی از میله‌ها عبور کند.

برج هانوی
یک جورچین برج هانوی با ۸ دیسک

قوانین این جورچین به صورت زیر است:

  • جورچین با قرار گرفتن همه صفحه‌ها روی یک میله آغاز می‌شود. ترتیب صفحه‌ها این‌گونه است که بزرگ‌ترین آن‌ها در زیر قرار می‌گیرد و کوچک‌ترین در رو.
  • هدف جورچین این است که همه صفحات در یک میله دیگر قرار داده شوند.
  • هر دفعه فقط یک صفحه اجازه حرکت دارد و صفحه‌ها در هر دفعه روی میله‌‌ها قرار داده می‌شوند.
  • هر صفحه را می‌توان در یک میله خالی یا روی یک صفحه بزرگ‌تر قرار داد.

عبارت Tn T_ n را به عنوان حداقل تعداد حرکت‌های لازم برای حل یک جورچین با nn صفحه تعریف می‌کنیم. مشخص نیست که یک راه‌حل بازگشتی برای این مسئله کارگشا باشد. با وجود این، مواردی درباره مسئله وجود دارد که آن را یک گزینه مناسب برای حل با رابطه بازگشتی قرار می‌دهد.

تعریف یک مسئله برای حل با استفاده از رابطه بازگشتی به صورت زیر است:

  • مسئله را می‌توان به نسخه‌های ساده‌تر کاهش داد.
  • مقدار عددی nn برای شناسایی هر مورد وجود دارد. برای جورچین برج هانوی، این مقدارِ عددی، تعداد صفحات است.
  • اگر مقدار عددی افزایش یابد، پیچیدگی مسئله زیاد می‌شود. وقتی تعداد صفحات در مسئله برج هانوی افزایش پیدا کند، یافتن جواب برای آن دشوارتر خواهد بود.

هدف ما در مسئله جورچین برج هانوی، یافتن رابطه بازگشتی Tn T _ n است. به جای تلاش برای حل یک معمای پیچیده (مانند نمونه‌ای که دارای 8 صفحه بالا است)، اغلب بهتر است با ساده‌ترین نسخه ممکن مسئله شروع کنیم.

گام ۱: تعریف یک نسخه پایه 

ساده‌ترین نسخه جورچین برج هانوی، تنها شامل یک دیسک است.

برج هانوی ساده

اگر بخواهیم مسئله را طبق رابطه بازگشتی بنویسم، داریم: n=1 n = 1 . همچنین، T1=1 T_ 1 = 1 ، زیرا تنها یک حرکت لازم است تا همه دیسک‌ها به میله دیگر منتقل شوند.

بدیهی است که نسخه پایه مسئله، اغلب بسیار ساده است. البته لازم است موارد پیچیده‌تر را نیز بنویسیم. حتی اگر هدف مسئله یافتن رابطه‌ای برای Tn T_n باشد، سریعاً نمی‌توان گفت که این معادله به چه شکلی خواهد بود. لازم است برای این کار مسئله را تکرار کنیم. بعد از آنکه دو مورد را کامل کردیم، می‌توانیم بفهیمیم که شکل رابطه بازگشتی چگونه است.

گام ۲: انجام موارد پیچیده‌تر 

شکل زیر جواب جورچین برج هانوی را برای n=2 n = 2 نشان می‌دهد.

برج هانوی

از شکل بالا در می‌یابیم که T2=3 T_ 2 = 3 .

جواب جورچین برج هانوی برای  n=3  n = 3 نیز در شکل زیر نشان داده شده است.

برج هانوی

از شکل بالا مشخص است که T3=7 T_ 3 = 7 .

در صورت لزوم، می‌توانیم همین‌گونه ادامه داده و موارد پیچیده‌تر مسئله را بنویسیم. هدف این فرایند، فهمیدن این موضوع است که مسئله چگونه پیش می‌رود و چگونه می‌توان رابطه بازگشتی را تشکیل داد.

اگرچه در مثال بالا دو مورد را بررسی کردیم، گاهی لازم است موارد بیشتری را برای افزایش درک مسئله انجام دهیم. با مشاهده دو مورد بالا، احتمالاً می‌توانیم دریابیم که چه رابطه‌ای وجود دارد.

گام ۳: نوشتن رابطه بازگشتی

می‌خواهیم ببینیم تکرارها چه رابطه‌ای با هم دارند. در n=1 n = 1، مسئله ساده بود و با یک حرکت جورچین کامل شد. برای n=2 n = 2 ، دیسک کوچک‌تر را باید قبل از دیسک بزرگ‌تر جابه‌جا می‌کردیم تا امکان حرکت آن وجود داشته باشد. پس از حرکت دیسک بزرگ‌تر، دیسک کوچک‌تر را روی آن قرار دادیم و مسئله حل شد. در حالت n=3 n = 3، دیسک‌های کوچک‌تر را قبل از حرکت دیسک بزرگ‌تر جابه‌جا کردیم. پس از آن باید دیسک‌های کوچک‌تر را روی دیسک بزرگ‌تر قرار می‌دادیم تا جورچین کامل شود. اگر بخواهیم این موارد را برحسب nn بیان کنیم، داریم:

  • باید تعداد Tn1 T_ {n-1} حرکت انجام دهیم تا دیسک‌های کوچک‌تر را از روی دیسک بزرگ‌تر برداریم.
  • باید ۱ حرکت انجام دهیم تا دیسک بزرگ‌تر را در میله قرار دهیم.
  • باید Tn1 T _ {n-1} حرکت انجام دهیم تا دیسک‌های کوچک‌تر را روی دیسک بزرگ‌تر قرار دهیم.

در کل، تعداد جابه‌جایی‌ها برای nn دیسک برابر است با:‌

Tn+1=2Tn+1. \large T _ { n + 1 } = 2 T _ { n } + 1 .

می‌توان تأیید کرد که رابطه بازگشتی بالا با مقادیری که در اختیار داریم سازگاری دارد:

T1=1T2=2T1+1=2(1)+1=3T3=2T2+1=2(3)+1=7. \large \begin {aligned} T _ 1 & = 1 \\ T _ 2 & = 2 T _ 1 + 1 = 2 ( 1 ) + 1 = 3 \\ T _ 3 & = 2 T_ 2 + 1 = 2 ( 3 ) + 1= 7 . \end {aligned}

رابطه بازگشتی مربوط به جورچین برج هانوی، مثالی از یک رابطه بازگشتی خطی است. این رابطه را می‌توان با استفاده از روش‌هایی به فرم بسته نوشت.

حل رابطه بازگشتی با توابع مولد

یک روش برای حل روابط بازگشتی استفاده از یک تابع مولد است. تابع مولد (Generating Function) یک سری توانی است که ضرایب آن متناظر با جملات دنباله‌ای از اعداد است.

مثال ۱

از تابع مولد TnT_n استفاده کرده و فرم بسته Tn T _ n را برای مثال بالا بنویسید.

حل: رابطه بازگشتی که به دست آوردیم، به صورت زیر است:

Tn+1=2Tn+1. \large T _ { n + 1 } = 2 T _ {n } + 1 .

از قبل می‌دانیم که T1=1 T_1 = 1، اما لازم است مقدار T0T_0 را نیز بدانیم. با قرار دادن T0=0T_0 = 0 رابطه بازگشتی هنوز برقرار است.

تابع مولد زیر را تعریف می‌کنیم:

T(x)=n=0Tnxn=T0+T1x+T2x2+. \large \begin {aligned} T ( x ) & = \sum \limits _ { n = 0 } ^ { \infty } T _ n x ^ n \\ \\ & = T _ 0 + T _ 1 x + T _ 2 x ^ 2 + \cdots . \end{aligned}

که در آن، T0=0T_0 = 0 . هر دو طرف رابطه بالا را بر xx تقسیم کرده و داریم:

T(x)x=T1+T2x+T3x2+=n=0Tn+1xn. \large \begin {aligned} \frac { T ( x ) } { x } & = T _ 1 + T _ 2 x + T _ 3 x ^ 2 + \cdots \\ \\ & = \sum \limits _ { n = 0 } ^ { \infty } T _ { n + 1 } x ^ n . \end {aligned}

اکنون رابطه بازگشتی Tn+1 T _ { n + 1 } را در معادله جایگذاری می‌کنیم:‌

T(x)x=n=0(2Tn+1)xn=2T(x)+n=0xn. \large \begin {aligned} \frac { T ( x ) } { x } & = \sum \limits _ { n = 0 } ^ { \infty } ( 2 T _ { n } + 1 ) x ^ n \\ \\ & = 2 T ( x ) + \sum \limits _ { n = 0 } ^ { \infty} x ^ n . \end {aligned}

اگر x<1 |x|<1، آنگاه یک تصاعد هندسی نامتناهی داریم که مقدار آن برابر است با:

n=0xn=11x, x<1. \large \sum \limits _ { n = 0 } ^ { \infty } x ^ n = \frac { 1 } { 1 - x } , \ \, | x | < 1 .

با جایگذاری عبارت بالا، داریم:‌

T(x)x=2T(x)+11x, x<1. \large \frac { T ( x ) } { x } = 2 T ( x ) + \frac { 1 } { 1 - x } , \ \, | x | < 1 .

حاصل T(x)T(x) را می‌توان به صورت زیر نوشت:

T(x)=x(1x)(12x), x<1. \large T ( x ) = \frac { x } { ( 1 - x ) ( 1 - 2 x ) } , \ \, | x | < 1 .

اکنون فرم بسته عبارت تابع مولد به دست آمده و باید فرم بسته Tn T_ n را بنویسیم. از آنجایی که تابع مولد برابر با یک عبارت گویا با عوامل دوجمله‌ای در مخرج است، می‌توانیم از گسترش به کسرهای جزئی استفاده کنیم:

T(x)=x(1x)(12x)=x(212x11x). \large \begin {aligned} T ( x ) & = \frac { x } { ( 1 - x ) ( 1 - 2 x ) } \\ \\ & = x \left ( \frac { 2 } { 1 - 2 x } - \frac { 1 } { 1 -x } \right ) . \end {aligned}

تصاعد هندسی نامتناهی را به یاد آورید. برای گام بعدی، دو عبارت گویا را با استفاده از اتحادها به فرم سری توانی بر می‌گردانیم:

212x=n=02n+1xn11x=n=0xn. \large \begin {aligned} \frac { 2 } { 1 - 2 x } & = \sum \limits _ { n = 0 } ^ { \infty } { 2 ^ { n + 1 } x ^ n } \\ \\ \frac { 1 } { 1 - x } & = \sum \limits _ { n = 0 } ^ { \infty } x ^ n . \end {aligned}

با جایگذاری این اتحادها، داریم:

T(x)=x(n=02n+1xnn=0xn)=n=0(2n+11)xn+1=n=1(2n1)xn. \large \begin {aligned} T ( x ) & = x \left ( \sum \limits _ { n= 0 } ^ { \infty } { 2 ^ { n + 1 } x ^ n } -\sum \limits _ { n = 0 } ^ { \infty } x ^ n \right ) \\ \\ & = \sum \limits _ { n = 0 } ^ { \infty } { ( 2 ^ { n + 1 } - 1 ) x ^ { n + 1 } } \\ \\ & = \sum \limits _ { n = 1 } ^ { \infty } { ( 2 ^ { n } - 1 ) x ^ { n } } . \end {aligned}

در نتیجه، بدیهی است که ضریب تابع مولد (سری TnT_n) برابر است با:‌

Tn=2n1. \large \boxed { T _ n = 2 ^ { n } - 1 } .

چند نوجوان با کوله پشتی ایستاده (تصویر تزئینی مطلب رابطه بازگشتی)

حل رابطه بازگشتی با عوامل مجموع‌یابی

راه دیگری برای حل روابط بازگشتی به فرم Aan=Ban1+C A a _ n = B a _ { n - 1 } + C وجود دارد که در آن، AA، BB و CC توابعی از nn هستند. این روش با نام روش عوامل مجموع‌یابی (Summation Factors) شناخته می‌شود. از این روش برای حل مسئله جورچین برج هانوی استفاده می‌کنیم.

مثال ۲

نشان دهید فرم بسته رابطه بازگشتی Tn=2Tn1+1 T_n = 2 T_{n-1} + 1 به صورت Tn=2n1 T_n = 2 ^n -1 است (فرض کنید T0=0T_0 = 0 ).

حل: عامل مجموع‌یابی sns_n با A(n)=1 A(n)=1 و B(n)=2B(n) =2 برابر است با:

sn=111222=12n1, \large s _ n = \frac { 1 \cdot 1 \cdot \cdots \cdot 1 } { 2 \cdot 2 \cdot \cdots \cdot 2 } = \frac { 1 } { 2 ^ { n - 1 } } ,

که در آن، 11 و 22 به تعداد n1n-1 بار تکرار شده‌اند. با ضرب رابطه بالا در رابطه بازگشتی، خواهیم داشت:

12n1Tn=12n2Tn1+12n1. \large \frac { 1 } { 2 ^ { n - 1 } } T _ n = \frac { 1 } { 2 ^ { n- 2 } } T _ { n - 1 } + \frac { 1 } { 2 ^ { n -1 } } .

فرض می‌کنیم، bn=12n1 b _ n = \dfrac { 1 } { 2 ^ { n - 1 } } . در نتیجه، bn1=12n2Tn1 b _ { n - 1 } = \dfrac { 1 } { 2 ^ { n - 2 } } T _ { n - 1 } و b0=1201T0 b _ 0 = \dfrac { 1 } { 2 ^ { 0 - 1 } } T _ 0 . در نتیجه، خواهیم داشت:

bn=bn1+12n1. \large b _ n = b _ { n - 1 } + \frac { 1 } { 2 ^ { n - 1 } } .

بنابراین، فرم بسته bn b_n به صورت زیر خواهد بود:

bn=0+k=1n12k1=1(12)n1121=212n1. \large b _ n = 0 + \sum _ { k = 1 } ^ n \frac { 1 } { 2 ^ { k - 1 }} = \frac { 1 \cdot \left ( \frac 1 2 \right ) ^ n - 1 } { \frac 1 2 - 1 } = 2 - \frac { 1 } { 2 ^ { n - 1 } } .

همان‌طور که می‌بینیم، مجموع بالا، یک دنباله هندسی متناهی است. اما از آنجایی که bn=12n1Tn b _ n = \frac {1} {2^{n-1}} T_n، فرم بسته Tn T_n به صورت زیر خواهد بود:

Tn=2n1(212n1)=2n1. \large T _ n = 2 ^ { n - 1 } \left ( 2 - \frac { 1 } { 2 ^ { n - 1 } } \right ) = \boxed { 2 ^ n - 1}.

رابطه بازگشتی خطی

یک رابطه بازگشتی خطی مرتبه kk یا درجه kk، معادله‌ای بازگشتی به فرم زیر است:

xn=A1xn1+A2xn2+A3xn3+Akxnk \large x _ n = A _ 1 x _ { n - 1 } + A _ 2 x _ { n -2} + A _ 3 x _ { n - 3 } + \dots A _ k x _ { n - k }

که در آن، Ak A_k یک ثابت است و  Ak0 A_k \neq 0 .

مثال‌هایی از معادله‌های بازگشتی خطی به شرح زیر است:

روابط بازگشتیمقادیر اولیهجواب‌ها
Fn=Fn1+Fn2 F _ n = F _ { n-1} + F _ {n-2} F1=F2=1 F _ 1 = F _ 2 = 1 دنباله فیبوناچی
Fn=Fn1+Fn2 F _ n = F _ { n-1} + F _ { n -2 } F1=1 F_1 = 1 و F2=3F _ 2 = 3 دنباله لوکاس
Fn=Fn2+Fn3 F _ n = F _ {n-2} + F _ {n-3} F1=F2=F3=1 F _ 1 =F_2=F_3=1دنباله پادوان
Fn=2Fn1+Fn2 F _n = 2 F _ {n-1} + F _ {n-2}F1=0 F_1 = 0 و F2=1 F_2 = 1 دنباله پِل

حل رابطه بازگشتی خطی

فرض کنید رابطه بازگشتی خطی مرتبه دوم  Fn=AFn1+BFn2 F_n = AF_{n-1} +BF_{n-2} را داشته باشیم که در آن، A A و B B اعدادی حقیقی هستند.

معادله مشخصه رابطه بازگشتی بالا به صورت زیر است:

 x2AxB=0 \large x^2 - Ax - B = 0

سه حالت در یافتن ریشه‌ها ممکن است رخ دهد:

  • حالت اول: اگر این معادله به صورت  (xx1)(xx1)=0 (x- x_1)(x- x_1) = 0 تجزیه شده و دو ریشه حقیقی متمایز x1 x _ 1 و x2 x _ 2 داشته باشد، آنگاه جواب  Fn=ax1n+bx2n F_n = ax_1^n+ bx_2^n است که در آن، a a و b b اعداد ثابتی هستند.
  • حالت دوم: اگر معادله به صورت  (xx1)2=0 (x- x_1)^2 = 0 بوده و داری ریشه تکراری x1 x _ 1 باشد، آنگاه جواب  Fn=ax1n+bnx1n F_n = a x_1^n+ bn x_1^n است.
  • حالت سوم: اگر ریشه‌های معادله، اعداد مختلط مجزای x1 x _1 و x2 x _ 2 به فرم قطبی  x1=rθ x_1 = r \angle \theta و  x2=r(θ) x_2 = r \angle(- \theta) باشند، آنگاه جواب Fn=rn(acos(nθ)+bsin(nθ)) F_ n = r ^ n ( a \cos ( n \theta ) + b \sin ( n \theta ) ) خواهد بود.
یک معلم با یک کاغذ در دست جلوی تخته ای پر از عدد (تصویر تزئینی مطلب رابطه بازگشتی)

مثال ۳

رابطه بازگشتی Fn=5Fn16Fn2F_n = 5F_{n-1} - 6F_{n-2} را حل کنید که در آن،  F0=1 F_0 = 1 و  F1=4 F_1 = 4 .

حل: معادله مشخصه دنباله بازگشتی به صورت زیر است:

 x25x+6=0, \large x^2 - 5x + 6 = 0,

بنابراین،  (x3)(x2)=0 (x - 3) (x - 2) = 0. در نتیجه، ریشه‌های آن x1=3 x _1 = 3 و x2=2 x _ 2 = 2 هستند. همان‌طور که می‌بینیم، ریشه‌ها حقیقی و مجزا هستند. بنابراین، جواب برابر است با:

 Fn=ax1n+bx2n \large F_n = ax_1^n + bx_2^n

وقتی x1=3 x _1=3 و x2=2 x_2=2، آنگاه Fn=a3n+b2nF_n=a3^n+b2^n. در نتیجه:

1=F0=a30+b20=a+b \large 1 = F _ 0 = a 3 ^ 0 + b 2 ^ 0 = a + b

4=F1=a31+b21=3a+2b \large 4 = F _ 1 = a 3 ^ 1 + b 2 ^ 1 = 3 a + 2 b

با حل این معادلات، جواب‌های a=2a=2 و b=1 b = -1 را به دست خواهیم آورد.

بنابراین، جواب نهایی برابر است با:

Fn=23n+(1)2n=23n2n \large F _ n = 2 \cdot 3 ^ n + ( - 1 ) \cdot 2 ^ n = 2 \cdot 3 ^ n - 2 ^ n

مثال ۴

رابطه بازگشتی  Fn=10Fn125Fn2 F_n = 10F_{n-1} - 25F_{n-2} را حل کنید که در آن،  F0=3 F_0 = 3 و  F1=17 F_1 = 17 .

حل: معادله مشخصه رابطه بازگشتی به صورت زیر است:‌

x210x25=0 \large x ^ 2 - 1 0 x - 2 5 = 0

بنابراین، داریم:  (x5)2=0 (x - 5)^2 = 0 . از آنجایی که یک ریشه تکراری داریم، جواب به صورت زیر خواهد بود:

Fn=ax1n+bnx1n \large F _ n = a x _ 1 ^ n + b n x _ 1 ^ n

با توجه به رابطه بالا، می‌توان معادلات زیر را نوشت:

3=F0=a50+b050=a \large 3 = F _ 0 = a \cdot 5 ^ 0 + b \cdot 0 \cdot 5 ^ 0 = a

17=F1=a51+b151=5a+5b \large 17 = F _ 1 = a \cdot 5 ^ 1 + b \cdot 1 \cdot 5 ^ 1 = 5 a + 5 b

با حل معالات اخیر، مقادیر a=3 a=3 و b=2/5 b = 2/5 به دست می‌آیند.

در نهایت، جواب برابر با Fn=35n+(2/5)n2n F _ n = 3 \cdot 5 ^ n + ( 2 / 5 ) \cdot n \cdot 2 ^ n است.

مثال ۵

رابطه بازگشتی  Fn=2Fn12Fn2 F_n = 2F_{n-1} - 2F_{n-2} را حل کنید که در آن، F0=1 F _ 0 = 1 و F1=3 F_1 = 3 .

حل: معادله مشخصه رابطه بازگشتی به صورت زیر است:

x22x2=0 \large x^2 -2x -2 = 0

ریشه‌های معادله بالا،  x1=1+i x_1 = 1 + i و  x2=1i x_2 = 1 - i هستند. این ریشه‌ها را می‌توان به فرم قطبی  x1=rθ x_1 = r \angle \theta و  x2=r(θ) x_2 = r \angle(- \theta) نوشت که در آن،  r=2 r = \sqrt 2 و  θ=π4 \theta = \frac{\pi}{4} . از آنجایی که ریشه‌های معادله مشخصه مختلط هستند، جواب را می‌توان به صورت زیر نوشت:

Fn=(2)n(acos(nπ/4)+bsin(nπ/4)) \large F _ n = ( \sqrt 2 ) ^ n ( a \cos ( n \pi / 4 ) + b \sin ( n \pi / 4 ) )

با توجه به معادله بالا، داریم:

1=F0=(2)0(acos(0π/4)+bsin(0π/4))=a \large 1 = F _ 0 = ( \sqrt 2 ) ^ 0 ( a \cos ( 0 \pi / 4 ) + b \sin ( 0 \pi / 4 ) ) = a

3=F1=(2)1(acos(1π/4)+bsin(1π/4))=2(a/2+b/2) \large 3 = F _ 1 = ( \sqrt 2 ) ^ 1 ( a \cos ( 1 \pi / 4 ) + b \sin ( 1 \pi / 4 ) ) = \sqrt 2 ( a / \sqrt 2 + b / \sqrt 2 )

با حل معادلات بالا، a=1 a=1 و b=2 b = 2 به دست می‌آید.

بنابراین، جواب نهایی برابر است با:

Fn=(2)n(cos(nπ/4)+2sin(nπ/4)) \large F _ n = ( \sqrt 2 ) ^ n ( \cos ( n \pi / 4 ) + 2 \sin ( n \pi / 4 ) )

یک نوجوان نشسته در کتابخانه در حال خواندن کتاب و فکر کردن

رابطه بازگشتی ناهمگن

یک رابطه بازگشتی را ناهمگن می‌گوییم، اگر به فرم زیر باشد:

Fn=AFn1+BFn2+f(n) \large F _ n = A F _ { n - 1 } + B F _ { n - 2 } + f ( n )

که در آن،  f(n)0 f(n) \ne 0 .

رابطه بازگشتی همگن متناظر با رابطه ناهمگن بالا به صورت زیر است:

Fn=AFn1+BFn2 \large F _ n = A F _ { n – 1 } + B F _ { n - 2 }

جواب an a _ n یک رابطه بازگشتی ناهمگن دو بخش دارد. بخش اول، جواب ah a _ h متناظر با رابطه بازگشتی همگن متناظر و بخش دوم جواب خصوصی ata_t است:

an=ah+at \large a _ n = a _ h + a _ t

جواب بخش اول را می‌توان با روندی که در بالا آن را توضیح دادیم، به دست آورد. اما برای یافتن جواب خصوصی، یک جواب آزمایشی را به دست می‌آوریم. فرض کنید  f(n)=cxn f(n) = cx^n. با در نظر گرفتن  x2=Ax+B x^2 = Ax + B به عنوان معادله مشخصه متناظر با رابطه بازگشتی همگن و x1 x _1 و x2x_2 به عنوان ریشه‌های آن،‌ می‌توانیم عبارات زیر را بنویسم:

  • اگر  xx1 x \ne x_1 و  xx2 x \ne x_2 ، آنگاه  at=Axn a_t = Ax^n .
  • اگر  x=x1 x = x_1 و xx2x \ne x_2 ، آنگاه at=Anxna_t = Anx^n .
  • اگر  x=x1=x2 x = x_1 = x_2 ، آنگاه at=An2xna_t = An^2x^n .

مثال ۶

رابطه بازگشتی ناهمگن  Fn=AFn1+BFn2+f(n) F_n = AF_{n–1} + BF_{n-2} + f(n) را با ریشه‌های معادله مشخصه x1=2 x _ 1 =2 و x2=5 x _ 2 = 5 در نظر بگیرید. جواب‌های آزمایشی (Trial) ممکن مقادیر f(n) f (n) به صورت زیر هستند:

f(n)\large f (n)
جواب‌های آزمایشی
44AA
52n 5 \cdot 2 ^ nAn2nAn2^n
85n8\cdot 5 ^nAn5nAn5^n
4n4^nA4nA4^n
 2n2+3n+12n^2+3n+1An2+Bn+CAn^2 + B n + C

مثال ۷

رابطه بازگشتی  Fn=3Fn1+10Fn2+75n F_n = 3F_{n-1} + 10F_{n-2} + 7\cdot 5^n را حل کنید که در آن، F0=4F_0 = 4 و  F1=3 F_1 = 3 .

حل: این رابطه، یک رابطه بازگشتی ناهمگن است که معادله همگن مرتبط با آن،  Fn=3Fn1+10Fn2 F_n=3F_{n-1}+10F_{n-2} بوده و داریم:  f(n)=75n f(n)=7 \cdot 5^n .

معادله مشخصه رابطه همگن متناظر به صورت زیر است:‌

 x23x10=0 \large x^2 - 3x -10 = 0

یا

(x5)(x+2)=0 \large (x - 5)(x + 2) = 0

یا

 x1=5\large  x_1= 5 و x2=2 \large x_2 = -2 .

بنابراین، ah=a.5n+b.(2)na_h = a.5^n + b.(-2)^n ، که در آن، a a و bb اعداد ثابتی هستند.

از آنجایی که  f(n)=7.5n f(n) = 7.5^n ، یعنی  c.xn c.x^n ، یک جواب آزمایشی مستدل آن،  Anxn Anx^n است.

 at=Anxn=An5n \large a_t = Anx^n = An5^n

بعد از قرار دادن جواب در رابطه بازگشتی، داریم:

An5n=3A(n1)5n1+10A(n2)5n2+75n \large A n 5 ^ n = 3 A ( n – 1 ) 5 ^ { n - 1 } + 1 0 A ( n – 2 ) 5 ^ { n - 2 } + 7 \cdot 5 ^ n

با تقسیم هر دو طرف بر  5n2 5^{n-2} ، خواهیم داشت:

An52=3A(n1)5+10A(n2)50+752 \large A n 5 ^ 2 = 3 A ( n - 1 ) 5 + 1 0 A ( n - 2 ) 5 ^ 0 + 7 \cdot 5 ^ 2

در نتیجه، A=5A=5 به دست می‌آید.

بنابراین، Fn=An5n=5n5n=n5n+1F_n = An5^n= 5n5^n=n5^{n+1}.

جواب رابطه بازگشتی به صورت زیر است:

Fn=ah+at=a5n+b(2)n+n5n+1 \large F _ n = a _ h + a _ t = a \cdot 5 ^ n + b \cdot ( - 2 ) ^ n + n 5 ^ { n + 1 }

با جایگذاری مقادیر  F0=4 F_0 = 4 و F1=3 F_1 = 3  در معادله بالا، مقادیر a=2 a = -2 و b=6 b = 6 به دست می‌آیند. بنابراین، جواب رابطه بازگشتی مورد نظر، برابر است با:

Fn=n5n+1+6(2)n25n \large F _ n = n 5 ^ { n + 1 } + 6 ( - 2 ) ^ n - 2 \cdot 5 ^ n

فیلم‌ های آموزش رابطه بازگشتی — از صفر تا صد (+ دانلود فیلم آموزش رایگان)

فیلم آموزشی تشکیل رابطه بازگشتی

دانلود ویدیو

فیلم آموزشی حل رابطه بازگشتی با توابع مولد

دانلود ویدیو

فیلم آموزشی حل رابطه بازگشتی با عوامل مجموع‌یابی

دانلود ویدیو

فیلم آموزشی حل رابطه بازگشتی با تبدیل Z

دانلود ویدیو

فیلم آموزشی رابطه بازگشتی خطی و نامتغیر

دانلود ویدیو

فیلم آموزشی رابطه بازگشتی ناهمگن

دانلود ویدیو
بر اساس رای ۴۷ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
BrilliantTutorialspoint
۴ دیدگاه برای «رابطه بازگشتی — از صفر تا صد (+ دانلود فیلم آموزش رایگان)»

واقعا افرین به شما درجه یک یک بود افرین

سلام سپاسگزارم
برای من کمی گنگ بود ولی ممنونم. استفاده کردم

واقعا مننون از فرادرس
اکثرا مطالب رو اینجا یاد می گیرم

سلام.
خوشحالیم که مطالب مجله فرادرس برایتان مفید بوده است.
سالم و موفق باشید.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *