زمان تقریبی مطالعه :

تاریخ : چهارشنبه 1393/07/09

گام دوازدهم در برنامه نویسی ++C

اهداف کلی:

آشنایی با الگوریتم بازگشتی وشناخت واستفاده صحیح آن درمسئله

اهداف رفتاری و عمکردی:

انتظار می‌رود پس از پایان این جلسه بتوانید:
مسایل مطرح شده را با الگوریتم های بازگشتی بنویسید و همین طور بتوانید تشخیص دهید که چه مسئله ای را باید بازگشتی بنویسید تا راحت ترمی باشد و این الگوریتم را در دیگر مساله هایی که حل کردید بسط دهید.

سرفصل های تئوری:

- توضیح: اعداد مثلثی
-. آشنایی با چگونگی حل مسأله به روش بازگشتی
- نمونه‌ی غیربازگشتی
- بررسی دقیق‌تر ـ ساز و كار بازگشت
- خواص توابع بازگشتی
- چند نكته در مورد توابع بازگشتی
- توضیح برج هانوی
- الگوریتم ـ چرخش اشكال سرفصلهای عملی :
- یافتن nامین عدد مثلثی
- مثلث سرپینسكی
- برج های هانوی
-حل برنامه كه تمام زیرمجموعه‌های یك مجموعه شامل اعداد 1 تا n

مواد و تجهیزات لازم برای گام:

بازگشت

فنی در برنامه‌نویسی كه در آن یك تابع، خودش را فراخوانی می‌كند.
بازگشت با استفاده از یك مثال بسیار ساده، مطرح می‌شود. مثالی كه در ابتدا با روش معمولی (استفاده از فنی) حل شود، سپس از جهت دیگری بررسی شود و حل مسأله به نوشتن یك تابع محدود شود. این تابع، در قسمتی باید تابع دیگری را برای حل نمونه‌ی ساده شده‌ی مسأله صدا بزند و با استفاده از نتیجه كار تابع ثانویه، جواب مسأله را بیابد. و پس از كمی بررسی، راه حل بازگشتی مطرح شود.
مثال1: یافتن nامین عدد مثلثی

1, 3, 6, 10, 15, 21, …

توضیح: اعداد مثلثی، دنباله‌ای از اعداد هستند كه در آن، جملهn ام حاصل جمعn جمله‌ی قبلی است. وجه تسمیه‌ی این دنباله، نمایش آن با استفاده ازمثلث‌ها است.

N=1 N=2 N=3

هدف: یك مسأله كه هر دونمونه‌ی معمولی بازگشتی آن، ساده هستند. آشنایی با چگونگی حل مسأله به روش بازگشتی

نمونه‌ی غیربازگشتی

Int triangle(int n)
{
int result = 0;
int i;
for (i=1 ; i<=n; ++i)
result +=i;
return result ;
}

نمونه‌ی بازگشتی با استفاده از فرمول:

triangle(n) = triangle(n-1) + n

یا با توجه به شكل

int triangle(int n)
{
int result = n + triangle(n-1); // .ناقص است. شرط خاتمه ندارد

return result;
}

دراین مرحله، با مثالی، لزوم وجود شرط خاتمه یا حالت پایه روشن می‌شود:
دانش آموزی، می خواهد 5امین عدد مثلثی را پیدا كند، برای این كار محاسبه‌ی 4امین عدد مثلثی را به دوستش محول می‌كند. پس از اینكه دوستش، 4امین عدد را یافت ، 5 را با جواب او جمع می‌كند و مسأله حل می‌شود. دوست او هم به همین صورت قسمتی از كار را به دوست خود واگذار می‌كند. ولی بالاخره كسی باید باشد كه بتواند بدون كمك گرفتن از دیگران، عدد مثلثی خواسته شده را محاسبه كند.
در این مورد خاص، مشخص است كه اولین عدد مثلثی، 1 است.

تعریف: شرطی را كه باعث می‌شود یك تابع بدون فراخوانی بازگشتی دیگری به فراخواننده‌ی خود بازگردد، حالت پایه می‌نامند. لازم است كه حتماً هر تابع بازگشتی دارای یك حالت پایه باشد تا از ایجاد بازگشت نامتناهی و مختل ساختن اجرای برنامه، جلوگیری شود.

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

در اینجا، شرط خاتمه نوشته شود و مثال كامل شود.
مثال 2- اعداد فیبوناچی: دنباله‌ای از اعداد به صورت … و 8 و 5 و 3 و 2 و 1 و 1 است كه در آن هر عدد، جمع دو عدد قبل خود است. برنامه‌ای بنویسید كه nامین عدد فیبوناچی را محاسبه كنید.

هدف: مثال كمی پیچیده‌تر كه نشان‌دهنده‌ی ساده شدن حل بعضی مسائل با كمك بازگشت است.

حل بدون بازگشت: باید كاملاً در كلاس توضیح داده شود:

int fibonachi(int n)
{
int prev, prev2; // prev, prev of prev
int result; // hasel
int i ; // index

prev=prev2=1; // 1st and 2nd numbers
result=1; // in the case of n<=2;
for (i=3; i<=n; ++i)
{
result = prev + prev2;
prev=prev2;
prev2=result;
}
return result;
}

توجه: هنگام تدریس، شاید بهتر باشد ابتدا حلقه یا فراخوانی بازگشتی گفته شود. سپس مقادیر اولیه و شرط خاتمه (حالت پایه)
حل بازگشتی:

int fibonachi( int n)
{
if ( n==1 || n==2 ) // base case
  return 1;
else
return ( fibonahi(n-1) + fibonachi(n-2) );
}

بررسی دقیق‌تر ـ ساز و كار بازگشت
در این قسمت با استفاده از جدول و نشان دادن مقادیر متغیرها در فراخوانی‌های تو در تو،‌ یا با استفاده از شكلی مثل شكل زیر (بدون استفاده از مفهوم stack و اشاره‌ای به آن و جزئیات فراخوانی)، مرحله به مرحله،‌ بازگشت نشان داده شود.

خواص توابع بازگشتی

1. خود را فراخوانی‌ می‌كنند.
2. در هر بار، خود را برای حل مسأله ساده‌تری (كوچك‌تر شده‌ای) صدا می‌زنند.
3. نسخه‌ای از مسأله وجود دارد كه به قدری ساده است كه برای حل آن نیازی به فراخوانی مجدد نیست.

چند نكته در مورد توابع بازگشتی
• با توجه به اینكه در هر مرحله فراخوانی تابع، برای متغیرها حافظه‌ی جدیدی گرفته می‌شود، چون این حافظه (stack) محدود است، ممكن است در اثر فراخوانی زیاد، برنامه دچار مشكل شود. و پس از مدتی توسط سیستم عامل متوقف شود.

• مسایلی كه به روش بازگشتی حل می‌شوند و فراخوانی بازگشتی آنها، در انتهای تابع است، در صورتی كه تنها یك فراخوانی بازگشتی داشته باشند (مثل اعداد مثلثی)، قابل تبدیل به یك حلقه و در صورتی كه بیش از یك فراخوانی داشته باشند (مثل اعداد فیبوناچی)، آخرین فراخوانی بازگشتی قابل جایگزینی با حلقه است. این كار باعث می‌شود از متغیرهایی كه در هر بار فراخوانی در اختیار داریم، بتوانیم مجدداً استفاده كنیم و از تعداد فراخوانی‌های تو در تو بكاهیم.

البته این كار ممكن است كمی درك عملكرد تابع بازگشتی را سخت بكند.

• روش‌هایی وجود دارد كه با آن، هر تابع بازگشتی قابل پیاده‌سازی با استفاده از حلقه است ولی از حوزه درسی فراتر است.

• دقت كنید كه روش بازگشتی برای حالت‌های خیلی ساده هم به درستی كار كند (مثلاً برای n=1 )

• مطمئن شوید كه در همه‌ی حالات، شرط خاتمه پس از تعداد محدودی فراخوانی براورده شود.

• به متغیرهایی كه توسط توابع بازگشتی در هر مرحله دستكاری می‌شوند دقت كنید. ممكن است در اثر بی‌دقتی، متغیری كه گمان می‌كردید در طول اجرای یك تابع ثابت باقی می‌ماند یا پس از بازگشت از فراخوانی یك تابع هم چنان مقداری را دارد كه پیش از فراخوانی داشته، مقدارش تغییر كرده باشد. (مثلاً عناصر آرایه‌ها)

• به تعداد متغیرهایی كه توابع بازگشتی می‌گیرید و یا به عنوان آرگومان به آنها پاس می‌كنید دقت كنید و حتی‌الامكان تعدادشان را به حداقل برسانید تا از حافظه موجود حداكثر استفاده را بتوانید ببرید.

• همیشه روش بازگشتی بهترین روش حل مسایل نیست و بعضی اوقات، روش بازگشتی به حدی ناكارآمد است كه قادر به پاسخگویی به جواب مسأله در حالت‌های نسبتاً ساده هم نیست. معمولاً بدین خاطر از بازگشت استفاده می‌شود كه حل یك مسأله را آسان می‌سازد نه اینكه كارایی بیشتری دارد.

• كمی توضیح در مورد رابطه استقرای ریاضی و بازگشت داده شود.

نکته اضافه
مثال: حذف یك مرحله بازگشت از تابع fibonachi()

int fibonachi2(int n)
{
int result=1; // base case
while (n !=1 && n!=2)
{
result = fibonachi2(n-1) + result;
n-=2;
}
return result;
}

توضیح:

به دلیل اینكه در سطر ششم تابع fibonachi، پس از اجرای دستور fibonachi (n-2) دیگر با متغیرهای محلی (و پارامتر n) كاری نداریم، می‌توانیم به جای اینكه واقعاً خود را برای n-2 صدا بزنیم، این كار را با تنظیم و تغییر متغیرها برای حالت n-2 (كم‌ كردن 2 از n) و بازگشت به ابتدای تابع انجام دهیم.
برای شهود بیشتر، به نسخه‌ی بازنویسی شده‌ی تابع fibonachi اولیه دقت كنید.

int fibonachi(int n)
{
int result = 1;

if ( n!=1 && n!=2 )
result = fibonachi(n-1) + fibonachi(n-2);

return result;
}

از حلقه‌ی while برای بازگشت به ابتدای تابع و برآوردن شرط خاتمه (حالت پایه) استفاده شده است.

ادامه درس...

مثال: مثلث سرپینسكی

#include <iostream>
#include <graphics.h>
void ser(int x1, int y1, int x2, int y2, int x3, int y3, int n)
{
line((x1+x2)/2, (y1+y2)/2, (x1+x3)/2, (y1+y3)/2);
line((x1+x2)/2, (y1+y2)/2, (x2+x3)/2, (y2+y3)/2);
line((x1+x3)/2, (y1+y3)/2, (x2+x3)/2, (y2+y3)/2);
if (n > 1)
{
ser(x1, y1, (x1+x2)/2, (y1+y2)/2, (x1+x3)/2, (y1+y3)/2, n-1);
ser((x1+x2)/2, (y1+y2)/2, x2, y2, (x2+x3)/2, (y2+y3)/2, n-1);
ser((x1+x3)/2, (y1+y3)/2, (x2+x3)/2, (y2+y3)/2, x3, y3, n-1);
}
}
int main()
{
int n, x1, y1, x2, y2, x3, y3;
cout << “enter the number of steps : “;
cin >> n;
initwindow(800,600);
x1 = 320; y1 = 50;
x2 = 100; y2 = 400;
x3 = 540; y3 = 400;
line(x1, y1, x2, y2);
line(x1, y1, x3, y3);
line(x2, y2, x3, y3);
ser(x1, y1, x2, y2, x3, y3, n);
return 0;
}

تمرین 1- برج های هانوی
توضیح: برج های هانوی معمایی قدیمی است كه در آن تعدادی صفحه در سه ستون قرار گرفته‌اند. صفحات دارای قطرهای متفاوتی هستند و در میانه‌ی خود سوراخی دارند از طریق این سوراخ بر روی ستون‌ها قرار می‌گیرند. تمامی صفحات در ابتدا بر روی ستونA قرار دارندهدف معما انتقال تمامی صفحات از ستون A به ستون C است. در هر بار فقط می‌توان یك صفحه را جابه‌جا كرد و هیچ صفحه‌ای نباید بر روی صفحه‌ای كه كوچكتر از خود است قرار گیرد.
با استفاده از روش بازگشتی، راه حلی برای این مسأله ارایه دهید.

راهنمایی: ابتدا مسأله رابرای‌‌حالت‌های خیلی ساده حل كنید (مثلاً n=2 )
سپس هر چه مسأله بزرگ تر می‌شود،‌ سعی كنید با استفاده از روشی كه در حالت‌های ساده‌تر استفاده كرده بودید و با كمی تعمیم، مسأله را حل كنید.

سعی كنید یك استراتژی حل با استفاده از تكرار الگوهای ساده پیدا كنید. شاید اگر ستون‌ها و صفحات را نامگذاری كنید، سپس به ستون‌ها به صورت ستون مبدأ، ستون میانی و ستون مقصد بنگرید و در هر مرحله، مبدأ،‌ مقصد و ستون میانی را شناسایی كنید، در یافتن الگوریتم بازگشتی به شما كمك كند.

روش حل: ابتدا باید به روشی، تمام صفحات به جز بزرگترین آنها را به ستون میانی منتقل كرد. سپس صفحه‌ی بزرگتر را به ستون مقصد. بعد هم صفحات باقی‌مانده را از ستون میانی به ستون مقصد منتقل كرد.
حالت پایه: حالتی كه تنها یك صفحه لازم است به ستون میانی منتقل شود.

توجه: به این حتماً‌ توجه شود كه نحوه‌ی فراخوانی توابع بازگشتی توسط استفاده‌كنندگان (مثلاً تابع main) باید كاملاً مشخص شود و به دانش‌آموزان تفهیم شود. بعضی اوقات همه‌ی ورودی‌های توابع بازگشتی در صورت مسأله نیامده است و فقط در حل مسأله به صورت بازگشتی مفهوم پیدا می‌كنند.

در این مواقع بهتر است یك تابع ساده نوشته شود كه ورودی‌های آن، همان پارامترهای مسأله باشند و اولین فراخوانی تابع بازگشتی با ورودی‌های مناسب، توسط این تابع انجام شود. مثلاً یك تابع مرتب‌سازی بازگشتی ممكن است پارامترهای زیر را بگیرد:

recSort(int array [], int tempSpace [], int start, int end);

tempSpace [ ]، start و end جزو ملزومات مسأله نیستند. بلكه تنها array[] و n (تعداد اقلام) مهم است. بنابراین می‌توان یك تابع واسط (كمكی) برای فراخوانی recSort با ورودی‌های مناسب، نوشت:

void sort(int array [], int n)
{
int *temSpace = new int[n];
recSort(array, tempSpace, 0, n-1);
delete tempSpace;
}

حل مسأله برج‌های هانوی

void hanoi(int topN, char src, char temp, char dest)
{
if (topN==1)
cout<<“Disk 1 from “<<src<<” to “<<dest;
else {
hanoi(topN-1, src, dest, temp); // source to middle
cout<<“Disk “<<topN<<” from “<<src<<” to “<<dest;
hanoi(topN-1, temp, src, dest); // middle to dest
}
}

یا به صورت مختصرتر:

if (topN>O)
{
hanoi(topN-1, src, dest, temp);
cout<<“Disk “<<topN<<” from “<<src<<” to “<<dest;
hanoi(topN-1, temp, src, dest);
}

گام به گام با برنامه نویسی به زبان C++