پاورپوینت حل معادلات بازگشتی (pptx) 14 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 14 اسلاید
قسمتی از متن PowerPoint (.pptx) :
1
حل معادلات بازگشتی
روشها:
استقرا
معادله شاخص
تغییر متغیر
جایگزینی
قضیه اصلی مرتبه زمانی
2
مثال (محاسبه فاکتوریل با روش بازگشتی)
Int fact(int n) T(n):زمان اجرا به عنوان تابعی از تعداد ضربها
{
if (n==0)
return 1;
else
return n*fact(n-1);
}
tn=tn-1+1
t0=0
T(n)=T(n-1)+1
t1=t0+1=0+1=1
t2=t1+1=1+1=2
t3=t2+1=2+1=3
…
tn=n
حل معادلات بازگشتی با روش استقرا
3
محاسبه فاکتوریل...(اثبات جواب با روش استقرا)
پایه :
n=0, t0=0
فرض :
n>0, tn=n
حکم :
tn+1=n+1
اثبات :
tn+1=t(n+1)-1+1=tn+1=n+1
حل معادلات بازگشتی با روش استقرا
4
مثال:
tn= 7tn/2 توانی از 2 است n و n>1
t1=1
t2=7t2/2=7t1=7
t4=7t4/2=7t2=72
t8=7t8/2=7t4=73
t16=7t16/2=7t8=74
اثبات:
پایه : n=1, t1=1=70=7lg 1
فرض : tn=7lg n n>0, n=2k:
حکم : t2n=7lg (2n)
t2n=7t(2n/2) =7tn=77lg n=71+lg n=7lg 2+lg n=7lg (2n)
tn=7lg n
حل معادلات بازگشتی با روش استقرا
5
معادلات خطی همگن
معادله بازگشتی خطی همگن: یک معادله بازگشتی به شکل a0tn+ a1tn-1+…+ aktn-k=0 که در آن k و ai مقادیر ثابت هستند.
معادله شاخص: برای معادله بازگشتی خطی همگن با ضرایب ثابت, معادله شاخص به صورت زیر تعریف می شود:
a0rk+ a1rk-1+…+ akr0=0
قضیه: اگر معادله شاخص یک معادله بازگشتی دارای k جواب مجزای r1,r2,..,rk باشد, آنگاه تنها جواب معادله به شکل زیر است:
tn= c1r1n+…+ ckrkn
حل معادلات بازگشتی با استفاده از معادله شاخص
6
مثال
حل معادله:
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
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
(4n)
7
حل معادله بازگشتی تولید دنباله فیبوناچی:
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
مثال
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
8
قضیه: اگر r یک ریشه یه توان m معادله شاخص برای معادله بازگشتی خطی همگن با ضرایب ثابت باشد, انگاه:
tn=rn, tn=n rn, tn=n2rn, …, tn=nm-1rn
مثال: حل معادله بازگشتی:
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
حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص
(n3n)
9
معادلات خطی غیرهمگن
معادله بازگشتی خطی غیرهمگن: یک معادله بازگشتی به شکل
a0tn+ a1tn-1+…+ aktn-k=f(n) که در آن k و ai مقادیر ثابت هستند و f(n) یک تابع غیر صفر است.
حالت خاص: f(n)=bnP(n)
معادله شاخص: برای معادله بازگشتی خطی غیرهمگن با ضرایب ثابت, معادله شاخص به صورت زیر تعریف می شود:(d درجه P است)
(a0rk+ a1rk-1+…+ akr0)(r-b)d+1=0
حل معادلات بازگشتی خطی غیرهمگن با استفاده از معادله شاخص
ثابت
چندجمله ای از n