این برنامه مربوط به بازی دوز (بازی TicTacToe) است که به زبان سی پلاس پلاس و با استفاده از شیءگرایی و مفهوم کلاس نوشته شده است. در این پروژه برای محیط بازی یک آرایه دو بعدی ۳ در ۳ در نظر گرفته شده و دو بازیکن با هم به رقابت می پردازند.
شکل زیر نمونه ای از اجرای پروژه را نمایش می دهد:
بازی TicTacToe با CPP
برای دانلود پروژه بازی دوز (بازی TicTacToe) به زبان C++ بر روی لینک زیر کلیک کنید:
جستجوی عمق اول (Depth-first Search یا به اختصار DFS) یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار میرود. الگوریتم از ریشه شروع میکند (در گرافها و یا درختهای بدون ریشه راس دلخواهی به عنوان ریشه انتخاب میشود) و در هر مرحله همسایههای رأس جاری را از طریق یالهای خروجی رأس جاری به ترتیب بررسی کرده و به محض روبهرو شدن با همسایهای که قبلاً دیده نشده باشد، به صورت بازگشتی برای آن رأس به عنوان رأس جاری اجرا میشود. در صورتی که همه همسایهها قبلاً دیده شده باشند، الگوریتم عقبگرد میکند و اجرای الگوریتم برای رأسی که از آن به رأس جاری رسیدهایم، ادامه مییابد. به عبارتی الگوریتم تا آنجا که ممکن است، به عمق بیشتر و بیشتر میرود و در مواجهه با بن بست، عقبگرد میکند. این فرایند تا زمانی که همه ی رأسهای قابل دستیابی از ریشه دیده شوند ادامه مییابد. از نقطه نظر عملی، برای اجرای الگوریتم، از یک پشته استفاده میشود. بدین ترتیب که هر بار با ورود به یک رأس دیده نشده، آن رأس را در پشته قرار میدهیم و هنگام عقبگرد رأس را از پشته حذف میکنیم. بنابراین در تمام طول الگوریتم اولین عنصر پشته رأس در حال بررسی است. جزئیات پیادهسازی در ادامه خواهد آمد.
در ادامه قصد داریم برنامهای بنویسیم که گراف زیر را به روش DFS پیمایش کند و ترتیب رؤیت گره ها را در خروجی چاپ نماید (فرزندان یک گره به ترتیب حروف الفبا رؤیت شوند). فرض میکنیم که جستجو از گره C که ما شماره آنرا ۲ در نظر گرفتهایم شروع شده است ولی برنامه این قابلیت را دارد که با تغییر این عدد، بتوانیم از هر گره دلخواه دیگری نیز شروع کنیم.
گراف نمونه برای پیمایش
برای دانلود فایل برنامه مربوط به حل این مسئله با استفاده از الگوریتم جستجوی اول عمق (DFS) به زبان ++C همراه با فایل معرفی کامل روش DFS و توضیحات خط به خط کد برنامه بر روی لینک زیر کلیک نمایید:
الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار میکند:
۱- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.
۲- گره جاری را پردازش کن.
۳- گرههای مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.
در ادامه قصد داریم برنامهای بنویسیم که گراف زیر را به روش BFS پیمایش کند و ترتیب رؤیت گرهها را در خروجی چاپ نماید (فرزندان یک گره به ترتیب حروف الفبا رؤیت شوند). فرض میکنیم که جستجو از گره C که ما شماره آنرا ۲ در نظر گرفتهایم شروع شده است ولی برنامه این قابلیت را دارد که با تغییر این عدد، بتوانیم از هر گره دلخواه دیگری نیز شروع کنیم.
گراف نمونه برای پیمایش
برای دانلود فایل برنامه مربوط به حل این مسئله با استفاده از الگوریتم جستجوی اول سطح (BFS) به زبان ++C همراه با فایل معرفی کامل روش BFS و توضیحات خط به خط کد برنامه بر روی لینک زیر کلیک نمایید:
الگوریتم جستجوی دودویی (Binary Search) تکنیکی است برای یافتن یک مقدار عددی از میان مجموعهای از اعداد مرتب. این متد محدوده جستجو را در هر مرحله به نصف کاهش میدهد، بنابراین هدف مورد نظر یا به زودی پیدا میشود و یا مشخص میشود که مقدار مورد جستجو در فهرست وجود ندارد. جستجوی دودویی فقط در آرایه های مرتب استفاده می شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود، اگر با این خانه برابر بود جستجو تمام می شود. اگر عنصر مورد جستجو از خانه وسط بزرگتر بود، جستجو در بخش بالایی آرایه و در غیر این صورت، جستجو در بخش پایینی آرایه انجام می شود (فرض کرده ایم آرایه به صورت صعودی مرتب شده است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه مییابد. جستجوی دودویی نمونهای از الگوریتمهای تقسیم و غلبه (Divide and conquer) میباشد.
یک الگوریتم جستجو به طور کلی الگوریتمی است که درون یک مجموعه از دادهها که توسط یک نوع ساختمان داده ذخیره شدهاند، مکان یک مقدار داده شده به عنوان آرگومان جستجو را درون ساختمان داده مشخص میکند، یا تعیین میکند در مجموعه وجود دارد یا خیر.
یکی از الگوریتم هایی که برای جستجوی یک سری داده وجود دارد، جستجوی ترتیبی (sequential search) یا جستجوی خطی (linear search) است. این الگوریتم که جزو ساده ترین الگوریتمهای جستجو میباشد کلیه عناصر درون یک لیست را یکی یکی بررسی میکند تا آرگومان جستجو پیدا شود.
مرتبسازی انتخابی یکی از انواع الگوریتم مرتب سازی میباشد که جزو دسته الگوریتمهای مرتبسازی مبتنی بر مقایسهاست. اعمال این الگوریتم روی مجموعه بزرگی از اعداد کارا به نظرنمی رسد و به طور عمومی ضعیفتر از نوع مشابهش که مرتبسازی درجی است عمل میکند. این مرتبسازی به دلیل سادگی اش قابل توجهاست. این الگوریتم اینگونه عمل میکند:
ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا میکنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا میکنیم و این روند را برای n-1 عدد اول تکرار میکنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم میکنیم. زیرلیست اول که قبلاً مرتب کردهایم و سایر اعضای لیست که هنوز مرتب نشدهاست.
شکل زیر نمونه ای از اجرای مرتب سازی انتخابی به صورت مرحله به مرحله روی یک آرایه ۶ مقداری را نمایش می دهد (توضیحات بیشتر در مورد این مثال نیز در فایل توضیحات آورده شده است):
نمونه مراحل اجرای مرتب سازی انتخابی (Selection Sort)
دو شکل زیر هم نمونه ای از کار مرتب سازی انتخابی بصورت انیمیشن می باشند که یکی ارقام ۰ تا ۹ و دیگری فهرستی از اعداد تصادفی را مرتب می کند:
نمونه اجرای مرتب سازی انتخابی روی فهرستی از اعداد تصادفی
نمونه اجرای مرتب سازی انتخابی برای ارقام ۰ تا ۹
برای دانلود پروژه کامل پیاده سازی مرتب سازی انتخابی (Selection Sort) به زبان ++C همراه با فایل توضیحات کامل و تصویری بر روی لینک زیر کلیک نمایید:
مرتب سازی حبابی یک الگوریتم مرتبسازی ساده است که فهرست را پشت سرهم پیمایش میکند تا هر بار عناصر کنار هم را با هم سنجیده و اگر در جای نادرست بودند جابهجایشان کند. دراین الگوریتم این کار باید تا زمانی که هیچ جابهجایی در فهرست رخ ندهد، ادامه یابد و در آن زمان فهرست مرتب شده است. این مرتبسازی از آن رو حبابی نامیده میشود که هر عنصر با عنصر کناری خود سنجیده شده و درصورتی که از آن کوچکتر باشد جای خود را به آن میدهد و این کار همچنان پیش میرود تا کوچکترین عنصر به پایین فهرست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند (یا به رتبهای بالاتر روند یا به پایینتر فهرست رانده شوند).
شکل زیر نمونه ای از اجرای مرتب سازی حبابی به صورت مرحله به مرحله روی یک آرایه ۵ مقداری را نمایش می دهد (توضیحات بیشتر در مورد این مثال نیز در فایل توضیحات آورده شده است):
نمونه مراحل اجرای مرتب سازی حبابی (Bubble Sort)
شکل زیر نمونه ای از کار مرتب سازی حبابی بصورت انیمیشن می باشد که فهرستی از اعداد تصادفی را مرتب می کند:
نمونه اجرای مرتب سازی حبابی روی فهرستی از اعداد تصادفی