صفحه اصلی

صفحه شخصی مسعود اقدسی‌فام
الگوریتمستان - برنامه‌نویسی و طراحی الگوریتم
● وب‌سایت آرشیو سوالات منطقه‌ای و جهانی مسابقات برنامه‌نویسی ACM-ICPC، با امکان ارسال پاسخ و بررسی جواب.
● علاقمندان به شرکت در مسابقات برنامه‌نویسی و حل سوالات الگوریتمی می‌توانند از این وب‌سایت معتبر به همراه کتاب معرفی شده جهت تمرین و آمادگی بیشتر استفاده کنند.
امروز: یکشنبه، 2 آذر ماه 1393 ، تعداد افراد آنلاین: 2 نفر
جستجو در مطالب وب‌سایت:   
برنامه‌نویسی ++C
برنامه‌نویسی ++C

آموزش زبان برنامه‌نویسی ++C
طراحی الگوریتم‌ها
طراحی الگوریتم‌ها

بحث‌هایی از طراحی الگوریتم
ساختمان داده‌ها
ساختمان داده‌ها

آموزش مباحث ساختمان داده‌ها
مسابقات برنامه‌نویسی
مسابقات برنامه‌نویسی

راهنما و نمونه سوالات مسابقات
محاسبات ریاضی
محاسبات ریاضی

الگوریتم‌های محاسبات ریاضی
مرتب‌سازی
مرتب‌سازی

روش‌های مرتب‌سازی داده‌ها


الگوریتمستان
معرفی متغیرهای مرجع در زبان برنامه‌نویسی ++C و آشنایی با مهمترین کاربردهای آنها
الگوریتمستان
بررسی مساله Simple Addition، از سوالات آمادگی مسابقات برنامه‌نویسی
الگوریتمستان
آشنایی با روش حریصانه و کاربردهای آن مانند مساله خرد کردن پول
الگوریتمستان
آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
الگوریتمستان
بررسی مساله دوست خوب، از سوالات مسابقات برنامه‌نویسی ACM
الگوریتمستان
بررسی روش‌های مختلف محاسبه ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
الگوریتمستان
بررسی مساله مربی ناامید، از سوالات مسابقات برنامه‌نویسی ACM
الگوریتمستان
بحث در مورد مساله کاشی‌کاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل
الگوریتمستان
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی، با قابلیت دانلود
الگوریتمستان
آشنایی با درخت Heap (هیپ، هرم یا کپه) به عنوان یکی از ساختمان های داده پرکاربرد و بررسی روش ساخت، درج گره و حذف گره و ارائه کد نمونه به زبان برنامه‌نویسی ++C
الگوریتمستان
آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
الگوریتمستان
بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه دترمینان ماتریس مربعی، و پیچیدگی زمانی آنها
الگوریتمستان
آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
الگوریتمستان
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه آن با روش تقسیم و حل و روش برنامه‌نویسی پویا

یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی معتبر همچون ACM، این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟

کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات، که برای هر علاقمند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.

ادامه مطلب ...

معمای هشت وزیر از جمله مسائل کلاسیک مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود.

 

برای افرادی که با بازی شطرنج آشنایی ندارند

وزیر مهره‌ای از مهره‌های بازی شطرنج است که می‌تواند در تمامی هشت جهت به هر تعداد خانه - تا زمانی که مهره‌ای مانع نباشد - حرکت کند. اگر در این مسیرها مهره‌ای از حریف قرار گرفته باشد، آن مهره در معرض خطر حمله توسط وزیر قرار دارد؛ یا به اصطلاح وزیر آن مهره را تهدید می‌کند.

 

معمای هشت وزیر

ادامه مطلب ...

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

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

 

حلقه تکرار while

این نوع حلقه، ساده‌ترین نوع حلقه تکرار در این زبان برنامه‌نویسی است. فرم کلی حلقه while به این صورت است:

 

ادامه مطلب ...

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

3- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.

 

ادامه مطلب ...

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مساله بر زیرمساله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

زمانی که یک مساله به دو یا چند زیرمساله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

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

ادامه مطلب ...

یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش Divide and Conquer است که در زبان فارسی به صورت تقسیم و حل یا تقسیم و غلبه ترجمه شده است.

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

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

 

1. مرتب‌سازی سریع (Quick Sort)

ادامه مطلب ...

دترمینان ماتریس مربعی - که به صورت | A | یا ( det( A نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه سریع دترمینان یک ماتریس با ابعاد بزرگ، بحث مهمی است، که در ادامه سه روش محاسباتی رایج و پیچیدگی زمانی آنها مرور خواهند شد.

طبق تعریف دترمینان، اگر اندازه ابعاد ماتریس مربعی یک باشد (n = 1)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

 

محاسبه دترمینان ماتریس

 

ادامه مطلب ...