سلام
به رابطه بازگشتی زیر توجه کنید، توی جزوه یکی از استادها این رو از طریق تغییر متغیر حل کرده بود.
با تغییر متغیر اون رو به معادله ی ناهمگن با ضرایب ثابت تبدیل کرده، من روند حل رو تا یه جاهایی نوشتم ولی توی عبارت بعد از مساوی گیر کردم!
![[تصویر: CLRS.jpg]](https://img.manesht.ir/CLRS.jpg)
تشکر.
(۰۱ مهر ۱۳۹۲ ۰۳:۰۳ ب.ظ)هاتف نوشته شده توسط: سلام
به رابطه بازگشتی زیر توجه کنید، توی جزوه یکی از استادها این رو از طریق تغییر متغیر حل کرده بود.
با تغییر متغیر اون رو به معادله ی ناهمگن با ضرایب ثابت تبدیل کرده، من روند حل رو تا یه جاهایی نوشتم ولی توی عبارت بعد از مساوی گیر کردم!
بعد از این جواب نهایی که از حل بوسیله معادله مشخصه بدست اومده هم نوشتم، لطفا ادامه ی حل مسئله رو به من توضیح بدید.
تشکر.
سلام آقا هاتف
خوب ببین دو تا کار میشه کرد... اولی اینکه معادله مشخصه قسمت همگن و ناهمگن بدست بیاریم با هم ترکیب کنیم بریم جلو تا حل بشه. و بعد تغییر متغیر بدیم و بشه اون چیزی که شما نوشتی. دومین کار اینکه با جایگزینی حل کنیم و بعد تغییر متغیر بدیم. من اولی راهکار رو ساده تر میدونم ولی میخواهم سخته رو حل کنم واست. (یعنی جایگزینی)
داریم : [tex]G(k)=2G(k-1) \frac{2^k}{k}[/tex] از طرفی چون تغییر تابع این رو خودمون دادیم : [tex]g(k)=T(2^k)[/tex] در نتیجه :
[tex]n=2^k , T(1)=1 , T(2^k)=1 \Rightarrow k=0 \Rightarrow g(0)=1[/tex]
[tex]n=2^k , T(2)=2 , T(2^k)=1 \Rightarrow k=1 \Rightarrow g(1)=2[/tex]
تا اینجا که بدیهی است. خوب حالا بریم سراغ جایگزینی :
[tex]g(2)=2g(1) \frac{2^2}{2}=2[2] \frac{2^2}{2}=\frac{2^2}{1} \frac{2^2}{2}[/tex]
[tex]g(3)=2g(2) \frac{2^3}{3}=2[\frac{2^2}{1} \frac{2^2}{2}] \frac{2^3}{3}=\frac{2^3}{1} \frac{2^3}{2} \frac{2^3}{3}[/tex]
.
.
.
[tex]g(k)=\frac{2^k}{1} \frac{2^k}{2} \frac{2^k}{3} ... \frac{2^k}{k}=2^k( \frac{1}{1} \frac{1}{2} \frac{1}{3}... \frac{1}{k})=2^klog(k)[/tex]
خب حالا تغییر متغیر رو برگردونیم. بقیش آسونه.
سلام
خیلی عالی ممنون، جز یه بخش کوچیک که پائین پرسیدم باقی رو کامل متوجه شدم.
(۰۱ مهر ۱۳۹۲ ۰۵:۵۳ ب.ظ)vojoudi نوشته شده توسط: داریم : [tex]G(k)=2G(k-1) \frac{2^k}{k}[/tex] از طرفی چون تغییر تابع این رو خودمون دادیم : [tex]g(k)=T(2^k)[/tex] در نتیجه :فقط یه سوال، اینجا که فرمودید بدیهی هست
[tex]n=2^k , T(1)=1 , T(2^k)=1 \Rightarrow k=0 \Rightarrow g(0)=1[/tex]
[tex]n=2^k , T(2)=2 , T(2^k)=1 \Rightarrow k=1 \Rightarrow g(1)=2[/tex]
تا اینجا که بدیهی است..
شما چطور نوشتید [tex]T(1)=1 [/tex] یا [tex]T(2)=2 [/tex]
تابع به ما مقادیر اولیه رو که نداده بود!
بعد از این میخواستم ازتون خواهش کنم به روش اول هم حل اش کنید. ممنون.