بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus

مسأله‌ی انتخابات

[برو به فهرست نوشته‌ها]
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران

مسأله

    جناب خان که با کسب و کار لبوی خود میلیاردر شده است، می‌خواهد رئیس جمهور شود! در کشور او که از چندین ایالت تشکیل شده است، از روشی با عنوان هیئت انتخاب (یا هیئت الکترال) برای انتخاب رئیس جمهور استفاده می‌شود. در چنین ساختاری شمارش رأی در هر ایالت به صورت مستقل انجام می‌شود و هر ایالت متناسب با جمعیت خود تعدادی نماینده در هیئت انتخاب کنندگان رئیس جمهور دارد. تمام نمایندگان یک ایالت در نهایت به نامزدی رأی می‌دهند که در آن ایالت اکثریت آرا را کسب کرده باشد. اگر نامزدها رأی برابر داشته باشند، هر ایالت قوانین خاص خود برای انتخاب نهایی را دارد. در نهایت رئیس جمهور کسی است که بیش از نصف مجموع رأی‌های هیئت انتخاب را از آن خود کند.

ادامه ...

مسأله‌ی اعداد اردوش

[برو به فهرست نوشته‌ها]
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge

مسأله

    پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته‌ی قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

ادامه ...

فایل سرآیند algorithm

[برو به فهرست نوشته‌ها]
        معرفی فایل سرآیند algorithm از کتابخانه قالب استاندارد زبان برنامه‌نویسی ++C به همراه نمونه کد

فایل سرآیند (هدر فایل) algorithm از جمله فایل‌های سرآیند تعاریف کتابخانه‌ قالب استاندارد (STL) زبان برنامه‌نویسی ++C‌ است که به طور عمده شامل توابعی برای کار با مجموعه‌ای از داده‌ها (آرایه‌ها و لیست‌ها) است. با استفاده از این توابع به راحتی می‌توان با تنها یک خط کد عملیات جستجو، مرتب‌سازی، شمارش و بررسی یک خاصیت در تمامی داده‌های یک بازه‌ی مشخص را انجام داد.

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

      

ادامه ...

مسأله‌ی بشکه‌های آب

[برو به فهرست نوشته‌ها]
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان

مسأله

    $n$ بشکه‌ی آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه‌ی $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه‌ی $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه‌ی $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه‌ی شماره‌ی یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه‌ی دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.

ادامه ...

مسأله‌ی آسانسورها

[برو به فهرست نوشته‌ها]
        بررسی مسأله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM

مسأله

    ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی 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 $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.

ادامه ...

مباحث کاربردی در مسابقات برنامه‌نویسی

[برو به فهرست نوشته‌ها]
        عناوین بخشی از مباحث پرکاربرد در سوالات مسابقات برنامه‌نویسی

یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی معتبر همچون ACM این است که چگونه خود را برای این مسابقات آماده کنیم؟ تا چه حد تسلط به یک زبان برنامه‌نویسی یا مفاهیم مختلف طراحی الگوریتم و شاخه‌های وابسته مورد نیاز است؟

    کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده‌ی موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات که برای هر علاقه‌مند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.

ادامه ...

مسأله‌ی حداکثر مجموع

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

مسأله

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

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

ادامه ...

مسأله‌ی چراغ راهنمایی

[برو به فهرست نوشته‌ها]
        بررسی سوال مسابقات برنامه‌نویسی Turn for MEGA و راه حل آن

مسأله

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

ادامه ...

مسأله‌ی مربی ناامید

[برو به فهرست نوشته‌ها]
        بررسی مسأله‌ی مربی ناامید، از سوالات مسابقات برنامه‌نویسی ACM

مسأله

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

ادامه ...