توی بخش قبلی در مورد توابع یاد گرفتیم. یادگرفتیم که چه‌جوری توابع رو تعریف کنیم و از اون‌ها استفاده کنیم. امروز علاوه بر این که توی بحث تکنیکی کار جلو می‌ریم روی بحث الگوریتم هم یه ذره کار می‌کنیم و یک مدل الگوریتمی پرکاربرد رو هم یاد می‌گیریم.

برای شروع تمرین اول بخش قبلی رو حل می‌کنم:

قراره یه کد بنویسیم که سه‌تا عدد بگیره و به ترتیب چاپ‌شون کنه.

int Max(int a, int b)
{
if(a>=b)
return a;
return b;
}

void OrderPrint(int a, int b, int c)
{
if(c>=Max(a, b))
{
cout << c << " " << Max(a, b) << " " << a+b-Max(a, b);
}
else
{
if(c>=a+b-Max(a, b))
{
cout<< Max(a, b) << " " << a+b-Max(a, b) << " " << c;
}
else
{
cout<< Max(a, b) << " "<< c << " "<< a+b-Max(a, b);
}
}
}

 

و همون‌طور که می‌بینید کار (یه‌ذره) دشواریه چون باید همه‌ی حالت‌های ممکن بررسی بشه. اولین توضیح این که بین a و b وقتی که Max(a,b)  یکی از اعداد ماست پس a + b – Max(a,b)  اون یکی عدد می‌شه.

ما هم این‌جا اومدیم و از تابع Max استفاده کردیم تا بتونیم سه‌تا عدد رو به‌ترتیب چاپ کنیم. توی حالت اول (if اول) چک کردیم که آیا c از جفت‌شون بزرگ‌تره یا نه. توی حالت دوم وسط بودن c رو بررسی کردیم و اگر دو حالت بالا نبوده پس c حتماً از جفت‌شون کوچیک‌تره.

حالا فرض کنید که Max یه تابع ۲۰۰۰۰ خطیه که هربار صدا زدنش یک ثانیه طول می‌کشه که نتیجه بده. در این شرایط کد بالا استخون‌های هر مسئول بهینه‌سازی کد رو توی قبر می‌لرزونه. چون با این حساب برنامه‌ی ساده‌ی بالا بیش‌تر از ۸ ثانیه طول می‌کشه که جواب بده و مطمئناً این خودش بخش کوچیکی از یه برنامه‌ی خیلی بزرگ‌تره و احتمالاً ۸ ساعت طول می‌کشه که برنامه‌مون جواب بده (مثل این کار جادی که ۴۰ ساعت طول کشیده :) در صورتی که باید در کم‌تر از یک ثانیه جواب بده)

برای بهینه‌سازی تابع‌مون چون مقادیر a و b تغییر نمی‌کنه خیلی راحت می‌تونیم از همون اول a و b رو به ترتیب مرتب کنیم و دیگه از تابع Max استفاده نکنیم. پس کدمون این‌جوری می‌شه:

void OrderPrint(int a, int b, int c)
{
	b=a+b-Max(a,b);
	a=Max(a,b);
	if(c>=a)
	{
		cout << c << " " << a << " " << b;
	}
	else
	{
		if(c>=b)
		{
			cout<< a << " " << b << " "  << c;
		}
		else
		{
			cout<< a  << " "<< c << " "<< b;
		}
	}
}

 

که همون اول کار از مقادیر اصلی a و b صرفنظر کردیم و بر اساس بزرگی و کوچیکی مقدارشون رو تغییر دادیم.

یکی از نکات جالبی که شما توی توابع شاهدش هستید اینه که می‌شه چندتا تابع با اسم یکسان توی برنامه داشته‌باشیم. البته برای این که کامپایلر گیج نشه (گیج شدن = کامپایل ارور!) باید این توابع هم‌نام تفاوت‌هایی داشته باشن. تفاوت‌ها می‌تونن در تعداد و نوع ورودی‌های تابع و نوع خروجی تابع باشن

توی تمرین (تحقیق!) دوم شما باید دنبال راهی (در صورت وجود!) می‌گشتید (که اتفاقاً وجود داره! دنبال نخود سیاه که نمی‌فرستم‌تون!) که بتونم تابعی که قراره استفاده کنیم رو زیر (بعد از) تابع فعلی‌مون بنویسیم. مثلاً اگر می‌خوایم از HelloWorld توی main استفاده کنیم، اون رو زیر main تعریف کنیم نه بالای main (اگر یادتون رفته باید بگم که سی‌پلاس‌پلاس فقط در صورتی می‌تونه از تابع استفاده کنه که اون رو قبلش تعریف کرده باشید)

خوب راه‌حل تقریباً جلوی چشم شماست! همون‌طور که بالا گفتم «سی‌پلاس‌پلاس فقط در صورتی می‌تونه از تابع استفاده کنه که اون رو قبلش تعریف کرده باشید» و برای تعریف تابع فقط کافیه خصوصیات‌ش رو توی کد بنویسیم. (بعله! لازم نیست کروشه رو باز و بسته کنیم و توش کدهای تابع رو بنویسیم. البته به ; نیازه!)

مثلاً اگه می‌خواهیم HelloWorld رو بعد از main بنویسیم، کدمون این‌جوری می‌شه:

void HelloWorld();

int main()
{
HelloWorld();
return 0;
}

void HelloWorld()
{
cout << "Hello World”;
}

 

و اگر برنامه رو اجرا کنیم (که باید اجراش کنید! اصلاً تمام مثال‌ها و تمرین‌هایی که میگیرید رو باید حل و اجرا کنید!)

می‌بینیم که بدون هیچ مشکلی تابع HelloWorld اجرا می‌شه در حالی که کد اصلی‌ش رو زیر تابع main نوشتیم.

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

int main()
{
double a,b,c,avg;
int i=0;
cin >> a >> b >> c >> i;
avg=(a+b+c)/3;

cout << avg;

if(i==0)
{
cout << a;
}

if(i==1)
{
cout << b;
}

if(i==2)
{
cout << c;
}
}

 

کاری که توی کد بالا انجام می‌دم اینه که سه تا متغیر برای نمرات و یه متغیر برای شماره‌ی نمره‌ی درخواستی تعریف می‌کنم و نمرات و شماره‌ی نمره‌ی درخواستی رو می‌گیرم، میانگین و نمره‌ی درخواستی رو هم چاپ می‌کنم.

توی کد بالا مخصوصا عدد نمره‌ی درخواستی رو از ۰ شروع کردم. یعنی نمره‌ی اول عددش صفره، نمره‌ی دوم یک و نمره‌ی سوم دو. حالا دلیل‌ش رو تا چند دقیقه‌ی بعدی متوجه می‌شیم!

خوب این کاری بود که برای سه تا نمره انجام دادیم. حالا اگر بخواهیم همین فرآیند رو برای ۲۰ تا داوطلب کنکوری انجام بدیم و درسدهاشون توی دروس دیفرانسیل، گسسته، هندسه، فیزیک و شیمی رو ذخیره‌کنیم و مثلا درصد گسسته‌ی داوطلب ۱۸ام رو بخوایم باید چی‌کار کنیم؟ اگر بخواهیم همین شیوه رو ادامه بدیم باید ۲۰ تا متغیر تعریف کنیم و در ازای هر کدوم هم a1 تا a5 داشته باشیم و در ازای هرکدوم ۵ تا شرط. یعنی ۱۰۰ تا شرط تو در تو.

حالا فرض کنید شرط ۷۸ام رو اشتباه بنویسید و برنامه درست جواب نده. حالا بیا و درست‌ش کن!

مشکلاتی مثل این و حتی مشکلاتی پیچیده‌تر (مثل نتایج کنکور سراسری ۹۳ با یه چیزی حدود ۱ میلیون داوطلب) و انواع دیگه‌ی مشکلات باعث به وجود اومدن راه‌حلی به اسم آرایه شد. آرایه در واقع یه چیزی مثل یه کتابخونه‌ست که تو هر طبقه‌ش می‌شه یه مقداری ذخیره کرد. به بیان بهتر آرایه یه چیزی مثل اینه:

{شکل آرایه}

که تو هر خونه‌ش یه مقداری ذخیره می‌شه.

برای تعریف آرایه ما نیاز داریم که اسم آرایه، نوع خونه‌هاش (که همه‌ی خونه‌ّهاش هم‌نوع هستن) و تعداد خونه‌ّهاش رو بدونیم. و در ضمن باید بدونیم که هر خونه‌ی آرایه دقیقا به اندازه‌ی همون نوع متغیر فضا از رم می‌گیره (و باید در مصرف آرایه هم صرفه‌جویی کنیم )

حالا اگر بخواهیم آرایه‌ای برای میانگین درصد ۲۰تا داوطلب توی آزمون آزمایشی درست کنیم باید از این ساختار استفاده کنیم: double a[20]. یعنی کافیه نوع متغیر رو بنویسیم، اسم آرایه رو بنویسیم و بعدش یه کروشه باز کنیم و تعداد خونه‌های آرایه رو بنویسیم.

مهمه که بدونید که تعداد خونه‌ّهای آرایه رو حتما باید تعریف کنید و این‌که این تعداد نمی‌تونه یه متغیر دیگه باشه و حتما باید عدد ثابت باشه. البته اگر بخواهید توی ورودی‌های تابع یه آرایه رو ورودی بگیرید نباید دیگه تعداد خونه‌ّهای آرایه رو بنویسید و فقط باید کروشه رو بازکنید و ببندید.

برای دست‌رسی به خونه‌ی nام آرایه باید از ساختار a[n] استفاده کنید. یعنی اسم آرایه، کروشه باز، این‌بار شماره‌ی خونه و کروشه بسته. اصطلاحا به n اندیس اون خونه هم گفته می‌شه. و درضمن برای اندیس آرایه می‌تونید از متغیر هم استفاده کنید.

مهمه که بدونید که اندیس خونه‌ی nام، n-1هست‌ش. یا به یه زبون دیگه شماره‌ی خونه‌ی آرایه‌ها از 0 شروع می‌شه نه از ۱. برای همین هم موقع آموزش for از ۰ شروع می‌کردیم و یا توی مثال اول هم از ۰ شروع کردیم.

اون مثال ۲۰تا داوطلب این‌جوری می‌شه:

int main()
{
double a[5],avg=0;
for(int i=0;i<5;i++)
{
cin >> a[i];
avg+=a[i];
}

avg/=5;
cout << avg << endl;

int i;
cin >> i;
cout << a[i];

}

 

توی خط اول نوع متغیر رو نوشتم، بعد یه آرایه به اسم a تعریف کردم و بعد از تعریف a یه متغیر دیگه (که آرایه) نیست به اسم avg تعریف کردم. هدف این بوده که بگم می‌شه با یک بار نوشتن نوع متغیر بی‌شمار آرایه و بی‌شمار متغیر پشت سر هم تعریف کرد.

خوب فکر کنم این نکته واضح باشه که اندیس آرایه باید از تعداد خونه‌های اون کم‌تر باشه و از صفر بیش‌تر. و نوع اندیس عدد طبیعیه. یعنی خونه‌ی ۲.۷۵ نداریم و خونه‌ی رادیکال ۲ هم نداریم ولی مثلا خونه‌ی «حد تابع f(x)=[x]-[-x] وقتی x به یه عدد صحیح میل می‌کنه» داریم  چون حدش همیشه برابره با -۱.

دیگه نکته‌ای از آرایه به ذهنم نمی‌رسه! بریم سراغ بخش بعد…

موضوع دیگه‌ای (و موضوع آخری) که می‌خوایم در موردش بحث کنیم تابع‌های بازگشتی هستن. توی توابع ساده ما یه مقداری رو ورودی می‌گرفتیم و یه مقداری رو خروجی می‌دادیم. حالا به نظرتون چه اتفاقی میوفته اگه ما یهویی دستمون به کیبورد بخوره و توی تابع خود تابع رو صدا بزنیم؟

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

مثلا HelloWorld زیر تا بی‌نهایت اجرا می‌شه به شرطی که یه بار از توی main صداش بزنیم.

void HelloWorld()
{
cout << "HW";
HelloWorld();
}

 

ولی در شرایط خاص و پرکاربردی این صدا زدن تابع از توی تابع خیلی کار ما رو راحت‌تر می‌کنه و حتی کلی خط کد رو به چند خط ناقابل تبدیل می‌کنه.

برای این‌که بیش‌تر با مبحث آشنا بشید یه بازگشتی می‌زنید به مبحث دنباله‌ها (چون من تازگی‌ها رسما باهاشون آشنا شدم برای من «بازگشت» معنی نداره :) ) که توی پیش‌دانشگاهی باهاش آشنا شدید (اگر قبل‌ش آشنا شدید که چه بهتر، نشدید هم توضیحات رو متوجه می‌شید)

دنباله یه دنباله‌ای از اعداده! که معمولا با هم رابطه دارن (البته لزومی هم نداره که با هم رابطه داشته باشن). به هر عدد یه جمله‌ی دنباله گفتن می‌شه و مثل آرایه‌ها (یا بهتره بگم آرایه‌ها مثل دنباله‌ها!) هر جمله‌ی دنباله هم با یه اندیس مشخص می‌شه.

یک نوعی از دنباله‌ها دنباله‌های بازگشتی هستن. یعنی جملات‌شون با توجه به جملات قبلی‌شون مشخص می‌شه (به جمله‌ی قبل بازگشت می‌کنن). یکی از معروف‌ترین این دنباله‌ها دنباله‌ی فیبوناچی (یا به قول معلم دیفرانسل‌مون فیبوناتچی!) هست‌ش که جمله‌ی nام‌ش برابر حاصل جمع دو جمله‌ی قبلی خودشه و جمله‌ی اول و دومش هم یکه. (دقت کنید که اگر دو جمله‌ی اول رو مشخص نکنیم مثل صدا زدن تابع از توی خود تابع دور بی‌نهایت به وجود میاد). یعنی این‌جوری می‌شه ۱ ۱ ۲ ۳ ۵ ۸ ۱۳ ۲۱ ۳۴ ۵۵

خوب این پیش‌نیاز اول مبحث بود.

توی توابع بازگشتی مثل دنباله‌ی بازگشتی نیاز به یه نقطه‌ی شروع (در واقع نقطه‌ی پایان) داریم. یعنی جایی که تابع دیگه خودش رو از اون‌جا صدا نزنه. برای همین به شکل کلی ابتدای توابع بازگشتی یه if می‌ذارن و توش شروط اولیه (مثلا جملات اول و دوم توی دنباله‌ی فیبوناچی برای تابعی که می‌خواد دنباله‌ی فیبوناچی به‌دست بیاره) رو قرار می‌دن و حتما هم توی اون if یه مقداری رو خروجی می‌دن. و بعد از اون if هم چندخط کد که توش دوباره تابع صدا زده می‌شه.

دقت کنید که جایی تابع دوباره صدا زده می‌شه مثل return عمل نمی‌کنه و بعد از اتمام بازگشت‌های تابع بازگشتی (که با if جلوی دور بی‌نهایت رو گرفتیم) تابع دوباره کارش رو ادامه می‌ده (دقت کنید که توی همه‌ی اون بازگشت‌ها هم تابع بازم تا آخر تا جایی که به return برسه ادامه می‌ده)

مثلا تابع بازگشتی فیبوناچی (یافتن جمله‌ی nام دنباله) این‌جوری می‌شه:

int fib(int n)
{
if(n==1 || n==2)
{
return 1;
}

return fib(n-1)+fib(n-2);
}

 

به همین سادگی به همین خوشمزگی.

البته اگرهم متوجه نشدید نگران نباشید. در طی زمان (مثلا وقتی برسیم به سوال‌هایی که به الگوریتم نیاز دارن) کم‌کم متوجه می‌شید. مثلا من سال دوم راهنمایی این مفهوم رو متوجه شدم ولی تا سوم دبیرستان (مسابقات برنامه‌نویسی بیان) زیاد استفاده‌ی خاصی ازش نکردم.

البته دونستن این نکته مهمه که یه جاهایی توابع بازگشتی باعث می‌شن که دیباگ (رفع اشکال) برنامه خیلی سخت بشه و برای همین پیشنهاد می‌شه تا وقتی در استفاده از اون‌ها خبره نشدید سراغ‌شون نرید.

برای جلسه‌ی بعد:

توی همه‌ی تمرین‌های پایین سعی کنید تابع‌تون رو بعد از main تعریف کنید.

– ب.ب.ک میانگین درسد ۱۰۰تا داوطلب رو بگیره (چک کنه که از صفر کم‌تر و از ۱۰۰ بیش‌تر نباشه) و میانگین همه‌ی اون‌ها، بیش‌ترین درسد، کم‌ترین درسد و اندیس داوطلبی که نزدیک‌ترین درسد به میانگین رو داشته یا بالاترین درسد یا پایین‌ترین درسد بوده رو حساب کنه.

– اگر توی تابع‌ها دقت کرده باشید وقتی یه متغیر رو به تابع می‌فرستیم و توی تابع مقدار اون متغیر رو عوض می‌کنیم، مقدار متغیر اصلی تغییری نمی‌کنه. در صورتی که (الان باید متوجه بشید که!) وقتی یه آرایه رو به تابع می‌فرستیم و مقدارش رو توی تابع عوض می‌کنیم، مقدار آرایه‌ی اصلی هم عوض می‌شه. تحقیق کنید که چرا این اتفاق میوفته (من اسم‌ش رو می‌ذارم سازوکار متغیرها! با تشکر از درس شیمی!)

– توی تابع بازگشتی فیبوناچی برای محاسبه fib(n)  ما یه بار fib(n-1)  رو حساب می‌کنیم (که توی اون یه بار fib(n-2)  هم حساب می‌شه) و یه بار دیگه هم جداگانه fib(n-2)  رو حساب می‌کنیم. و اگر یه ذره شهودی به قضیه نگاه کنیم می‌بینیم که اگر n بزرگ باشه این تکرارها خیلی زیاد می‌شه و باعث کندی تابع می‌شه. آیا پیشنهادی برای رفع این مشکل دارید؟
– به نظرتون چجوری می‌شه درصدهای درس دیف، گسسته، هندسه، فیزیک و شیمی ۱۰۰تا داوطلب رو توی آرایه ذخیره کرد؟ به نظرتون راهی بهتر از تعریف ۱۰۰تا آرایه‌ی ۵تایی یا ۵تا آرایه‌ی ۱۰۰تا وجود داره؟

– آیا راهی وجود داره که تابع fib‌ رو توی یک خط خلاصه کرد؟ (آقا به خدا وجود داره! من کردم! منظورم اینه که برید دنبالش پیداش کنید!) (راهنمایی: ساختار بازگشتی تابع رو عوض نکنید!) (راهنمایی۲: شرط‌ها رو به‌جز با if به یه شکل ساده‌تر دیگه هم می‌شه نشون داد)