لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت حل معادلات بازگشتی توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت حل معادلات بازگشتی قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

حل معادلات بازگشتی با استفاده از معادله شاخص

.۱معادلات خطی همگن

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

اسلاید ۲ :

حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص

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           ۴c1-c2=1                     c1=1/5, c2=-1/5

جایگزینی ثابتها:

tn=(1/5)4n-1/5(-1)n

اسلاید ۳ :

حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص

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+Ö۵)/۲, (۱-Ö۵)/۲

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

tn=c1 [(1+Ö۵)/۲] n+c2 [(1-Ö۵)/۲] n

تعیین ثابتها:

c1=1/ Ö ۵, c2=-1/ Ö ۵

جایگزینی ثابتها:

        [(۱+ Ö۵ )/۲ ] n-[(1- Ö۵) /۲ ] n

اسلاید ۴ :

حل معادلات بازگشتی خطی همگن با استفاده از معادله شاخص

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

اسلاید ۵ :

حل معادلات بازگشتی خطی غیرهمگن با استفاده از معادله شاخص

.۲معادلات خطی غیرهمگن

¨معادله بازگشتی خطی غیرهمگن: یک معادله بازگشتی به شکل

     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

اسلاید ۶ :

حل معادلات بازگشتی خطی غیرهمگن با استفاده از معادله شاخص

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

اسلاید ۷ :

حل معادلات بازگشتی با استفاده از تغییر متغیر

nمثال: حل معادله:

T(1)=1      

T(n)=T(n/2)+1    , n>1 , توانی از ۲ 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

اسلاید ۸ :

حل معادلات بازگشتی با استفاده از جایگزینی

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

     =۱+۲+…+n-2+n-1+n=n(n+1)/2

اسلاید ۹ :

حل معادلات بازگشتی با استفاده از جایگزینی

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+…+۲/(n-2)+2/(n-1)+2/n

     =۰+۲/۲+…+۲/(n-2)+2/(n-1)+2/n

 

     =۲ S 1/i=2ln n

اسلاید ۱۰ :

حل معادلات بازگشتی با استفاده از قضیه اصلی مرتبه زمانی

اگر:

T(n)=θ(۱)                    n ≤ n0

T(n)=aT(n/b)+θ(nk)      n > n0

    n0,k ³ ۰,   b > 1,   a ³ ۱

آنگاه:

T(n)=θ(nk)                  a < bk

T(n)=θ(nklogbn)         a = bk

T(n)=θ(nlogba)             a > bk