کمک در مورد برنامه ی بازگشتی

[Armanprogrammer]

کسی هست که بتونه در مورد نحوه ی قرار گرفتن داده های این برنامه در پشته و پردازش فدم به قدم اون منو یاری کنه
پیشاپیش از کمکتون ممنون

[soroush_vs]

این برنامه که بی پایانه همیشه n=3 هست و هیچ وقت n=1 نمی شه چون اصلا داده رو کم نمی کنید باید از --n استفاده کنید.

[mzjahromi]

این برنامه که بی پایانه همیشه n=3 هست و هیچ وقت n=1 نمی شه چون اصلا داده رو کم نمی کنید باید از --n استفاده کنید.
?????????????????????????????????????????

کسی هست که بتونه در مورد نحوه ی قرار گرفتن داده های این برنامه در پشته و پردازش فدم به قدم اون منو یاری کنه
پیشاپیش از کمکتون ممنون
این برنامه هانوی نیست؟
اگر اشتباه نکرده باشم و هانوی باشه دومین باری که تابع بازگشتی کال شده پارامترهاش اشتباهه

[Mahyaa]

با trace کردن و دیدن همزمان پشته ، مشکلت حل نمیشه ؟ یا من درست نفهمیدم ؟!

با هربار call شدن تابع میتونی دقیقا پشته رو ببینی مثلا

در اولین فراخوانی وضعیت پشته اینطوری میشه :
f(3,7,4,2)

دومی
f(3,7,2,4)
f(3,7,4,2)

سومی
f(1,7,4,2)
f(2,7,2,4)
f(3,7,4,2)

چهارمی
f(1,4,7,2)
f(2,7,2,4)
f(3,7,4,2)

, ...




این برنامه که بی پایانه همیشه n=3 هست و هیچ وقت n=1 نمی شه چون اصلا داده رو کم نمی کنید باید از --n استفاده کنید.
بی خیال !!!!!!!!!!!

پ.ن : اومدم نقل قول کنم دستم خورد به تشکر:(

[Armanprogrammer]

سلام دوستان

این برنامه یه توضیحی بر برنامه برج های هانویه !!
مشکل اصلی من با برج های هانویه ، که یه همچین کاری اونجا انجام میشه ؛ یعنی از داخل یه تابع Void خود تابع دوبار به صورت پشت سر هم فراخوانی داره !!

برنامه این ه :


#include<iostream.h>
#include<conio.h>
void Tower(int,char,char,char);
int i=1;
void main()
{
int n=4;
char a='F',b='H',c='T';
Tower(n,a,b,c);
}
void Tower(int n,char from,char help,char to)
{
if(n==1)
cout << i++ << "=Move a disk from " << from << " to " << to << endl << endl;

else
{
Tower(n-1,from,to,help);
cout << i++ << "=Move a disk from " << from << " to " << to << endl << endl;
Tower(n-1,help,from,to);
}
}

[mzjahromi]

کار اصلی رو توابع چاپ انجام میدن.
در واقع زمانی که برنامه به خطوط Cout میرسه مشخص میکنه که کدم میله کی و به چه صورت باید انتقال پیدا کنه. برای برنامه بازگشتی هم بهتره منطق اون رو در نظر بگیری نه Trace (البته بعضی مواقع Trace میخوان که اونم باید به صورت درختی ترسیمشون کنی والا خیلی دردسره. تو این مساله درخت دودوئی میشه که به صورت میان ترتیب پیمایش میشه.(رسمش اینجا خیلی سخته)
ولی اگر هدفت اینه که فقط درک کنی که برنامه چه کاری انجام میده باید تنها سه مرحله رو در نظر بگیرید.

1- n-1 حلقه رو از a به به b ببر با کمک c
2- حلقه n رو از a به C ببر با کمک b
3- ا n-1 حلقه رو از b به cببر با کمک c

ردیف وسط هست که کار شما رو انجام میده
امیدوارم کافی باشه

[Armanprogrammer]

ممنون از کمکتون ولی من trace شو میخوام چون این سوال یک سال کارشناسی ارشد بوده و خروجی برنامه رو میخواست البته درسته که به وسیله الگوریتم هانوی میشه حل کرد ولی اگر یک کم تغییر بدن جواب دادن بهش سخته
سوال من اینه ترتیب اجرا شدن فراخوانی تابع به چه صورته. یعنی اینکه اول فرخوانی اول رو بر میگردونه یا دوم بعد از اولین فراخوانی کدوم فراخوانی رو بر میگردونه یا تو پشته قرار میده اگر 3 تا فراخوانی بشه چکار باید کرد

[Mahyaa]

من هنوز درست متوجه نشدم سوالت چیه . وقتی صحبت از پشته میشه دیگه همه چیز یکجورایی معلومه دیگه .
شاید این سوالت رو جواب بده :(همون مثال اول که زدی)
اولی تا زمانیکه n به مقدار 1 نرسه فراخوانی میشه . یعنی با احتساب اولین فراخوانی این تابع که از بیرون از اون (مثلا همین Main خودمون) انجام شده ، ما n تا ازش تو پشته داریم .
حالا چون n=1 شده ، تابع به محلی که صدا زده شده برمیگرده (یعنی همون فراخوانی اولی) .
حالا دومی صدا زده میشه . که بسته به مقدار n یا برمیگرده و یا اولی رو دوباره صدا میکنه و همون داستان قبلی .

[mzjahromi]

ولی من trace شو میخوام چون این سوال یک سال کارشناسی ارشد بوده و خروجی برنامه رو میخواست
جوابت اینه:

تو این مساله درخت دودوئی میشه که به صورت میان ترتیب پیمایش میشه.(رسمش اینجا خیلی سخته)
هر جا دیدی یه بار تابع صدا زده شد یک نود برای درخت ایجاد کن.
بعد هم صدا زدنهای داخل یک تابع هم یک فرزند در نظر بگیر.
به هر نود مثل یک تابع جداگانه نگاه کن تا زمانیکه مقدار N آن نود 1 بشه(اون نود برگه)
درخت که ایجاد شد با پیمایش میان ترتیب به راحتی میتونی جواب رو بدست بیاری

[Armanprogrammer]

ممنون از راهنماییتون ولی خوب تمام فرمایشات شما رو هم خودم میدونم ولی این روش برای زمانی هست که تابع چیزی رو برگردونه این تابع void است و زمانی که خودشو فراخوانی میکنه باید تا آخرین خط اجرا بشه مشکل من هم همینه یعنی ترتیب اجرا شدن و هنوز هم جواب قانع کننده ای نگرفتم و به همین سادگی هم نیست چون استادم هم نتونست کمک کنه!!!!!!!

[mzjahromi]

جواب همونه
درخت رو بکش
به روش میان ترتیب پیمایش کن(درخت دودوئی است) چون

اول یک بار برنامه صدا زده میشه
یک خط نوشته میشه
و یک بار دیگز برنامه صدا زده میشه

نیاز به باز گردوندن مقدار خاصی هم نیست