من فکر کردم قراره از مرکز خونه ها حرکت کنه نه از روی مرز ها.نقل قول:
پس توی کدی که گذاشتم من تعداد حرکت ها رو N-1 و M-1 گذاشتم که باید بجاش M و N میگذاشتم:
کد:nWays = findWays(nCols, nRows);
Printable View
من فکر کردم قراره از مرکز خونه ها حرکت کنه نه از روی مرز ها.نقل قول:
پس توی کدی که گذاشتم من تعداد حرکت ها رو N-1 و M-1 گذاشتم که باید بجاش M و N میگذاشتم:
کد:nWays = findWays(nCols, nRows);
توابع بازگشتی هست دیگه.توی کد تابع findWays خودش رو صدا میزنه.اصلا بعید میدونم بدون توابع بازگشتی بشه برای هر M و N ی نوشتش.مثلا اگه M و N خیلی زیاد باشن و نخوای از بازگشتی استفاده کنی باید تعداد زیادی for بگذاری که اصلا معقول نیست..نقل قول:
انصافا برای درس شما سوال سختی هست معلومه استاد سخت گیری دارین:31: ولی اگه صورت مساله رو کامل درک کنی و مفهوم تابع بازگشتی رو بفهمی میتونی راحت بنویسیش.
هر مرحله رو توی یک خط مینویسه منتها به حالت درختی(چون نخواستم آرایه بگذارم) یعنی مثلا برای 3 در 3 خروجی این هست :نقل قول:
که اولین مسیر میشه R R R D D D دومی میشه R R D R D D که دو مرحله ی اول مسیر دوم(R R) نوشته نشده چون عینا توی مسیر اول هست.کد:R R R D D D
D R D D
D R D
D R
D R R D D
D R D
D R
D R R D
D R
D R R
D R R R D D
D R D
D R
D R R D
D R
D R R
D R R R D
D R
D R R
D R R R
مسیر سوم میشه R R D D R D که دوباره 3 مرحله ی اول مسیر سوم (R R D) چاپ نشده چون عینا توی مسیر دوم هست. الی آخر.
میشه با روشی کاری کرد که همه رو چاپ کنه (مثل آرایه) اما من خواستم ساده تر باشه تا موضوع رو بگیری بعد خودت کامل بنویسی
استاد ما هنوز تابع بازگشتی رو نگفته من خودم از کتاب جعفر نژاد قمی خوندم. خیلی سخته هر کاری می کنم نمی تونم بفهمم می تونی برام توضیح بدی؟ تو خودت چه جوری فهمیدی؟نقل قول:
استاد گفته بود که این تمرین اختیاریه و هر کی بیاره 1 نمره می گیره.
نقل قول:
يك نكته راجع به تابع بازگشتي در نظر داشته باش كه چون توابع بازگشتي با پشته stack كار مي كند، به سرعت پشته را پر كرده و اگر تعداد مراجعه به آن بيش از حد معقول باشد باعث overflow پشته خواهد شد. برنامه نويسان حرفه اي بر خلاف تصور استفاده از توابع بازگشتي را مگر در مواقع ضروري پيشنهاد نمي كنند.(جهت استحضار)
اینو تقریبا فهمیدم. میشه با آرایه هم بگی شاید اونجوری راحتتر مسئله رو بگیرمنقل قول:
سلام من توي يك برنامه يك مشكل عجيب پيدا كردم.
اين قسمتي از برنامه ي منه:
for (i=99;i>=0;i--)
B[i]=getche()-48;
B[100]=0;
for (i=0;i<=200;i++)
C[i]=0;
كه تو اين برنامه توي آرايه ي B قراره صد تا عدد بريزه و اعداد آرايه C رو هم صفر كنه اما مشكل اين جاست كه B[0] رو وقتي مي گيره از دست مي ده يعني وقتي برنامه رو اين جوري اجرا مي كنم:
for (i=99;i>=0;i--)
B[i]=getche()-48;
B[100]=0;
printf("\n%d%d",B[1],B[0]);
for (i=0;i<=200;i++)
C[i]=0;
printf("\n%d%d",B[1],B[0]);
در پرينت اول بي صفر و يك رو درست چاپ مي كنه اما در دومين پرينت مقدار بي صفر رو از دست مي ده و به جاش عدد صفر رو چاپ مي كنه!
حالا مشكل اين از كجاست؟
اگر خطوط برنامه اتان دقيقا" همين هست كه نوشتيد، احتمالا" در بخشي از برنامه []B بصورت تابعي از []C تعريف شده است. بهمين دليل است كه با تغيير []Cمقادير[] B تغيير مي كند. بررسي كنيد واگر حل نشد و تمايل داشتيد برنامه را كامل بگذاريد تا شايد بتوان مشكل را حل كرد.نقل قول:
علاوه بر اين مشكل،شما كه از ورودي عدد ميگيريد ،چرا از تابع getche استفاده كرده ايد؟
معمولا وقتی بخواهیم یه عمل تکراری رو چندین بار انجام بدیم میتونیم از توابع بازگشتی استفاده کنیم و توی تابع, خود تابع رو صدا بزنیم و با استفاده از چک کردن آرگومان ها این حلقه تا یه جایی ادامه پیدا کنه.نقل قول:
فکر کنم یه مثال ساده در مورد توابع بازگشتی تابع فاکتوریل بشه (گرچه نوشتن فاکتوریل به صورت بازگشتی از لحاظ سرعت اجرا جالب نیست اما مثال خوبیه)
ما میخواهیم تابعی بنویسیم که این !5 رو حساب کنه.توی محاسبه ی این ضرب, ما عدد 1 رو داریم که در عدد بعدیش یعنی 2 ضرب میشه.نتیجه در عدد بعدی یعنی 3 ضرب میشه.بعدی در 4 و الی آخر.یعنی یه عمل تکراری باید انجام بشه.و البته برعکس هم میشه بهش نگاه کرد.ما عدد 5 رو داریم که باید در عدد کمتر از خودش یعنی 4ضرب بشه.نتیجه باید در عدد کمتر یعنی 3 ضرب بشه تا اینکه به 1 برسیم و وقتی به یک رسیدیم دیگه کار تمومه.کد:5! = 5 x 4 x 3 x 2 x 1
تابع رو برای حالت دوم مینویسیم.
تابع(fact) فقط یک عدد(n) میگیره و فاکتوریلش رو برمیگردونه, به این صورت که اگه عدد یک بود, 1 رو برمیگردونه و در غیر این صورت, مقدار(n * fact(n-1 رو که برابر همون !n هست رو برمیگردونه.وقتی توی خود تابع, (fact(n-1 فراخوانی میشه, مسیر برنامه به اول تابع میره (مثل وقتی که توی یک تابع, یک تابع دیگه رو صدا بزنی) و n-1 رو به تابع میده.دوباره اینجا اگه n دو باشه n-1 میشه 1 و تابع 1 رو برای تابع فراخواننده(که همین تابع هست) برمیگردونه در نتیجه در تابع اول, (fact(n-1 رو برمیگردونه. اگه n بیشتر از 2 باشه دوباره توی تابع دوم تابع fact برای بار دوم صدا زده میشه (fact(n-1 -1 و مقدار در n-1 ضرب میشه و برای تابع اول فرستاده میشه.
این حلقه ی تو در تو تا جایی که n ی که برای تابع فرستاده میشه 1 نباشه ادامه پیدا میکنه و نتیجه ای که توی اولین تابع بدست میاد میشه :
میدونم شاید درست توضیح ندادم روی شکل خیلی راحتر میشه توضیح داد.اگه از یه IDE مثل Visual Studio که Debug قوی داشته باشه استفاده میکنی, با Trace کردن خط به خط این تابع خیلی راحتتر متوجه میشی که منظور چیه :کد:n * (n-1) * (n-2) * (n - 3) * ... * 1
کد:long fact(int n)
{
if (n != 1)
return n * fact(n - 1);
// else
return 1;
}
با آرایه ساده تر نمیشه اما اینجا برای اینکه خیلی پیچیده نشه از آرایه ایستا(Static) استفاده کردم(فکر کنم هنوز آرایه پویا(استفاده از new) رو نخونده باشین) واسه همین طول آرایه باید از قبل مشخص باشه و برنامه نمیتونه برای هر M و N ی نتیجه رو حساب کنه.آرایه دو بعدی رو 20 در 6 گرفتم تا نتیجه ی مساله برای حالت 3 در 3 توش ریخته بشه(20 مسیر 6 حرکتی) و چاپ بشه.ضمن اینکه باز هم واسه سادگی آرایه رو سراسری تعریف کردم و آرایه به صورت آرگومان به تابع ارسال نمیشه.اگه میخوای برای مقدار های بیشتر هم نتیجه رو ببینی باید اندازه ی آرایه رو بیشتر کنی :نقل قول:
کد:#include <iostream>
#include <windows.h>
using namespace std;
char a[20][6];
int findWays(int nRight, int nDown,int iCol = 0);
int main()
{
int nRows, nCols, nWays;
/*
cout << "Enter number of rows : ";
cin >> nRows;
cout << "Enter number of columns : ";
cin >> nCols;
*/
nRows = 3;
nCols = 3;
cout << "Number of rows : " << nRows << endl
<< "Number of cols : " << nCols << endl;
nWays = findWays(nCols, nRows);
cout << "Number Of Ways : " << nWays << endl;
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 6; j++)
cout << a[i][j] << ' ';
cout << endl;
}
return 0;
}
int findWays(int nRight, int nDown, int iCol)
{
static int iRow = 0;
if (nRight == 0 && nDown == 0)
{
iRow++;
return iRow;
}
if (nRight != 0)
{
a[iRow][iCol] = 'R';
findWays(nRight-1, nDown, iCol + 1);
}
if (nDown != 0)
{
if (nRight != 0)
for (int i = 0; i < iCol; i++)
a[iRow][i] = a[iRow-1][i] ;
a[iRow][iCol] = 'D';
findWays(nRight, nDown-1, iCol + 1);
}
return iRow;
}
تابع آرایه رو پر میکنه و بعد توی main چاپ میشه