PDA

View Full Version : توضیح تابع بازگشتی



mononok
جمعه 26 مهر 1387, 16:23 عصر
سلام
من برنامه ورابطه ی برنج هانوی را دارم و خودم از روی شکل می توانم نحوه ی کار آن را بفهمم مثلا برای تشکیل برج 4 تایی باید اول برج 3 تایی تشکیل شود و برای تشکیل برج 3 تایی باید 2 تایی اول تشکیل شود تا 1 و بعد 4 آزاد می شود و به ستون مورد نظر می رود و بعد دوباره همان 3 تایی روی ستونی که 4 هست دوباره تشکیل شودو... ولی وقتی از روی برنامه می خواهم تریس کنم نمی توانم درک کنم چه می شود یهنی در فهم چگونگی تابع بازگشتی آن مشکل دارم...ممنون می شم اگه کسی پیدا بشه و برایم توضیح بده..:لبخندساده:


procedure Hanoi(n: integer; from, dest, by: char);
Begin
if (n=1) then
writeln('Move the plate from ', from, ' to ', dest)
else begin
Hanoi(n-1, from, by, dest);
Hanoi(1, from, dest, by);
Hanoi(n-1, by, dest, from);
end;
End;

m.abbasi.kia
جمعه 26 مهر 1387, 18:31 عصر
با سلام خدمت شما دوست عزیز
تو روابط بازگشتی کلا مسوله به چند مسئله کوچکتر تقسیم میشه ، مثلا این الگوریتم هانوی به این شکل حل میشه که : ابتدا ما n-1 دیسک رو به طریق بازگشتی از A به B منتقل می کنیم و بعد اون یه مهره رو با یه حرکت به c منتقل می کنیم خوب حالا اون n-1 مهرهای که تو B هستن رو باز هم به طریق بازگشتی به C منتقل میکنیم . در واقع مسئله به یه مسئله با n-1 مهره تبدیل میشه چون ما یه مهره رو انتقال دادیم

m.abbasi.kia
جمعه 26 مهر 1387, 20:24 عصر
یه مثال جالبتر میزنم که با این حتما متوجه میشی
به این شکل که مسئله همون برج های هانوی هست ولی اینجا ما نمیتونیم مستقیما مهره رو از A به C بفرستیم یعنی واسه انتقال اون ابتدا باید اون مهره رو به B و بعدش به C انتقال بدیم
خوب حالا حل این مسئله

ابتدا ما n-1 مهره رو به طریق بازگشتی از A به C منتقل می کنیم


http://m-abbasi-kia.persiangig.com/image/1.JPG
سپس یک مهره باقی مانده در A را به B منتقل می کنیم
http://m-abbasi-kia.persiangig.com/image/2.JPG
حالا n-1 مهره که تو میله c هستن رو به طریق بازگشتی به A منتقل می کنیم.
http://m-abbasi-kia.persiangig.com/image/3.JPG

یک دیسک موجود در B رو به C منتقل می کنیم
http://m-abbasi-kia.persiangig.com/image/4.JPG

در مرحله آخر n-1 مهره باقی مانده در a رو به طریق
بازگشتی به C منتقل می کنیم
http://m-abbasi-kia.persiangig.com/image/5.JPG


تابع بازگشتیش هم این میشه:

procedure Hanoi(n: integer; A,C,B :char);

Begin

if (n=1) then;

else begin

Hanoi(n-1, A, C, B);

writeln('Move the plate from ', A , ' to ', B)

Hanoi(n-1, C, A, B);

writeln('Move the plate from ', B , ' to ', C)

Hanoi(n-1, A, C, B);

end;

End;



که پیچیدگی زمانی ش هم میشه T(n)=3T(n-1)+2 که مرتبه O(3^2 .



امیدوارم که به دردت بخوره .:چشمک:

mononok
جمعه 26 مهر 1387, 22:57 عصر
دوست عزیز خیلی از کمکتون ممنونم ولی همون طور که گفتم از رو شکل کاملا همون چیزهایی که گفتید رو می فهمم ولی تو ترجمه ی این سه خط موندم:یعنی وقتی خودم رو کاغذ می یام یه عدد بدم و خط به خط برنامه رو بنویسم نمی دونم چطوری n-1 رو منتقل می کنه مشکلم خود تابع بازگشتی یه .این که چه طوری کارش رو انجام میده.
بازهم ممنون

m.abbasi.kia
شنبه 27 مهر 1387, 22:23 عصر
خوب تابع بازگشتی هر سری با یه تابع کوچیکتر صدا زده میشه و بقیه مراحل برنامه رو
تو پشته میریزه (آدرس بازگشت از زیر برنامه) خوب حالا تا جایی این کار رو هی تکرار میکنه تا به شرط توقف برسه و بعد پشته رو پاپ میکنه. شما سعی کن واسه n های کوچیک مثل 3 یا 4 انجام بدی راحت متوجه میشی
مثلا این فرمول بازگشتی T(n)=2T(n-1)+1 حلش میشه
T(n)=2(2T(n-2)+1)+1
T(n)=2(2(2T(n-3)+1)+1)+1
.
.
.
T(n)=2^n T(1)+ n
وقتی به این مرحله میرسه کامپیوتر T(1) شرط توقف واسش برا همین همه مراحلی که فرستاده تو پشته رو یکی یکی پاپ میکنه و محاسبه میکنه