الگوریتمستان
کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) کتابچه‌ای است که در آن عموم مباحث مورد نیاز جهت شرکت در رقابت‌های برنامه‌نویسی همچون المپیاد کامپیوتر دانش‌آموزی یا مسابقات برنامه‌نویسی دانشجویی به صورت مختصر و مفید یک جا جمع شده است.
دکتر Antti Laaksonen از مربیان تیم‌های المپیاد کامپیوتر کشور فنلاند این کتاب را به صورت رایگان جهت استفاده عموم در سه بخش و سی فصل با عناوین زیر منتشر کرده است.
دنباله‌ای از $n$ عدد صحیح را Jolly Jumper گویند هر گاه قدر مطلق اختلاف عناصر متوالی آن، همه اعداد 1 تا $n-1$ را تولید کند. برای مثال دنباله
1 4 2 3
Jolly Jumper است. چرا که قدرمطلق اختلاف عناصر متوالی آن 3، 2 و 1 است. همچنین هر دنباله با تنها یک جمله، Jolly Jumper محسوب می‌شود. شما باید برنامه‌ای بنویسید که مشخص کند آیا یک دنباله Jolly Jumper است یا نه؟
مستندات دوره «Introduction to Programming Contests» دانشگاه استنفورد با تدریس Jaehyun Park (مربی تیم‌های ACM-ICPC این دانشگاه) شامل اسلایدها، سوالات برگزیده برای تمرین در موضوعات مختلف ریاضیات، ساختمان داده‌ها و الگوریتم‌ها به همراه نکات برنامه‌نویسی از پیوند زیر قابل مشاهده و دریافت هستند:
گروهی از دانشجویان عضو کلوپی هستند که هر سال سفر به یک منطقه را در برنامه‌های خود دارد. ایندیاناپلیس، فینیکس، نَشویل، فیلادلفیا، سن خوزه و آتلانتا از جمله مناطقی هستند که در گذشته سفر انجام شده و این بهار نیز نوبت سفر به آیندهوون است.
این گروه دانشجویی توافق کرده‌اند که سهم هر کدام از نفرات در مخارج سفر با دیگر اعضا یکی باشد. برای رسیدن به این هدف، عملا امکان تقسیم خرج بین نفرات در هر هزینه وجود ندارد. به همین دلیل هر کدام از نفرات هزینه‌های مختلف از قبیل وعده‌های غذایی، اقامت و ایاب و ذهاب را پرداخت می‌کنند و پس از اتمام سفر، مجموع کل هزینه‌ها محاسبه شده و پول بین نفرات به قسمی رد و بدل می‌شود که همه به یک میزان در خرج مشارکت داشته باشند یا حداکثر یک سنت اختلاف وجود داشته باشد.
الگوریتمی را در نظر بگیرید که با دریافت یک عدد $n$، دنباله‌ای از اعداد را تولید می‌کند. به این ترتیب که اگر $n$ زوج بود، تقسیم آن بر عدد 2 و اگر فرد بود، $ 3n + 1 $ را به عنوان جمله بعدی دنباله و مقدار جدید برای $n$ تولید کرده و عملیات را تا زمانی که مقدار $n$ برابر 1 شود، ادامه دهد. برای مثال، دنباله زیر با شروع از $ n = 22 $ تولید می‌شود:
اعضای کمیته علمی ACM امسال از ایمیل برای بحث در مورد سوالات استفاده می‌کنند. آنها می‌دانند که ایمیل ابزار امنی برای ارتباط در مورد چنین موضوعات حساسی نیست. بنابراین فایل‌های فشرده رمزگذاری شده را تبادل می‌کنند. برای تبادل کلمه عبور فایل نیز از SMS رمز شده با ساختار تایپ multi-tap استفاده می‌کنند.
کف اتاق خواب غلام با کاشی‌های سفید و زرد پوشیده شده است. گاهی که حوصله ندارد، روی یکی از کاشی‌ها می‌ایستد و در آن ردیف از کاشی‌ها قدم می‌زند. او ابتدا عدد $n$ را انتخاب می‌کند و تنها $n$ قدم حرکت می‌کند. اگر در حین حرکت به دیوار برسد، چرخیده و در جهت خلاف به حرکت خود ادامه می‌دهد. توجه داشته باشید که خود عمل چرخش گام حساب نمی‌شود. در حین قدم زدن (یک کاشی در هر قدم) او تعداد دفعاتی که پا روی کاشی زرد گذاشته را می‌شمارد.
ویدئوهای راه حل سوالات مسابقه جهانی ACM-ICPC 2016 را در کانال آپارات الگوریتمستان مشاهده کنید:
aparat.com/algorithmha
می‌دانیم که جایگاه رقم در یک عدد، وزن آن را در مقدار عدد مشخص می‌کند. برای مثال، عدد 362 در مبنای 10 از رقم 2 با وزن $10^0$، رقم 6 با وزن $10^1$ و رقم 3 با وزن $10^2$ به صورت $ 3 \times 10 ^ 2 + 6 \times 10 ^ 1 + 2 \times 10 ^ 0 $ یا $ 300 + 60 + 2 $ تشکیل شده است. چنین ساختاری برای نمایش اعداد در سایر مبناها نیز وجود دارد.
کتاب Programming Challenges: The Programming Contest Training Manual اثر Steven Skiena و Miguel Revilla یکی از کتاب‌های مناسب تمرین گام به گام برای شرکت در مسابقات برنامه‌نویسی‌ای همچون المپیاد کامپیوتر و ACM-ICPC است. این کتاب مورد تایید UVa Online Judge بوده و تمام سوالات تمرینی کتاب نیز از این مخزن است.
جناب خان که با کسب و کار لبوی خود میلیاردر شده است، می‌خواهد رئیس جمهور شود! در کشور او که از چندین ایالت تشکیل شده است، از روشی با عنوان هیئت انتخاب (یا هیئت الکترال) برای انتخاب رئیس جمهور استفاده می‌شود. در چنین ساختاری شمارش رأی در هر ایالت به صورت مستقل انجام می‌شود و هر ایالت متناسب با جمعیت خود تعدادی نماینده در هیئت انتخاب کنندگان رئیس جمهور دارد. تمام نمایندگان یک ایالت در نهایت به نامزدی رأی می‌دهند که در آن ایالت اکثریت آرا را کسب کرده باشد. اگر نامزدها رأی برابر داشته باشند، هر ایالت قوانین خاص خود برای انتخاب نهایی را دارد. در نهایت رئیس جمهور کسی است که بیش از نصف مجموع رأی‌های هیئت انتخاب را از آن خود کند.
پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.
منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.
در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه بیشتر» بخوانید.
بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله اعدادی تبعیت می‌کنند که امروزه با نام دنباله اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته می‌شود. مشهورترین خاصیت این اعداد نسبت دو جمله متوالی آنها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.
فایل سرآیند (هدر فایل) algorithm از جمله فایل‌های سرآیند تعاریف کتابخانه قالب استاندارد (STL) زبان برنامه‌نویسی ++C است که به طور عمده شامل توابعی برای کار با مجموعه‌ای از داده‌ها (آرایه‌ها و لیست‌ها) است. با استفاده از این توابع به راحتی می‌توان با تنها یک خط کد عملیات جستجو، مرتب‌سازی، شمارش و بررسی یک خاصیت در تمامی داده‌های یک بازه مشخص را انجام داد.
$n$ بشکه آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه شماره یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.
کتاب Introduction to Algorithms: A Creative Approach را می‌توان مکملی بر استفاده از کتاب Introduction to Algorithms (مشهور به کتاب CLRS) دانست. در این کتاب علاوه بر معرفی تکنیک‌های مختلف طراحی الگوریتم‌ها و روش‌های حل برخی مسائل الگوریتمی، روش‌های تحلیل و حل آنها با جزئیات بیشتر و به صورت گام به گام بررسی شده است. به همین دلیل نیز از جمله منابع اصلی پیشنهادی به متقاضیان شرکت در المپیادهای کامپیوتر و مسابقات برنامه‌نویسی برای یادگیری طراحی و تحلیل الگوریتم‌ها است.
جدولی با n سطر و m ستون در نظر بگیرید. در تمام خانه‌های این جدول عدد 0 نوشته شده است. در ابتدای کار حامد در خانه‌ای از جدول ایستاده است. او عدد این خانه را پاک می‌کند و عدد 1 را به جای آن می‌نویسد. حامد شروع به حرکت می‌کند و در هر ثانیه یک خانه به بالا، راست، پایین یا چپ می‌رود. او با وارد شدن به هر خانه، عدد نوشته شده در خانه را پاک می‌کند و عددی یک واحد بزرگتر از آخرین عددی که نوشته است را می‌نویسد و بعد از مدتی متوقف می‌شود. می‌دانیم حامد در انتهای حرکت خود تمام خانه‌های جدول را دیده است.
کتاب Introduction to Algorithms (مشهور به کتاب CLRS) از انتشارات MIT اثر Thomas H. Cormen، Charles E. Leiserson، Ronald L. Rivest و Clifford Stein کتاب جامع مباحث الگوریتم‌ها و ساختمان داده‌ها است که منبع درسی بسیاری از دانشگاه‌های معتبر بوده و تا کنون بیش از سی هزار مقاله و کتاب با ارجاع به آن نگارش یافته است. مطالب این کتاب از مباحث اولیه مانند مفهوم تحلیل و طراحی الگوریتم آغاز شده و مباحث پیشرفته طراحی الگوریتم‌ها و ساختمان داده‌ها را نیز پوشش می‌دهد. به همین دلیل مطالعه و استفاده از آن به عنوان مرجع برای کلیه علاقمندان مباحث طراحی الگوریتم‌ها، ساختمان داده‌ها و همینطور شرکت‌کنندگان المپیادهای کامپیوتری و مسابقات برنامه‌نویسی توصیه می‌شود.
ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند.
کتاب Concrete Mathematics: A Foundation for Computer Science نوشته‌ای با موضوع مفاهیم اولیه ریاضیات پیوسته (CONtinuous mathematics) و ریاضیات گسسته (disCRETE mathematics) به قلم رونالد گراهام، دونالد کنوت و اُرِن پاتاشنیک - از دانشمندان بزرگ علوم ریاضیات و کامپیوتر - است . در این کتاب از بیان متفاوتی نسبت به نوشتار عموم کتاب‌های آموزش ریاضی استفاده شده و مفاهیم پایه‌ای محاسباتی علم کامپیوتر به زبان ساده و گیرا توضیح داده شده است. این مفاهیم پیش‌نیاز حل بسیاری از مسائل کامپیوتری، ریاضی و محاسبات علمی هستند. به همین دلیل، مطالعه آن به علاقه‌مندان برنامه‌نویسی، بویژه شرکت‌کنندگان المپیادهای کامپیوتری و مسابقات برنامه‌نویسی توصیه می‌شود.
کتاب Programming Challenges: The Programming Contest Training Manual از انتشارات معتبر Springer کتاب مفیدی برای آمادگی شرکت در مسابقات برنامه‌نویسی است که نویسندگان آن به صورت گام به گام، خلاصه و مفید، به مفاهیم و نکات مهم برنامه‌نویسی، ساختمان داده‌ها، محاسبات ریاضی و طراحی الگوریتم‌ها اشاره داشته و با طرح مسائل متفاوت از هر موضوع، خواننده را به چالش حل مسئله کشیده‌اند.
یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی معتبر همچون ACM این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟
کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات که برای هر علاقه‌مند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.
دو دوست در زمین نامحدودی متشکل از حصارهای دایره‌ای شکل هم‌اندازه با ساختار زیر قرار دارند. یکی از دوستان قصد دارد با حرکت در این ساختار نزد دوست دیگر خود برود. حرکت در این ساختار در هر گام شامل جابجایی به یکی از دایره‌های مجاور است. دو دایره مجاور هستند اگر در یک نقطه مشترک باشند.
ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.
به عنوان مثال، برای ماتریس زیر:
یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونه‌ای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه می‌کنند که باعث بالا رفتن حجم ترافیک می‌شود. مدیران مرکز سفارش نصب دوربین ویژه‌ای در نزدیکی آن محل را داده‌اند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد.
دنباله اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود.
$C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$
تابع بازگشتی (F(n با تعریف زیر مفروض است:
\[ F(n)= \left\{\begin{matrix} n \% 10 & & & if \; (n\%10) > 0\\ 0 & & & if \; n = 0 \\ F(n/10) & & & Otherwise \end{matrix}\right. \]
تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:
یکی از تیم‌های لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیره باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت می‌شود. به همین دلیل تصمیم می‌گیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانه‌ها اعلام می‌کند که هیئت مدیره باشگاه تنها زمانی از مربی حمایت می‌کنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند.
وب‌سایت UVa یکی از وب‌سایت‌هایی است که امکانات مفیدی را برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی (بالاخص ACM) مهیا کرده است. در این وب‌سایت مجموعه سوالاتی در سطوح مختلف و مشابه سوالات مسابقات برنامه‌نویسی بین‌المللی در دسترس عموم قرار گرفته است که علاقه‌مندان می‌توانند پس از عضویت در سایت، پاسخ هر سوالی را که حل کرده‌اند، ارسال کنند. این جواب‌ها بررسی شده و درست یا نادرست بودن آن به کاربر ابلاغ می‌شود. می‌توان گفت نوعی شبیه‌سازی مسابقات برنامه‌نویسی رسمی انجام می‌گیرد.