طراحی الگوريتم ها (روش های حل معادلات بازگشتی)

صفحه 1:
., ك2 Computer algorithms طراحى للكوريتم - مهندس محمد اكبربور 

صفحه 2:
Computer algorithms روش‌های حل معادلات ‎EF 3b‏ 4 همكن خطى با ضرايب ثابت غير همكن خطى با ضرايب ثابت ”- حل معادلات بازكشتى به روش تغيير متغير © طراحى الكوريتم - مهندس محمد 

صفحه 3:
پیچید گی الگوریتم‌های با ز گشتی int f(int n) { ‎if (n = = 0) return 1;‏ ‎return (f(n-1)+f(n-1)+f(n-1)+...+‏ ‎f(n-1))‏ ‏1 ‏اكر تعداد فراخوانى هاى بازكشتى رو 7 در نظر بككيريم بيجي دكى تابع فوق به صورت زير ميباشد: 616-1 ()1 21 160 ۱ و ۶ كل جمعهاى انجام شده رایدست آوريم: ید معادله ازگشتی زیر وا حل ‎eS‏ T(n) =cT{n- 1) +(c- 1) T(O) =0 week4 

صفحه 4:


صفحه 5:
۱- حل معادلات باز گشتی با استفاده (2بازگنتی زیر اب روش اتقرای ریاضی حل کنید. :حل : ابتدا بايد يكك حل كانديدا براى معادله فوق بيدا كنيم و سبس درستى اين حل كانديدا را به روش استقرا اثبا 31-0۱۱2 (4) =| A ‏ادن‎ +1-2+1-3 8 1) =U) +1=1(4) +1=3+1=4 م۰104( 0 t(n) =logh) 1 او مسد اكيريور ‎week4‏ 

صفحه 6:
با استفاده از استقراء ثابت مى كنيم كه اين حل درست امت ‎t(n) =log@)+1‏ مبناى استقراء: براى 0 > «دريم: ‏ 21 (1 فرض استقراء: فرض كنيد براى مقدار دلخواه 40 < »كه » توانى از ۲ است. داشته باشيم: t(n) =logh) +1 كام استقرا جون رابطه بازكشتى برای ‏ های توانی از ۲ است. عدد بعدی که باید در نظر گرفته شود © مى باشد لذا بايد نشان دهيم: week4 

صفحه 7:
ابتدا 20 را در رابطه باز گشتی مسأله قرار داده و با استفاده از فر oe a =1 t(2n) =log@n) +1—___-t(2n) =log@n) +1 قرا يا كام استقرا اثبات شد بنابراين حل كانديدا صحيح ميباشد . يعنى داريم t(n) =logh) +1 week4 

صفحه 8:
۲- حل معادلات باز به روش جایگزینی (22) با گشتی زير را به روش جایگزینی حل ‎AS‏ tm) ‏-صاع‎ 1+ forn>1 t@) =1 با توجه به ابنكه روش جايكزينى عكس روش استقراء استء داريم: t{n) =tn- Den tin) =tn- +n tin- I) =t{n- 2)4n-1 8 10- 2(+ 2- 1+ « = t(n- 2) =t(in- 3+n- 2 ifa= n= 24 n- +n =t()+2+..n- 2¢n- den (2) =t) +2 7 t@) =1 week4 ‏الگررتم -مهندس محند اکیرپور‎ ١ 

صفحه 9:
۳- حل معادلات با ز گشتی با فرمول تقسیم و حل 1 n=1 a T(n) = ante) + ۶0 else ‏با گشتی زیر را در نظر بگیرید‎ معادلاتى كه به فرم كلى فوق باشند معادلات روش تقسیم و حل می‌باشند و آنها را می‌توان به صورت زیر حل نمود: Tm) =n°**[T) + U(n)] 23h Gus 1 h(a) 2b O(a) ‏براي بدست آوردن‎ f@) noe h(n) = کل با ‎ely eT Cod le gage‏ (©)»اوباتوجه به جدول زير: ()40را محاسبه مىكتيم: hin) Ua) 1| ‏كمه‎ r<0 00 2 | @(dog n)') 120 ‏(۱+ز/ ۳ و00‎ 3| ‏كمه‎ r>0 Od@) week4 

صفحه 10:
لأكر (0) ثابت و یا لگاریتمی باشد : برای بدست آوردن (1()5) از فرمول دوم استفاده مى كنيم. با توجه به جدول فوق. جهت به دست آوردن (0)( با هر یک از (۳)۳های زیر از کدام فرمول استفاده می‌شود؟ قرمول شماره 3با ۲-1 ‎h(n) =n‏ فرمول شماره 2با 20 1 ‎h(n)=e‏ ‏فرمول شماره 1 پا 2 ی(« فرمول شماره 2با 1-1 ‎h(n) = (log n)!‏ week4 ‏الگررتم -مهندس محند اکیرپور‎ ١ 

صفحه 11:
(©6) باركمى زيروابا اسطاده رل ۶ ۱ ۱ 00 ae ‏مد رقمو > لهك‎ else جواب: با توجه به معادله با گشتی فوق موارد زیر را داریم ۲0-1 , ۶ , 2 ۶ ۶ 2 pa =1 foe? = 7f°S? =p , Knh= ‎٩‏ ۱60 پس برای محاسبه زمان؛ از فرمول شماره با () 1 استفدهمی‌کنیم ‏(«وملع (هت. = 2 (ه)ط ‎ ‎Ti) =111+(logn)] = T(x) =n+ (nlogn) T(n)€ O(n logn) ‎ ‏راحی الگوریتم - مهندس محمد اکبرپور ‎week4‏ 

صفحه 12:
*- با کشتی زیر را با استفاده از استقرای ریاضی حل کنید. (7- ها ‎t@) =1 ee‏ 7= )740= 12-7۷5 10۸-7۷ =7102)=7" E38 W=NG 110 =) =7t(8) =7* ) =74(4) =79 t(n) =7°9P eens week4 

صفحه 13:
با اسفاده از استقراءثابت می‌کنیم که حل دوست لت مبناى استقراء: ‏ برای 4 «داریم: 9- 21-7 (101 فرض استقراء: فرض كنيد براى هر مقدار دلخواه 0 < « که توانی از ۲است» داريم: 79 (و)] كام استقراء: بايد نشان دهيم: «همومر- رون اگر 2۳ را در بازكشتى قرار دهيم: يدست می‌آوریم: 1(2n) =74(22) =7t(n) =7 x7!°9" =7itlogn — 7log2slogn _ ‏(«ومار‎ ۱10) - 7 5 SM t(n) =n°9? wn?!) ‏وا رسيي‎ بم -مهتدس محند اکیرپوز ‎week4‏ 

صفحه 14:
*- الگوريتم باز گشتی پیدا کردن ما کزیمم عضو یکث لیست. بصورت زیر می‌باشد: Algmax(i,n) { if(1— 1) then return (A[iJ) : else ‏تمه مت‎ (max (s,|® |) , maxg+|| a-|2 [yy 12 |f ® 21۳ ‏ام‎ ‎} ‎; ‏لنديسخانه ايل‎ :1 ‏لیست‎ ‏تسعداد عتاصر‎ : © ‏لیست زیر رسم کنید.‎ slp by Gs gs Stage 0 16 10 9 5 4 3 1 12 19 ب) معادله بازكشتى الككوربتم بيدا كردن ماكزيمم عضو يكك ليست راء نوشته و آن را بصورت جايكزينى حل كنيد. aed بم -مهتدس محند اکیرپوز ‎week4‏ 

صفحه 15:
1,0 aa ea |[ aa @,e |] oa ‏مه || موم‎ | | 6 ۶ | مه | [ »6 | | مج | | وه | وه تعداد فراخواني برابر با 040 مي‌باشد. تعداد اجراي تابع مومس برابر با 40 مي‌باشد. تعداد فراخواني‌هاي با 0 < » برابر با 00 مي‌باشد (تعداد برگها و تعداد عناصر لیست). بم ‎pen‏ محمد اکیرپور ‎week4‏ 

صفحه 16:
ب) معادله با گشتی الگوریتم بصورت زیر خواهدبود ‎n=1‏ a = n. t=) +p ‏دحم‎ ‎2 ‎۳ ‏ار‎ ‎POU) +b 11-2 ‏لول ميض سورض‎ ‏هه + لاله - ما + (+ رك2)2-‎ n 2 1 a s =A(Q4Z) + B)+2bx-b = B17) + Abs 2+ b a و(2۳ + 2 + توب + + یله ‎bb + Tin) =nat+b-b‏ week4 

صفحه 17:


صفحه 18:


صفحه 19:
طراحى للكور يتم - مهندس محمد اکبربور >