طراحی الگوریتم ها - الگوریتم های بازگشتی

صفحه 1:
Desa m x 3 3 3 5 5 Algorithms (۱ طراحی الکوریتم ها 

صفحه 2:
طراحی الگوریتم ها روش های تحلیل الگوریتم های با زگشتی استاد راهنما : ارائه : سال 

صفحه 3:
منبع : تحلیل و طراحی الگوریتم ها ( فصل دوم ) مهندس جعفر تنها - دکتو احمد فراهی انتشارات دانشگاه پیام نور 

صفحه 4:
سرفصل ها : ب أن ‎a‏ کشتی یف الگوریتم باز باز كشت * روش باز محاسبه فا کتو يل اش با ز گشتی روش باز ۱ * روش باز گشتی محاسبه سر ۳ * روث محا روش با گشتی : ‎é.‏ ‏= ی فیبوناچی سبه مسا مسئله. برج هاد انهی * حل تعدادی مسئله نمونه 

صفحه 5:
مادا ۵6۷۱۲5۱۷۰ الکور یتم باز گشتی : الگوریتم هایی اند که برای محاسبه مقدارتابع نیازبه فراخوانی خود دارند. مزايا : ميتوان به راحتى بياده سازى و درك آن اشاره كرد . معايب : استفاده از حافظه و زمان اجراى زياد . 

صفحه 6:
الگوریتم با گشتی دارای دو مرحله مهم است : # عمل فراخوانی * بازگشت از یک فراخوانی 

صفحه 7:
۱ - متغیبرهای محلی و مقادیر آنها در پشته قرار میگیرند . عمل فراخوانى ۲ - آدرس با کشت به پشته منتقل میشود . ۳ - عمل انتقال بارامتر افجام ميكيرد . ۴- کنترل برنامه به ابتداى بردازه جديد اشاره مى كند . . ‏متغيبر هاى محلی از پشته حذف و در محل خود قرار ميكيرند‎ - ١ . ‏آدرس با زکشت از پشته بازیابی میشود‎ - ۲ . ‏با بت از یک فراغوانى ۴ - آخرین اطلاعات از پشته حذف میشود‎ 6 ‏کنترل برنامه از آدرس باز گشت ادامه می یابد.‎ -۴ 

صفحه 8:
* روش باز کشتی محاسبه فا کتوریل فا کتوریل عدد صحیح 19 بدن صورت تعريف است : مل ‎n(n-1)! if on a‏ | 0 > int fact (int n ){ if(n ==0) Return (1); ales : ‏تابع باز گشتی برای, محاسبه فا کتوریل‎ Return (n * fact ( n- 1); “4 

صفحه 9:
مراحل محاسبه الگوریتم باز گشتی فاکتوریل به ازای 3 < 8 * 3 < (۵6۲)3؟ fact(2) ‏شپت‎ 2 fact(2) = 2 * Le a CA ee 1 fact(1) = 1 * a fact(o) ‏ربا‎ fact (0) < 1 int fact (int n ){ if(n ==0) Return (1); else Return (n * fact ( n-1)); Sta A fact aot = 2 at 2-7 aa 7 

صفحه 10:
# روش با زکشتی محاسبه سری فیوناچی ‏ 0 1 < 0 ]أ تابع فیبوناچی را میتوان بدین صورت نمایش داد : مثال: تابع بازكشتى براى» محاسبه فیبوناچی : ‎V+ Vu‏ اأب.ء دام ‎Fib(n) | if 0 < 2 ۱ Fib(n-1) + Fib(n-2) if nee 2 Fib(4) Fib(2) = Fib(2) + int Fib ( ‏د‎ 0 (nee 1) ‎Return (0); else if (n == 2) Return (1); else Return (Fib(n - 1) + Fib(n - ‎20) 

صفحه 11:
مراحل محاسبه الگوریتم باز گشتی فیبوناچی به ازاى 5 2 8 Fib( 4) + Fib (3 3 a a) int Fib (int n){ if(n==1) Return (0); else if (n==2) Return (1); else Return (Fib(n - 1) + Fib(n - b) ( 2) 1 

صفحه 12:
* روش باز گشتی محاسبه مسئله برج هانوی void Hanoi ( int nDisk , var start, var temp, var end ){ if (nDisk == 1){ Move_ start _To_end (); F else { Hanoi (nDisk -1, start , end , temp ); Move_start To_end (); 1, temp , start, end ); محل موقت يا كمكى temp B star Hanoi (nDisk - + |] ‏شرع‎ oy تعداد دیسک ها ‎nDis‏ ‎k‏ 

صفحه 13:
مراحل محاسبه الگوریتم با زگشتی هانوی به ازای 3 < 8 

صفحه 14:
مراحل مجاسبه الگور تم با زکشتی هانوی به ازای 3 < 8 8 6 ‏فا‎ Hano! (Int nBisk, var start, var temp , rend 

صفحه 15:
حل چند مثال 

صفحه 16:
: ‏تعدادی مفال‎ Jo ‏تابع باز گشتی برای محاسبه بزرگترین مقسوم علیه مشترک به روش اقلیدسی‎ فرض میکنیم :۵ , 3 دو عدد محیح مثبت باشند و ۵ <- 3 باشد اكر ه - 5 باشد آتگاه ب.م.م برابر 3 خواهد بود . در غیر اینصورت ب.م.م برابر ب.م.م ۵ و باقیمانده 8 بر ۵ خواهد بود . int gcd (int a, int b){ if(b==0) Return a; else Return ( gcd (b, a % b)); } 

صفحه 17:
محاسبه ب.م.م ۸ و ۱۲ با استفاده از الگوریتم 960 =e = gcd( 8,12 98 ( = gcd(4, 8 %4 ) int gcd (int a, int b){ if(b 01 Return a; else Return ( gcd (b, a % b)); 1 Sta A gcd ck 5 gcd (8, 4) 8 12 ۳ 12, 0) a [38 ‏تمه‎ 

صفحه 18:
تعدادی منال : ‎eee‏ خروجی تابع زیر رابه( 6 , 3 ) ۲: محاسبه کنید ازای int F( int m, int n){ if((m==1)||(n==0) ||(m==n)) Return 1; else Return (F(m-1,n)+F(m-1,n Sl), 2 

صفحه 19:
عرلحلاجرلوئا گیریتم به( 6 , 3 ) ۴: ۲ ۱0 ۱۳۲ ۴ ‎int‏ if((m==1) || (n==0) || (m==n)) Return 1; else Return (F(m-1,n)+F(m-1,n < 1 (6 1 4 F(a, 6P(2,6)+F(2 12°?) 26 2 F(2, ) 5 

صفحه 20:
حل تعدادی مثال : : یک درخت دودویی را در نظر گرفته و سپس خروجی تابع باز گشتی زير را محاسبه نمایید int Func (Node *tree ){ if (tree == Null) Return 0 ; else if (( tree -> left == Null ) && ( tree -> right == Null) ) Return 1 ; else Return ( Func ( tree -> left) + Func ( tree -> right ) ); 1 

صفحه 21:
درخت زیر را در فظر ميكيريم :. else if (( tree -> left == Null ) &6 ( tree -> right ® == Null )) 7 \ Return 1; else Return ( Func ( tree -> left) + Func (tree > LN right )); 0 © 1 3 Fune 2 )8 ‏عمنة عرق )عمط‎ 6 2 ۵ Func (B Func ) ۳ (c) 5 Func ( D )+ Func 253 ‏م‎ ۹ ‏تابع تعدادبرک های یک درخت‎ a 8 ‏دودبی را می شمارد‎ ۸ Func 

صفحه 22:
حل تعدادی مثال : تابع زیر بر روی درخت دودویی چه عملی را انجام میدهد ؟ int Func ( Node *tree ){ if ( tree != Null) if (( tree -> left = == Null) ) Return 1; Null ) && ( tree -> right else Return (Func ( tree -> left) + Func ( tree -> right ) + 1); x 

صفحه 23:
if ( tree != Null ) dion if (tree -> left == Null) && ( tree -> right == Null)) Return 1; he x - 5 Return (Func ( tree -> left) + Func ( tree -> right) +1); © 5 } 5 Func 2 ) 6 ‏جرع )عمط‎ Func 1۱+ ۵8 Func ) ۳ (Cc) — Func ( D (+ ‏با‎ ‎Pes ‎at‏ تعداد کل کرههای یک درخت 0 8 دودیی را می شمارد ‎a‏ ۸ ‎Func Func ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 24:
يايان شما با تشكر از همراهى