الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب آمادگی مسابقه ACM نوشته‌ها با برچسب آمادگی مسابقه ACM - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

آمادگی مسابقه ACM

»

مسئله

دو دوست در زمین نامحدودی متشکل از حصارهای دایره‌ای شکل هم‌اندازه با ساختار زیر قرار دارند:

  

مسئله‌ی دوستان خوب

  

یکی از دوستان قصد دارد با حرکت در این ساختار نزد دوست دیگر خود برود. حرکت در این ساختار در هر گام شامل جابجایی به یکی از دایره‌های مجاور است. دو دایره مجاور هستند اگر در یک نقطه مشترک باشند.

با توجه به موقعیت دو دوست در این ساختار، هدف یافتن حداقل گام‌های مورد نیاز برای رسیدن دو دوست به یک خانه است. توجه داشته باشید که محل اولیه‌ی دو دوست لزوما متمایز نبوده و در کل مراحل یک دوست در محل خود ثابت مانده و دوست دیگر حرکت می‌کند.

ادامه ...

مسئله

ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.

به عنوان مثال، برای ماتریس زیر:

  

\[ \begin{matrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \end{matrix} \]

  

زیرماتریس بیشینه به این ترتیب خواهد بود:

ادامه ...

مسئله

یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونه‌ای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه می‌کنند که باعث بالا رفتن حجم ترافیک می‌شود. مدیران مرکز سفارش نصب دوربین ویژه‌ای در نزدیکی آن محل را داده‌اند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد.

عملکرد دوربین از n دقیقه‌ی قبل آغاز شده است. شما باید با توجه به اطلاعات ارسال شده از طریق این دوربین، تعداد خودروهایی را که در حال حاضر پشت چراغ راهنمایی متوقف شده‌اند محاسبه کنید.

ادامه ...

دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود.

  

$C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$

  

این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:

1- تعداد درخت‌های دودویی با n رأس داخلی برابر $C_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 محاسبه کنید.

ادامه ...

تعریف ترکیب (Combination)

تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:

  

\[C(n,r) = C_r^n= \begin{pmatrix} n \\ r \end{pmatrix} \]

این عدد به ضریب دوجمله‌ای نیز مشهور است که یکی از محل‌های استفاده‌ی آن است.

ادامه ...

مسئله

یکی از تیم‌های لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیره‌ی باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت می‌شود. به همین دلیل تصمیم می‌گیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانه‌ها اعلام می‌کند که هیئت مدیره‌ی باشگاه تنها زمانی از مربی حمایت می‌کنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند. مربی می‌خواهد بداند چقدر احتمال دارد به این موفقیت دست پیدا کند و از شما کمک می‌خواهد.فرض کنید احتمال کسب برد، باخت و تساوی در مسابقه‌های بعدی از روی مسابقات انجام شده تا به حال به دست می‌آید. به عنوان مثال اگر این تیم از 10 بازی انجام داده‌ی قبلی 3 برد داشته باشد، احتمال برد در آینده 30% خواهد بود.

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
»  ویدئوهای آموزشی کلاس Programming Challenges
ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
»  ابزار UVA Toolkit
معرفی وب‌سایت UVA Toolkit برای کمک به حل سوالات برنامه‌نویسی UVA Online Judge
»  کتاب طراحی الگوریتم با رویکردی خلاقانه
معرفی کتاب Introduction to Algorithms: A Creative Approach  با قابلیت دانلود نسخه‌ی الکترونیکی
»  کتاب Concrete Mathematics
معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
»  کتاب چالش‌های برنامه‌نویسی
معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود کتاب، فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
»  کتاب هنر مسابقات برنامه‌نویسی
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
برچسب‌ها
#آموزش الگوریتم #آمادگی المپیاد کامپیوتر #الگوریتم‌های گراف #آموزش برنامه‌نویسی ++C #ویدئوی آموزشی #ترجمه‌ی فارسی سوالات ACM #سوالات برنامه‌نویسی #الگوریتم‌های بازگشتی #حل سوالات UVa Online Judge #الگوریتم فلوید-وارشال #کتاب الگوریتم #درخت پوشا #الگوریتم‌های عقبگرد #مسابقات برنامه‌نویسی #کتابخانه قالب استاندارد ++C #نمونه سوال فارسی مسابقات ACM #حل سوالات ACM-ICPC #سوالات UVa Online Judge #تمرین طراحی الگوریتم #الگوریتم‌های مسیریابی #حل سوالات Timus Online Judge #محاسبات ریاضی #ترجمه‌ی فارسی سوالات UVa Online Judge #مسابقه برنامه نویسی #جستجوی اول عمق #مسئله‌ی کوله‌پشتی #تمرین مسابقه برنامه‌نویسی #مسئله‌های برنامه‌نویسی #آمادگی مسابقه ACM #کتاب الکترونیکی #مسابقه برنامه‌نویسی #نمونه سوالات مسابقه برنامه‌نویسی #ماتریس #الگوریتم #نمونه سوال مسابقه ACM #ساختمان داده #الگوریتم‌های کوتاهترین مسیر #آمادگی مسابقه برنامه‌نویسی #پیمایش گراف #مسابقات برنامه‌نویسی ACM #حل سوالات مسابقات برنامه‌نویسی #سوالات مسابقات برنامه‌نویسی بیان #مسأله‌های الگوریتمی #معرفی وب‌سایت #الگوریتم‌های مرتب‌سازی #الگوریتم دایکسترا #ترجمه‌ی فارسی سوالات برنامه‌نویسی #تمرین المپیاد کامپیوتر #سوالات مسابقات ACM-ICPC #صف #وبلاگ #کتاب مسابقات برنامه‌نویسی #نمونه سوال فارسی مسابقه‌ی ACM #درخت‌ها #مسئله‌های الگوریتمی #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #دانلود کتاب #آموزش ساختمان داده‌ها #نکات برنامه‌نویسی #برنامه‌نویسی #منبع آموزشی #آموزش طراحی الگوریتم #الگوریتم‌های تقسیم و غلبه #ترجمه فارسی سوالات کتاب Programming Challenges #نمونه سوال فارسی مسابقات برنامه‌نویسی #حل مسئله‌‌ی الگوریتمی #سوالات چالشی برنامه‌نویسی #الگوریتم‌های برنامه‌نویسی پویا #الگوریتم‌های حریصانه #گراف #تکنیک‌های طراحی الگوریتم #مسأله‌های برنامه‌نویسی #برنامه‌نویسی ++C #جستجوی اول سطح