آموزش ++C – مثالهای کاربردی

۲ دیدگاه

در این آموزش قصد دارم به تشریح چند مثال کاربردی بپردازم. قبل از اینکه مثالها را بررسی کنم چند سوال مطرح میکنم. به نظر شما چند درصد احتمال دارد شما استخدام شرکتی شوید که از شما خواسته شود برنامه ای بنویسید که یک آرایه دریافت کند و آرایه را به صورت صعودی مرتب کند؟ یا اینکه برنامه ‌ای بنویسی که در یک ماتریس به دنبال بزرگترین عدد بگردد؟! اگر به همه مثالهایی که در این سایت (یا در منابع دیگر آموزشی) مطرح شده است دقت کنید متوجه خواهید شد که هیچ شرکت یا سازمانی به شما بابت حل این مسائل حقوق نمی‌دهد. پس چرا در آموزشهای برنامه‌ نویسی این مثال ها مطرح شده اند؟
یک پاسخ ساده به این سوال اینست که شما در حال یادگیری زبان برنامه نویسی هستید و باید به صورت پله ای و گام به گام سختی سوالات پیش برود. در خان اول برنامه نویسی نمی‌توان ساخت نرم افزار حسابداری را آموزش داد. اما این همه ماجرا نیست؛ از یک زاویه دیگر می‌توان به این سوال نگاه کرد:
هیچ شرکتی وجود ندارد که بابت مرتب سازی آرایه از شما کمک بخواهد، اما شرکتهایی هستند که مسائل بزرگی برای برنامه‌نویسی دارند که بخشی از حل مساله بزرگ، مرتب‌سازی آرایه است. اما آیا در صورت مساله مشخص شده است که در حل این مثال به مرتب‌سازی آرایه نیاز داریم؟ قطعا نه! هنری که یک برنامه‌نویس به مرور زمان باید کسب کند هنرِ مدل‌بندی مساله است. در مسائل واقعی که با آن روبرو می‌شوید هیچ حرفی از آرایه و ماتریس و متغیر مطرح نمی‌شود. این شما هستید که باید تشخیص دهید که در مساله به چه ساختمان داده هایی (مثل متغیر و آرایه) و چه الگوریتم هایی نیاز دارید. در این نوشته با هنر حل مساله که همان مدل‌بندی مساله است آشنا می‌شوید.

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

هنر یک برنامه‌نویس این است که مساله را به خوبی تحلیل کند و به یک مدل مناسب برای کدنویسی دست یابد. مدل بندی مساله آنقدر اهمیت دارد که می‌توان از آن به هنر حل مساله یاد کرد.

نرم‌افزارهای مسیریاب

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

سوالی که ممکن است پیش بیاید این است که برنامه ما چگونه باید این نقشه را از ورودی دریافت کند؟ فرض کنید نقشه را دریافت کردید، چگونه باید اعداد روی نقشه را تشخیص دهیم؟ چگونه بفهمیم که فاصله بین شیراز و شهرهای دیگر چقدر است؟ اگر بخواهید نقشه را به صورت خام از ورودی دریافت کنید قطعا کار سختی در انتظار شماست. اما چه باید کرد؟ ما مدل بندی این مساله را با استفاده از ماتریسها انجام می‌دهیم. چگونه؟
دوباره به نقشه بالا نگاه کنید. فاصله شیراز تا فسا چند کیلومتر است؟ ۱۵۲!
حال به ماتریس زیر دقت کنید. سطر شیراز و ستون فسا چه عددی نوشته شده است؟ ۱۵۲! یعنی برای مدل بندی مساله به تعداد شهرها، سطر و ستون داریم (توجه داشته باشید در ماتریس زیر برای خلوت تر شدن و ساده تر شدن مثال فقط ۴ شهر در نظر گرفتیم). حال در ماتریس سطر لار وستون جهرم را پیدا کنید. چه عددی است؟ ۱۶۴. که در نقشه بالا فاصله لار تا جهرم هم ۱۶۴ کیلومتر است. پس به جای اینکه در مساله با نقشه کار کنیم (که کار سخت و نشدنی است) بر روی ماتریس متمرکز می‌شویم.

بد نیست کمی در مورد این ماتریس صحبت کنیم. با دقت به ماتریس می‌بینید که عناصر روی قطر اصلی ماتریس صفر هستند. مثلا چرا مقدار A[0][0] صفر است؟ چون فاصله شیراز به شیراز و اساسا فاصله هر شهر با خودش صفر است!
همچنین برای شهرهایی که مسیر مستقیم به یکدیگر ندارند (منظور از مسیر مستقیم بین دو شهر مسیری است که در طی آن شهر سومی وجود ندارد) از علامت بی‌نهایت استفاده کردیم. مثلا به این دلیل که بین شیراز و لار مسیر مستقیمی وجود ندارد از علامت بی نهایت استفاده شده است. (توجه داشته باشید که برای سفر از لار به شیراز ابتدا باید از لار به جهرم برویم (یعنی A[0][2]) و سپس از جهرم به شیراز برویم (یعنی A[2][0]) اما چون مسیر مستقیمی بین این دو شهر نیست A[0][1] و A[1][0] بی نهایت است)
نکته دیگری که باید به آن توجه کنیم این است که در برنامه نویسی از نماد بی نهایت نمی‌توان استفاده کرد. چون این نماد در سینتکس سی پلاس پلاس تعریف نشده است. اما در الگوریتم ها و شبه کدهای مسیریابی بین شهرهایی که مسیر مستقیمی برای آن تعریف نشده است از این نماد استفاده می‌شود.بنابراین اگر بخواهید این ماتریس را از ورودی دریافت کنید می‌توانید قرار داد کنید و به جای بی‌نهایت از یک عدد خیلی بزرگ استفاده استفاده کنید.

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

اگر این کد را اجرا کنید متوجه می‌شوید که در خروجی صفر چاپ می‌شود. علت آن هم واضح است. زیرا متغیر min را با A[0][0] مقدار دهی اولیه کرده‌ایم (که مقدارش صفر است) و در خط ۱۶ A[i][j] را min مقایسه کردیم که ممکن است A[i][j] صفر باشد. پس این قسمت از کد را میتوان به این صورت اصلاح کرد:


نکته بعدی که ممکن است شما هم متوجه آن شده باشید این است که صورت مساله از ما فاصله نزدیکترین دو شهر را نخواسته است. بلکه نام نزدیکترین دو شهر را می‌خواهد. مثلا انتظار می‌رود که در ماتریس بالا نام جهرم و فسا در خروجی چاپ شود، در صورتی که کد بالا ۹۰ را چاپ می‌کند. بدیهی است که باید کد را به گونه ای اصلاح کنیم که نام شهرها چاپ شود نه فاصله شهرها. توصیه می‌کنم قبل از خواندن ادامه آموزش کمی در مورد حل این مشکل فکر کنید.

در مثال ۵ آموزش آرایه بزرگترین عدد آرایه را پیدا کردیم. در آن مثال به دو روش مساله حل شد. هم بزرگترین عنصر آرایه را پیدا کردیم و هم اندیس بزرگترین عنصر آرایه. اگر روش پیدا کردن اندیس را فراموش کرده‌اید دوباره به این مثال نگاه بیندازید.

در واقع در این مثال هم ما به دنبال اندیس سطر و ستون کوچکترین عنصر آرایه هستیم. یعنی ۲ و ۳ . (چون A[2][3] کوچکترین عنصر آرایه است. اما باز هم مشکل حل نشده است! چون ما به دنبال ۲ و ۳ نبودیم، به دنبال جهرم و فسا هستیم! بدون توضیح اضافه کد نهایی مساله را ببینید تا متوجه شوید چگونه این مشکل حل شده است:

توضیح کد:
در خط ۱۳ تا ۱۹ اندیس کوچکترین عدد ماتریس پیدا شده است. باز هم تکرار میکنم، اگر در فهم این قسمت مشکل دارید مثال ۵ آموزش آرایه را دوباره بخوانید.
در خط ۲۲ تا ۳۴ تابعی به نام find_city تعریف شده است که عدد دریافت می‌کند و نام شهر را برمی‌گرداند. مثلا find_city(0) شیراز را برمیگرداند find_city لار. بنابراین عددی که به این تابع ارسال می‌شود همان اندیس‌هایی خواهد بود که در خط ۱۳ تا ۱۹ پیدا شده است.

در این مثال با یک مدل‌بندی ساده ولی بسیار کاربردی آشنا شدید. ولی ممکن است این سوالات در ذهنتان بوجود بیاید:

سوال: در این کد کاربر باید فاصله ها را به صورت دستی وارد برنامه کند. آیا در گوگل مپ هم به این صورت دیتابیس را مقداردهی کرده‌اند؟
پاسخ: خیر. دیتای نقشه از داده‌های جغرافیایی بدست می‌آید که از حوصله این نوشته خارج است. مساله نقشه و مسیریابی یک مساله ساده و پیش و پا افتاده نیست که بتوان در این نوشته توضیح داد. هدف از مطرح کردن این سوال آشنا شدن شما با نحوه مدل بندی مساله بود. با این نوع مدل‌بندی مساله شما قادر خواهید بود طیف زیادی از مسائل مربوط به نقشه را حل کنید. مثلا:
-یافتن همه شهرهایی که مسیر مستقیم به شیراز دارند
-یافتن شهری که بیشترین مسیر مستقیم به شهرهای دیگر دارد.

سوال: در کد بالا نزدیکترین دو شهر به هم را پیدا کردیم. آیا می‌توان با همین ایده دورترین دو شهر از هم را پیدا کرد؟ یعنی در ماتریس بزرگترین عدد ماتریس را پیدا کنیم؟
پاسخ: خیر. اگر به ماتریس بالا دقت کنید می‌بینید که ۱۸۸ بزرگترین عدد است، یعنی شیراز و جهرم دورترین شهرها از یکدیگر هستند. اما با دقت به تصویر می‌بینید که لار وشیراز دورترین شهرها از یکدیگر هستند. این مساله به همراه مساله کوتاهترین مسیر بین دو شهر دلخواه با الگوریتمهای پویا قابل پیاده سازی هستند که مطرح کردن این الگوریتمها به پیش‌نیازهایی نیاز دارد. دانشجویان کامپیوتر این مسائل را در درس طراحی الگوریتم و در ترم ۴ یاد میگیرند. توجه داشته باشید که در مساله کوتاهترین مسیر بین دو شهر دلخواه لزومی بر وجود مسیر مستقیم بین دو شهر نیست. مثلا کوتاهترین مسیر بین شیراز و آباده این است که از شیراز به مرودشت برویم و از مرودشت به آباده. (در صورتی که مسیر مستقیمی بین آباده و شیراز وجود ندارد)

بازی کندی کراش

اگر شما هم به بازیهای موبایلی علاقه دارید احتمالا یک بار هم که شده بازی کندی کراش یا بازیهای شبیه به این را بازی کرده‌اید. در این بازی لازم است آبنبات‌های یکسان را به تعداد حداقل سه تا در کنار هم قرار دهید تا از صفحه‌ی بازی حذف شوند.

پیاده سازی این بازی با این طراحی و گرافیک به دانش برنامه‌نویسی موبایل نیاز دارد. اما قسمت اصلی این بازی (که تشخیص آبنباتهای کنار هم است) و نیاز به کد نویسی دارد را می‌توان به مدلی که در ادامه توضیح می‌دهیم ساده کرد. در شکل بالا ۶ نوع آبنبات مشاهده می‌کنید. در کد نویسی برای هر آبنبات یک عدد در نظر میگیریم. اعداد ۱ تا ۶. از ظاهر بازی به راحتی می‌توانید تشخیص دهید که این مساله هم به ماتریس ها نیاز دارد. بدون هیچ توضیح اضافه‌ای تصویر زیر را ببینید:

پس در الگوریتم مساله ما با ماتریس سمت چپ کار داریم، نه تصویر سمت راست! حال که با منطق و مدل مساله آشنا شدید، بدون اینکه به کلیت مساله خللی ایجاد شود صورت سوال را به این صورت در نظر بگیرید:

برنامه‌ای بنویسید که از ورودی ماتریسی شامل اعداد ۱ و ۲ دریافت کند. سپس درایه مشخصی از ماتریس را دریافت کند و همه همسایه های این درایه که عدد برابر با درایه مشخص شده دارند را صفر کند. تصویر زیر صورت مساله را بهتر نشان می‌دهد.

برای نوشتن این کد اولین قدم پیدا کردن همسایه هاست. در شکل بالا (ماتریس ۱) کاربر با وارد کردن ۳ و ۱، A[3][1] را انتخاب میکند. در قدم اول الگوریتم، ۴ همسایه این خانه باید مشخص شود. یعنی:
همسایه بالا: A[2][1] که در آن عدد ۱ ذخیره شده است.
همسایه پایین: A[4][1] که در آن هم عدد ۱ ذخیره شده است.
همسایه راست: A[3][2] که در آن عدد ۲ ذخیره شده است.
همسایه چپ: A[3][0] که در آن عدد ۱ ذخیره شده است.

از بین این همسایه ها، کدام همسایه را باید گسترش دهیم؟ همسایه هایی که مقدارشان ۱ است (چون A[3][1] یک ست): پس همسایه بالا، همسایه چپ و همسایه پایین باید به همین طریق گسترش پیدا کنند و همسایه های جدیدی که مقدارشان یک است را به مجموعه اضافه کنند. پس در قدم اول باید در مورد این مساله فکر کنیم که اگر درایه r و c از کاربر دریافت کنیم چهار همسایه A[r][c] را چگونه می‌توان پیدا کرد (توجه داشته باشید که r مخفف row به معنی سطر و c مخفف column به معنی ستون است و در مثالی که دنبال می‌کنیم r=3 و c=1 است)

در ادامه کدی مینویسیم که ماتریس A از ورودی دریافت می‌کند، سپس r و c را دریافت می‌کند و با ارسال r، A و c به تابعی، چهار همسایه A[r][c] را چاپ کند.
(لطفا قبل از خواندن کد، سعی کنید خودتان چهار همسایه A[r][c] را تشخیص دهید.)

توضیح کد:
۱- برای ارسال آرایه یک بعدی به تابع دقیقا مانند ارسال متغیر عمل میکنیم. با این تفاوت که باید [] در کنار نام آرایه قرار گیرد. مثلا:

در خط ۱ متغیر x به عنوان پارامتر ورودی تابع دریافت شده است و در خط دوم آرایه یک‌بعدی A به عنوان ورودی تابع دریافت شده. اما در ارسال آرایه دو بعدی کمی متفاوت است و باید اندیس بعد دوم را به صورت ثابت در براکت قرار دهیم یعنی به این صورت:

۲- عنصر A[r][c] را در نظر بگیرید. همسایه سمت راست A[r][c] دقیقا هم ردیف با این عنصر است و ستون آن یکی بیشتر از این عنصر است.
بنابراین همسایه سمت راست A[r][c] این عنصر است: A[r][c+1]. با همین استدلال همسایه سمت چپ A[r][c] این عنصر است: A[r][c-1]
به طریق مشابه همسایه بالایی A[r][c] در ردیف بالا و در همان ستون است. پس :A[r-1][c] و همسایه پایینی : A[r+1][c]

۳- نکته مهمِ چاپِ همسایه های A[r][c] جایی است که این عنصر حداقل یکی از همسایه‌ها را نداشته باشد. مثلا اگر r=0 , c=0 باشد آنگاه A[r][c] همسایه بالا و چپ ندارد. بنابراین کد بالا در درایه های مرزی با خطا مواجه می‌شود. پس در تکمیل کد حتما باید این مورد را در نظر بگیریم.

برای ادامه کدنویسی ابتدا اسم تابع print_neighbors را تغییر می‌دهیم به check_neighbors . به این دلیل که قرار است در این تابع چک کنیم که آیا مقدار همسایه های A[r][c] با مقدار A[r][c] برابر است یا نه. در صورتی که هر کدام از همسایه ها با A[r][c] برابر بود باید همین سناریو را برای آن همسایه تکرار کنیم. پس تابع check_neighbors را به صورت زیر می‌نویسیم:

توضیح کد:
۱- در توضیح کد قبل، مورد ۳، در مورد درایه های مرزی هشدار دادیم که می‌تواند به تولید همسایه های نامعتبر منجر شود. بنابراین در خط ۳ و ۴ صحت اندیس r و c را چک میکنیم اگر خارج از محدوده معتبر باشد دستور ;return منجر به خروج از تابع می‌شود و بقیه دستورات اجرا نمی‌شود.
(در بحث تابع همیشه مقداری را برمیگرداندیم، مثلا ;return fact مقدار fatc را برمیگرداند. اما اگر دقت کنید نوع برگشتی تابع check_neighbor از نوع void است. یعنی قرار نیست این تابع مقداری را برگرداند. بنابراین از دستور ;return استفاده شده است)

۲- در خط ۶ مقدار A[r][c] در متغیر item ذخیره شده است. به این دلیل در item ذخیره میکنیم که در خط ۸ مقدار A[r][c] برابر صفر می‌شود (زیرا در صورت مساله خواسته شده است) و در ادامه کد به این مقدار نیاز داریم.

۳-در خط ۱۲ شرط c-۱>=۰ وجود همسایه چپ را چک میکند. اگر به یاد داشته باشید گفتیم A[0][0] همسایه چپ ندارد. همانطور که میبنید این شرط برای A[0][0] مقدار false را برمیگرداند و به درستی نشان میدهد که همسایه چپ وجود ندارد. اگر شرط اول (c-1>=0) درست باشه آنگاه شرط دوم را چک میکند:
A[r][c-۱] == item
تساوی این شرط نشان می‌دهد که مقدار A[r][c] با مقدار همسایه چپ برابر است. پس چه اتفاقی باید رخ دهد؟ همسایه چپ را باید گسترش دهیم. یعنی همان سناریویی که برای A[r][c] داشتیم اینبار باید برای A[r][c-1] اتفاق بیفتد. پس تابع check_neighbor را این بار با پارامت r و c-1 فراخوانی میکنیم یعنی: check_neighbor(A,r,c-1);

۴- با همین توضیحات کدهای ۱۵ تا ۲۴ برای همسایه های راست، بالا و پایین نوشته شده است.

حال می‌توانیم کد کامل این مثال را بنویسیم:

توضیح کد:
در خط ۱۳ تا ۱۵ ماتریس دریافت می‌شود و در خط ۱۸ تا ۲۲ همان ماتریس چاپ می‌شود تا کاربر ماتریس وارد شده را ببینید. در خط ۲۵ مقادیر r و c دریافت می‌شود. (در شکل زیر ماتریس سمت راست را به برنامه داده‌ایم. همچنین مقادیر r و c را ۱ وارد کرده‌ایم.)
در ادامه کد تابع اصلی فراخوانی می‌شود. در خط ۲۷ این دستور ;check_neighbor(A,r,c) اجرا می‌شود. توضیحات این تابع بالاتر مطرح شده است. در پایان در خط ۲۹ تا ۳۲ ماتریس خروجی چاپ می‌شود.

برگردیم به مثال کندی کرش! در آن مثال آبنبات‌ها را به اعداد ۱ تا ۶ مدل کردیم. برای راحتی کار فرض کردیم که فقط اعداد ۱ و ۲ در ماتریس وجود دارد. و براساس آن کد مساله را نوشتیم. اگر به کدها دقت کنید متوجه می‌شوید که کد فقط مختص اعداد ۱ و ۲ نیست و به ازای همه اعداد به درستی کار می‌کند. احتمالا برایتان قابل تصور است که توانستیم منطق بازی را به خوبی پیاده کنیم. برای تکمیل این بازی کافیست جای اعداد صفری که تولید میشود اعداد جدید قرار گیرند. و صد البته یک نمایش گرافیکی مناسب داشته باشد.

امیدوارم که از خواندن این آموزش لذت برده باشید. در قسمت نظرات می‌توانید در مورد مساله های واقعی و کاربردی شبیه به این مساله ها و نحوه مدل بندی مساله هایشان صحبت کنیم.

  • نویسنده
    حمید جهانگیری
  • تعداد بازدید
    836
۲دیدگاه فرستاده شده است.
شما هم دیدگاه خود را بنویسید
  1. سهیل :
    ۰۱ اردیبهشت ۹۹

    مطلب خیلی خوبی بود. ای کاش در پستهای بعدی بازیها و نرم افزارهای دیگه هم به این صورت بررسی کنید

    • حمید جهانگیری :
      ۰۱ اردیبهشت ۹۹

      سلام. ممنون.
      نکته ای که فرمودید رو حنما در آموزشهای بعدی لحاظ میکنم

نوشته‌های ویژه
اخبار ویژه

با عضویت در خبرنامه، تازه‌ترین نوشته‌های وبلاگ را در ایمیل‌تان دریافت کنید.
برای عضویت نشانی ایمیل خود را وارد کرده و بر روی دکمه عضویت کلیک نمایید.