الگوریتمستان
برنامهنویسی، طراحی الگوریتم و حل مسئلههای الگوریتمی
رابطهی جمع زدن دو عدد را در نظر بگیرید:
این عملیات در پسزمینه انجام میگیرد که کنترل آن خارج از اختیار ما است و خروجی آن لزوما نشانگر جمع صحیح نیست. اما میتوانیم هر تعداد ستون دلخواه از آن را حذف کنیم تا به جمع درستی برسیم. به عنوان نمونه، در مثال زیر میتوانیم با حذف ستونهای دوم و چهارم به جمع درستی برسیم:
پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجستهی قرن بیستم است که تا پایان عمر خود تلاش گستردهای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب میگردد.
با توجه به آنکه همکاری با ایشان برای هر کس ممکن نبود، تلاش میکردند با نفراتی در انتشار مقالهی علمی همکاری کنند که با این دانشمند بزرگ مقاله داشتند. این رویکرد باعث پدید آمدن عدد اردوش (Erdős number) یا فاصلهی همکاری اردوش شد؛ یعنی برای نویسندگانی که به صورت مستقیم با ایشان همکاری داشتند عدد 1 و برای کسانی که با این نفرات مقاله داشتند عدد 2 نسبت داده شد و ارتباطات دورتر نیز به همین ترتیب با اعداد طبیعی بعدی مشخص شدند.
جدولی با n سطر و m ستون در نظر بگیرید. در تمام خانههای این جدول عدد 0 نوشته شده است. در ابتدای کار حامد در خانهای از جدول ایستاده است. او عدد این خانه را پاک میکند و عدد 1 را به جای آن مینویسد. حامد شروع به حرکت میکند و در هر ثانیه یک خانه به بالا، راست، پایین یا چپ میرود. او با وارد شدن به هر خانه، عدد نوشته شده در خانه را پاک میکند و عددی یک واحد بزرگتر از آخرین عددی که نوشته است را مینویسد و بعد از مدتی متوقف میشود. میدانیم حامد در انتهای حرکت خود تمام خانههای جدول را دیده است.
ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاقها و کلاسهای طبقات مختلف، آسانسورها به گونهای تنظیم شدهاند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمههای داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم میکند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاقهای خود دارند. اما در حالت کلی باعث سردرگمی میشود. اگر شخصی بخواهد از طبقهای به طبقهی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش میآید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخابها شخص را در زمان کمتری به مقصد میرساند. اگر مسیر حرکت شخص از طبقهی i به طبقهی j به صورت $ i = f_1 \rightarrow f_2 \rightarrow f_3 \rightarrow \cdots \rightarrow f_k = j $ نمایش داده شود، عبارت $ \sum_{r=1}^{k-1} \vert f_i - f_{i+1} \vert $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامهای بنویسید که افراد را در استفادهی بهتر (در زمان کمتر) از آسانسورها یاری کند.
دو دوست در زمین نامحدودی متشکل از حصارهای دایرهای شکل هماندازه با ساختار زیر قرار دارند:
یکی از دوستان قصد دارد با حرکت در این ساختار نزد دوست دیگر خود برود. حرکت در این ساختار در هر گام شامل جابجایی به یکی از دایرههای مجاور است. دو دایره مجاور هستند اگر در یک نقطه مشترک باشند.
با توجه به موقعیت دو دوست در این ساختار، هدف یافتن حداقل گامهای مورد نیاز برای رسیدن دو دوست به یک خانه است. توجه داشته باشید که محل اولیهی دو دوست لزوما متمایز نبوده و در کل مراحل یک دوست در محل خود ثابت مانده و دوست دیگر حرکت میکند.
ماتریس مربعی با ابعاد $N$ در $N$ و درایههایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.
به عنوان مثال، برای ماتریس زیر:
\[ \begin{matrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \end{matrix} \]
زیرماتریس بیشینه به این ترتیب خواهد بود:
یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونهای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه میکنند که باعث بالا رفتن حجم ترافیک میشود. مدیران مرکز سفارش نصب دوربین ویژهای در نزدیکی آن محل را دادهاند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد.
عملکرد دوربین از n دقیقهی قبل آغاز شده است. شما باید با توجه به اطلاعات ارسال شده از طریق این دوربین، تعداد خودروهایی را که در حال حاضر پشت چراغ راهنمایی متوقف شدهاند محاسبه کنید.
تابع بازگشتی (F(n با تعریف زیر مفروض است:
\[ F(n)= \left\{\begin{matrix} n \% 10 & & & if \; (n\%10) > 0\\ 0 & & & if \; n = 0 \\ F(n/10) & & & Otherwise \end{matrix}\right. \]
تابع (S(p, q به این صورت تعریف شده است:
\[ S(p,q)=\sum_{i=p}^{q} F(i) \]
مقدار (S(p, q را به ازای مقادیر ورودی p و q محاسبه کنید.
یکی از تیمهای لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیرهی باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت میشود. به همین دلیل تصمیم میگیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانهها اعلام میکند که هیئت مدیرهی باشگاه تنها زمانی از مربی حمایت میکنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند. مربی میخواهد بداند چقدر احتمال دارد به این موفقیت دست پیدا کند و از شما کمک میخواهد.فرض کنید احتمال کسب برد، باخت و تساوی در مسابقههای بعدی از روی مسابقات انجام شده تا به حال به دست میآید. به عنوان مثال اگر این تیم از 10 بازی انجام دادهی قبلی 3 برد داشته باشد، احتمال برد در آینده 30% خواهد بود.