پاورپوینت حل معادلات بازگشتی

لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل :  powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 14 اسلاید

 قسمتی از متن powerpoint (..ppt) : 
 

حل معادلات بازگشتی
روشها:
استقرا
معادله شاخص
تغییر متغیر
جایگزینی
قضیه اصلی مرتبه زمانی
1
مثال (محاسبه فاکتوریل با روش بازگشتی)
Int fact(int n) T(n ): زمان اجرا به عنوان تابعی از تعداد ضربها
{
if (n ==0)
return 1;
else
return n*fact(n-1);
}
t n =t n-1 +1
t 0 =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
…
t n =n
باید با استقرا ثابت شود
حل معادلات بازگشتی با روش استقرا
2
محاسبه فاکتوریل...(اثبات جواب با روش استقرا)
پایه :
n=0, t 0 =0
فرض :
 n>0, t n =n
حکم :
t n+1 =n+1
اثبات :
t n+1 =t (n+1)-1 +1=t n +1=n+1
حل معادلات بازگشتی با روش استقرا
3
مثال:
t n = 7t n/2 توانی از 2 است n و n>1
t 1 =1
t 2 =7t 2/2 =7t 1 =7
t 4 =7t 4/2 =7t 2 =7 2
t 8 =7t 8/2 =7t 4 =7 3
t 16 =7t 16/2 =7t 8 =7 4
اثبات:
پایه : n=1, t 1 =1=7 0 =7 lg 1
فرض : t n =7 lg n  n>0, n=2 k :
حکم : t 2n =7 lg (2n)
t 2n =7t (2n/2) =7t n =7 7 lg n =7 1+lg n =7 lg 2+lg n =7 lg (2n)
t n =7 lg n
حل معادلات بازگشتی با روش استقرا
4