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

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

الگوریتم‌های مرتب‌سازی سریع، مرتب‌سازی ادغامی و جستجوی دودویی از الگوریتم‌های معروف تقسیم و حل هستند.
====== مرتب سازی ======
**تعریف مسأله**: آرایه داده شده را به صورت صعودی یا نزولی مرتب کنید.

**مرتب‌سازی سریع**:
در این الگوریتم یک عنصر به عنوان محور انتخاب می‌شود و بر اساس آن آرایه را به دو قسمت عناصر کوچکتر و بزرگتر تقسیم می‌کنیم. هر کدام از این قسمت‌ها به صورت بازگشتی مرتب می‌شوند. اگر عنصر میانه به عنوان محور انتخاب شود، زمان الگوریتم $O(n\log n)$ خواهد شد.

**مرتب‌سازی ادغامی**:
در ابتدای کار آرایه را به طور دلخواه به دو قسمت مساوی تقسیم می‌کنیم و هر قسمت را مرتب می‌کنیم. سپس بزرگترین عنصر هر قسمت را در آرایه‌ی جواب کپی می‌کنیم و این کار را ادامه می‌دهیم تا عناصر هر دو آرایه تمام شوند. این کار به صورت بازگشتی آرایه را مرتب می‌کند و زمان آن $O(n\log n)$ است.

**تحلیل**: بهترین زمان الگوریتم‌های مرتب‌سازی مقایسه‌ای $O(n\log n)$ است.

**پیاده‌سازی**:

پیاده‌سازی الگوریتم مرتب سازی در زبان $C++$، به صورت آماده در کتابخانه استاندارد $algorithm.h$ با نام $sort(begin,end)$ وجود دارد که $begin$ شروع و $end$ پایان آرایه را نشان می‌دهد. برای استفاده از این تابع برای مرتب‌سازی دلخواه خودتان، می‌توانید تابع مقایسه دو عنصر را بنویسید و به عنوان ورودی به آن بدهید. مثالی از پیاده‌سازی این الگوریتم برای نوع داده‌ای $vector$ که یک آرایه پویا است در [[http://www.cplusplus.com/reference/algorithm/sort/|اینجا]] آمده است.

====== جستجوی دودویی ======
**تعریف مسأله**: به ازای مقدار داده شده (کلید جستجو)، عنصر برابر با آن را در آرایه‌ی مرتب‌شده‌ی داده شده پیدا کنید.

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

**تحلیل**: این الگوریتم زمان $O(\log n)$ دارد. فرض کنید زمان این الگوریتم را با $T(n)$ نشان دهیم که در آن $n$ تعداد عناصر آرایه است.

\[
T(n) \leq T(n/2)+O(1)
\]
طبق قضیه اصلی تحلیل الگوریتم‌ها، زمان این الگوریتم $O(n^{\log_2^1}\log n)=O(\log n)$ است.

**پیاده‌سازی**:

این الگوریتم در زبان ++C در کتابخانه استاندارد ''algorithm.h'' پیاده سازی شده است و با نام ''lower_bound(begin,end, key)'' وجود دارد که در آن ''begin'' شروع آرایه، ''end'' پایان آرایه و ''key'' کلید آرایه است. اشکال پیشرفته‌تری از این تابع هم پیاده‌سازی شده‌اند ([[http://www.cplusplus.com/reference/algorithm/|قسمت جستجوی دودویی]] را ببینید).

این الگوریتم در زبان Java در ''Collections.binarySearch'' تعریف شده است.

**جستجوی دودویی روی بازه مقادیر**:

جستجوی دودویی را می‌توان برای به دست آوردن جواب یک مسأله که بازه مقادیر مجاز جواب آن را می‌دانیم (مثلاً بازه‌ی اعداد صحیح ۱ تا ۱۰۰) به کار برد، به شرطی که هر بار بتوانیم نیمی از بازه‌ی مقادیر را حذف کنیم. این اتفاق زمانی می‌افتد که مقادیر ورودی بر حسب مقادیر خروجی یکنوا باشند.
====== توان رسانی ======
فرض کنید می‌خواهیم یک ماتریس $A_{m\times m}$ را به توان $n$ برسانیم. برای این کار از رابطه‌ی بازگشتی زیر می‌توانیم کمک بگیریم:
\[
A^n = \left\{
\begin{array}{l l}
\left( A ^{\lfloor n/2\rfloor} \right)^2\quad &\text{if n mod 2 = 0}\\
\left( A ^{\lfloor n/2\rfloor} \right)^2\times A \quad &\text{if n mod 2 = 1}
\end{array}\right.
\]
رابطه‌ی بازگشتی قبل را می‌توان با نگه داشتن جواب هر مرحله در زمان $O(m^2\log n)$ به دست آورد. از این روش برای به توان رساندن اعداد در زمان $O(\log n)$ هم می‌توان استفاده کرد (اگر نخواهیم از تابع $pow$ استفاده کنیم. همچنین راه حل سریعتر برای ضریب ماتریس‌ها هم وجود دارد.

[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%A7%D8%B3%D8%AA%D8%B1%D8%A7%D8%B3%D9%86|الگوریتم ضرب ماتریس استراسن]]
===== مرتب‌سازی‌های خطی =====
الگوریتم‌های مرتب‌سازی برای حالت‌های خاص وجود دارند که در زمان خطی نسبت به تعداد عناصر کار می‌کنند. مرتب‌سازی مبنا و مرتب‌سازی سطلی از مثال‌های معروف این مرتب‌سازی‌ها هستند.

[[http://en.wikipedia.org/wiki/Sorting_algorithm#Distribution_sort|مرتب‌سازی‌های غیرمقایسه‌ای]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
