مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

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

====== ترکیبیات ======
در این قسمت به الگوریتم‌های مورد نیاز در حل مسایل ترکیبیات می‌پردازیم.
===== محاسبه ترکیب‌ها =====
انتخاب $r$ شئ از $n$ شئ پایه‌ی حل بسیاری از مسایل شمارشی است. برای آن رابطه‌ی بازگشتی زیر را داریم:
\[
\binom{n}{r} = \binom{n-1}{r}+\binom{n-1}{r-1} ,\quad \binom{n}{0} = 1
\]
با استفاده از این رابطه و [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] می‌توانیم مقادیر آن را محاسبه کنیم. دلیل این کار این است که رابطه فاکتوریلی آن اعداد بزرگی می‌دهد که می‌توانند باعث سرریز شوند:
\[
\binom{n}{r} = \frac{n!}{r!(n-r)!}
\]
===== پیدا کردن دور =====
دنباله‌ای داریم که اعداد آن به صورت منظم تکرار می‌شوند و $n$-امین جمله‌ی آن خواسته شده است که $n$ عدد بزرگی است و قطعاً نمی‌توانیم آن را به دست بیاوریم. اگر مقادیر بعد از یک عدد تکرار شوند، می‌توانیم با به دست آوردن دوره گردش آن، مقدار مورد نظر خودمان را به دست بیاوریم. (از $n$ تعداد اعداد ابتدای دنباله که جزو دوره گردش نیستند را کم می‌کنیم و باقیمانده‌ی آن را به دوره گردش محاسبه می‌کنیم.)

الگوریتم‌های دیگری برای حل این مسأله وجود دارند.

[[http://en.wikipedia.org/wiki/Cycle_detection|مطالب بیشتر در مورد پیدا کردن دور]]

===== احتمال =====
در این مسایل حالت‌های مختلفی از پیشامدها وجود دارد و باید احتمال پیشامد خاصی را به دست بیاورید. این کار معمولاً با کمک احتمال پیشامدهای مستقل به دست می‌آید: اگر رخ دادن یک پیشامد به معنی رخ دادن پیشامدهای دیگری باشد که از هم مستقل هستند، احتمال آن برابر حاصل ضرب این احتمالها خواهد بود.
\[
p = \prod_{i=1}^{n} p_i
\]
این مشابه اصل ضرب در ترکیبیات است. مشابه اصل جمع در ترکیبیات هم اصلی در احتمال هست که حالت‌های مختلف رسیدن به پیشامد مورد نظر، احتمالهایشان جمع می‌شود.

با کمک این دو اصل و [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] می‌توان مسایل این مبحث را حل کرد.

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه