پاورپوینت توابع بازگشتي (pptx) 30 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 30 اسلاید
قسمتی از متن PowerPoint (.pptx) :
توابع بازگشتي
1
تفكر تكراري تفكر الگوريتمي تفكر بازگشتي
2
اگر بتوان مسئله ای را با حلقه هاي تكرار پياده سازي كرد ، ترجيحا از حلقه هاي تكرار استفاده می كنيم ، زیرا توابع بازگشتي نسبت به حلقه های تکرار به حافظه ی بیشتری نیاز دارند . اما از نظر زماني هيچ تفاوتی در استفاده از حلقه هاي تكرار و توابع بازگشتي نيست به شرط آنكه روش حل يكي باشد و تنها پياده سازي متفاوت باشد.
به عنوان مثال موضوعيّت درخت يك تعريف بازگشتي است.
طرح تابع بازگشتي مستلزم داشتن تفكر بازگشتي است ؛
به عبارت ديگر :
باید بتوان يك مساله را با مساله اي دقيقاً از همان نوع و جنس ، امّا با تعداد داده هاي كمتر پاسخ داد .
3
اين نوع تفكر مستلزم دو نكته است: 1- داشتن منطق بازگشتي 2- شرط خاتمه(خروج)
مثال : براي موارد زير منطق بازگشتي و شرط خاتمه رابنويسيد.
1- فاكتوريل
2- عدد n ام فيبوناچي
3- جمع عناصر يك آرايه
4- معكوس كردن يك آرايه
طرح تابع بازگشتي مستلزم داشتن تفكر بازگشتي است .
5- عمق درخت
6- تعداد node درخت
7- كپي كردن درخت
4
پاسخ
منطق بازگشتي : n! = n (n-1)!
1- فاكتوريل
شرط خاتمه 0! = 1
منطق بازگشتي : عدد(n-2) + عدد (n-1) = عدد nام
2- عدد n ام فيبوناچي
شرط خاتمه n=1 → 1 يا n=2
منطق بازگشتي : باقي مانده آرايه اوّليه+عددآخر آرايه= جمع عناصرآرايه
3- جمع عناصريك آرايه
شرط خاتمه size = 0
5
منطق بازگشتي: معكوس كردن آرايه باقي مانده+جابجایی عنصر اول و آخر 4- معكوس كردن
يك آرايه شرط خاتمه size = 0 يا size =1
5- درخت : مي دانيم كه درخت يا تهي (شرط خاتمه)است و يا شامل يك عنصر به نام ريشه و دو زير درخت چپ و راست(منطق بازگشتي).
منطق بازگشتي: (زيردرخت راست + زيردرخت چپ)max + 1
عمق درخت
شرط خاتمه ريشه وجود نداشته باشد(درخت تهي)
6
منطق بازگشتي: (تعداد nodeزيردرخت راست+تعداد nodeزيردرخت چپ)1 6- nodeدرخت شرط خاتمه ريشه وجود نداشته باشد(درخت تهي)
منطق بازگشتي : كپي كردن زير درخت چپ و كپي كردن زير درخت راست
7-كپي درخت
شرط خاتمه ريشه وجود نداشته باشد(درخت تهي)
7
تمارين
1- كدهاي توابع مثال بالا را به زبان C بنويسيد.
2- تابع بازگشتي بنويسيد كه ارقام يك عدد صحيح را به ترتيب ارزش مكاني چاپ نمايد.
(به عنوان مثال عدد 2583 را به صورت 2583 چاپ كند)
3- تابع بازگشتي بنويسيد كه ارقام يك عدد صحيح را به ترتيب عكس ارزش مكاني چاپ نمايد.
(به عنوان مثال عدد 2583 را به صورت 3852 چاپ كند)
8
تحليل زماني توابع بازگشتي
شامل دو فاز است :
فازاوّل : بدست آوردن يك معادله ي بازگشتي ازروي الگوريتم بازگشتي .
فاز دوّم : حل رياضي معادله ی بازگشتي و ارائه پاسخ صريح .
9