الگوریتم برنامه‌نویسی پویا

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

مسئله انتخابات

آمادگی مسابقه برنامه‌نویسی مسئله الگوریتمی ریاضیات

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

مسئله اعداد اردوش

آمادگی مسابقه برنامه‌نویسی مسئله الگوریتمی الگوریتم برنامه‌نویسی پویا

پل اردوش ( اردیش - Paul Erdős ) ریاضیدان مشهور و برجسته قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد ...

دنباله اعداد فیبوناچی

سی‌پلاس‌پلاس ریاضیات الگوریتم تقسیم و غلبه

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

الگوریتم فلوید-وارشال

سی‌پلاس‌پلاس پایتون الگوریتم برنامه‌نویسی پویا

الگوریتم فلوید-وارشال (Floyd-Warshall) یک الگوریتم مبتنی بر روش برنامه‌نویسی پویا برای محاسبه کوتاهترین مسیر بین هر دو جفت گره گراف‌های وزن‌دار است. دو الگوریتم رایج دایکسترا و بلمن-فورد روش‌های محاسبه کوتاهترین مسیر از مبدأ ثابت هستند که در صورت تکرار آنها به ازای هر گره عملکردی همانند الگوریتم فلوید-وارشال دارند ...

مسئله آسانسورها

آمادگی مسابقه برنامه‌نویسی مسئله الگوریتمی الگوریتم برنامه‌نویسی پویا

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

مسئله حداکثر مجموع

آمادگی مسابقه برنامه‌نویسی مسئله الگوریتمی ریاضیات

ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است ...

دنباله اعداد کاتالان و محاسبه آن

سی‌پلاس‌پلاس ریاضیات الگوریتم تقسیم و غلبه

دنباله اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود. $C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$ این دنباله کاربردهای بسیاری در مسائل شمارشی دارد ...

ضرب زنجیره‌ای ماتریس‌ها

سی‌پلاس‌پلاس ریاضیات الگوریتم تقسیم و غلبه

مسئله ضرب زنجیره‌ای ماتریس‌ها و پرانتزبندی بهینه آن یکی از مثال‌های مشهور کاربرد برنامه‌نویسی پویا در حل مسائل بهینه‌سازی است. فرض کنید قصد داریم حاصلضرب عبارت ماتریسی $ A_{3 \times 7} \times B_{7 \times 8 } \times C_{8 \times 4} $ را محاسبه کنیم ...

الگوریتم‌های برنامه‌نویسی پویا

سی‌پلاس‌پلاس الگوریتم برنامه‌نویسی پویا الگوریتم

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

محاسبه ضرایب دوجمله‌ای

سی‌پلاس‌پلاس ریاضیات الگوریتم تقسیم و غلبه

ترکیب (Combination) به انتخاب تعدادی عنصر از یک مجموعه بزرگ‌تر بدون در نظر گرفتن ترتیب آن‌ها اشاره دارد. در ترکیب، برخلاف جایگشت (Permutation)، ترتیب انتخاب عناصر مهم نیست. این مفهوم در ریاضیات کاربرد گسترده‌ای دارد و یکی از موارد اصلی استفاده از آن در محاسبه‌ی ضرایب بسط دوجمله‌ای است ...