بخشی از پاورپوینت
اسلاید 1 :
حل معادلات بازگشتی با استفاده از معادله شاخص
.1معادلات خطی همگن
n
nمعادله بازگشتی خطی همگن: یک معادله بازگشتی به شکل a0tn+ a1tn-1+…+ aktn-k=0 که در آن k و ai مقادیر ثابت هستند.
n
nمعادله شاخص: برای معادله بازگشتی خطی همگن با ضرایب ثابت, معادله شاخص به صورت زیر تعریف می شود:
a0rk+ a1rk-1+…+ akr0=0
n
nقضیه: اگر معادله شاخص یک معادله بازگشتی دارای k جواب مجزای r1,r2,..,rk باشد, آنگاه تنها جواب معادله به شکل زیر است:
tn= c1r1n+…+ ckrkn
n
اسلاید 2 :
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
nحل معادله:
T(0)=0
T(1)=1
T(n)=3T(n-1)+4T(n-2) , n>1
tn-3tn-1-4tn-2=0
حل معادله شاخص:
r2-3r-4=0 (r-4)(r+1)=0, r=4,-1
تعیین جواب عمومی معادله:
tn=c14n+c2(-1)n
تعیین ثابتها:
t0=0=c140+c2(-1)0 c1+c2=0
t1=1=c141+c2(-1)1 4c1-c2=1 c1=1/5, c2=-1/5
جایگزینی ثابتها:
tn=(1/5)4n-1/5(-1)n
اسلاید 3 :
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
nحل معادله بازگشتی تولید دنباله فیبوناچی:
T(0)=0
T(1)=1
T(n)=T(n-1)+T(n-2) , n>1
tn-tn-1-tn-2=0
حل معادله شاخص:
r2-r-1=0 r=(1+Ö5)/2, (1-Ö5)/2
تعیین جواب عمومی معادله:
tn=c1 [(1+Ö5)/2] n+c2 [(1-Ö5)/2] n
تعیین ثابتها:
c1=1/ Ö 5, c2=-1/ Ö 5
جایگزینی ثابتها:
[(1+ Ö5 )/2 ] n-[(1- Ö5) /2 ] n
اسلاید 4 :
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
nقضیه: اگر r یک ریشه یه توان m معادله شاخص برای معادله بازگشتی خطی همگن با ضرایب ثابت باشد, انگاه:
tn=rn, tn=n rn, tn=n2rn, …, tn=nm-1rn
n
nمثال: حل معادله بازگشتی:
T(0)=0 T(1)=1 T(2)=2
T(n)=7T(n-1)-15T(n-2)+9T(n-3) , n>2
tn-7tn-1+15tn-2-9tn-3=0
حل معادله شاخص:
r3-7r2+15r-9=0 (r-1)(r-3)2=0 r=1,3,3
تعیین جواب عمومی معادله:
tn=c11n+c2 3n+c3 n3n
تعیین ثابتها:
c1=-1, c2=1, c3=-1/3
جایگزینی ثابتها:
tn=-1+ 3n+ n3n-1
اسلاید 5 :
حل معادلات بازگشتی خطی غیرهمگن با استفاده از معادله شاخص
.2معادلات خطی غیرهمگن
¨معادله بازگشتی خطی غیرهمگن: یک معادله بازگشتی به شکل
a0tn+ a1tn-1+…+ aktn-k=f(n) که در آن k و ai مقادیر ثابت هستند و f(n) یک تابع غیر صفر است.
¨حالت خاص: f(n)=bnP(n)
n
¨معادله شاخص: برای معادله بازگشتی خطی غیرهمگن با ضرایب ثابت, معادله شاخص به صورت زیر تعریف می شود:(d درجه P است)
(a0rk+ a1rk-1+…+ akr0)(r-b)d+1=0
n
اسلاید 6 :
حل معادلات بازگشتی خطی غیرهمگن با استفاده از معادله شاخص
nمثال: حل معادله:
T(0)=0
T(n)=T(n-1)+n-1 , n>0
tn-tn-1=n-1
حل معادله شاخص:
(r-1)(r-1)2=0 (r-1)3=0 r=1,1,1
تعیین جواب عمومی معادله:
tn=c11n+c2 n 1n+c3 n2 1n
تعیین ثابتها:
t0= c1=0 t1=c1+c2+c3 =0 t2=c1+2c2+4c3 =1 c2=-1/2 c3=1/2
جایگزینی ثابتها:
tn=-1/2 n+1/2 n2
اسلاید 7 :
حل معادلات بازگشتی با استفاده از تغییر متغیر
nمثال: حل معادله:
T(1)=1
T(n)=T(n/2)+1 , n>1 , توانی از 2 n
تغییر متغیر: n=2k
T(2k)= T(2k/2)+1= T(2k-1)+1
tk= T(2k), tk= tk-1+1, tk- tk-1=1معادله خطی غیرهمگن:
(r-1)(r-1)=0, r=1
tk=c11k+c2 k 1k
T(2k)=c1+c2 k
k=lg n Þ T(n)= c1+c2 lg n
c1=c2 =1 Þ T(n)= 1+ lg n
اسلاید 8 :
حل معادلات بازگشتی با استفاده از جایگزینی
nحل معادله:
T(1)=1
T(n)=T(n-1)+n, n>1
tn=tn-1+n
=tn-2+n-1+n
=tn-3+n-2+n-1+n
=t1+2+…+n-2+n-1+n
=1+2+…+n-2+n-1+n=n(n+1)/2
اسلاید 9 :
حل معادلات بازگشتی با استفاده از جایگزینی
nحل معادله:
T(1)=0
T(n)=T(n-1)+2/n, n>1
tn=tn-1+2/n
=tn-2+2/(n-1)+2/n
=tn-3+2/(n-2)+2/(n-1)+2/n
=t1+2/2+…+2/(n-2)+2/(n-1)+2/n
=0+2/2+…+2/(n-2)+2/(n-1)+2/n
=2 S 1/i=2ln n
اسلاید 10 :
حل معادلات بازگشتی با استفاده از قضیه اصلی مرتبه زمانی
اگر:
T(n)=θ(1) n ≤ n0
T(n)=aT(n/b)+θ(nk) n > n0
n0,k ³ 0, b > 1, a ³ 1
آنگاه:
T(n)=θ(nk) a < bk
T(n)=θ(nklogbn) a = bk
T(n)=θ(nlogba) a > bk
