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

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

====== نظریه اعداد ======
این مباحث اولیه برای حل مسایل ضروری هستند اما کافی نیستند.
===== اعداد اول =====
هدف پیدا کردن اعداد اول در یک بازه مشخص است.
==== غربال اراتستن ====
یک آرایه ۰ و ۱ به اندازه بزرگترین عددی که می‌خواهیم اول بودن آن را بررسی کنیم می‌سازیم. ابتدا علامت خانه متناظر ۲ را ۱ (به معنی اول) قرار می‌دهیم. سپس یک حلقه تکرار از ۳ تا $n$ (بزرگترین عدد مورد نظر) ایجاد می‌کنیم و درون آن بخش‌پذیری آن را بر اعداد کمتر یا مساوی از $\sqrt n$ بررسی می‌کنیم.

زمان این الگوریتم $O(n\sqrt n)$ است و حافظه $O(n)$ می‌برد.
===== ب.م.م و ک.م.م =====
دو روش برای پیدا کردن بزرگترین مقسوم علیه مشترک و کوچکترین مضرب مشترک دو عدد را در ادامه خواهید دید.
==== تجزیه اعداد ====
روش اول تجزیه کردن اعداد به عوامل اول آنها و به دست آوردن اشتراک بین این عوامل اول است. حاصل ضرب عوامل اول مشترک ب.م.م دو عدد را می‌دهد. برای تجزیه یک عدد، از یک حلقه تکرار استفاده می‌کنیم که در آن ابتدا عدد داده شده را تا زمانی که بخشپذیر است به ۲ تقسیم می‌کنیم و تعداد این عوامل ۲ را هم نگه می‌داریم. سپس این کار را برای عدد بعدی (۳) انجام می‌دهیم تا زمانی که عدد اولیه به ۱ برسد.
==== بازگشتی ====
روش دیگری با استفاده از همنهشتی برای پیدا کردن ب.م.م وجود دارد. فرض کنید می‌خواهیم ب.م.م دو عدد $a$ و $b$ را به دست بیاوریم. می‌دانیم:
\[
GCD(a,b) = GCD(a,b-a) = GCD(a-b,a)
\]
این تساوی هنگامی برقرار است که اعداد مثبت بمانند، پس هر بار عدد کوچکتر را از عدد بزرگتر کم می‌کنیم تا به جایی برسیم که دو عدد مساوی شوند که همان ب.م.م است.

زمان این کار خیلی زیاد است، پس برای حل این مشکل بهبودهایی روی این روش انجام می‌دهیم. می‌دانیم تا زمانی که به باقیمانده تقسیم $a$ بر $b$ نرسیده‌ایم، می‌توانیم عمل تفاضل را انجام دهیم. اگر باقیمانده‌گیری را با عملگر ٪ نشان دهیم، داریم:
\[
GCD(a,b) = GCD(a\%b,b)
\]
برای ک.م.م می‌دانیم:
\[
LCM(a,b) = \frac{a\times b}{GCD(a,b)} = a\times \frac{b}{GCD(a,b)}
\]
مزیت این کار کوچک کردن اعداد است که به ازای اعداد بزرگ سرریز نکنند.
===== فاکتوریل =====
چون رشد این تابع زیاد است پیشنهاد می‌شود از کتابخانه اعداد بزرگ جاوا استفاده کنید.
===== دنباله فیبوناچی =====
دنباله فیبوناچی یک دنباله بازگشتی پرکاربرد است. می‌توان آن را با استفاده از [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] با استفاده از رابطه بازگشتی آن محاسبه کرد:
\[
Fib(n) = Fib(n-1)+Fib(n-2),\quad Fib(0)=Fib(1) = 1
\]
از ویژگی‌های این اعداد این است که هر عدد را می‌توان در مبنای فیبوناچی نوشت، یعنی به صورت مجموع اعداد فیبوناچی غیرتکراری که هیچ دو عدد فیبوناچی متوالی در آنها نباشد.

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

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

ابزار کاربر

ابزار سایت

ابزار صفحه