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

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

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

       

بررسی مسأله‌ی آسانسورها (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 $  زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.

      

ورودی برنامه

  [بازگشت به فهرست]

هر ورودی از یک سطر با سه عدد i ، n  و j  شروع می‌شود که به ترتیب تعداد آسانسورها، طبقه‌ی مبدأ و طبقه‌ی مقصد را مشخص می‌کند. در ادامه، طبقات توقف هر آسانسور در یک سطر مجزا آمده است که هر کدام با عدد m  برای مشخص شدن تعداد طبقات توقف شروع می‌شوند.

    n  یک عدد طبیعی نابیشتر از 10  بوده و هر آسانسور حداکثر در 150  طبقه توقف می‌کند. انتهای ورودی‌ها نیز سه عدد صحیح صفر برای i ، n  و j  است.

      

2 2 5

5 0 1 3 5 7

5 0 2 4 6 8

3 3 8

6 0 1 2 3 4 5

5 0 6 7 8 9

4 0 4 5 6

0 0 0

  

خروجی برنامه

  [بازگشت به فهرست]

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

      

7

5

  

    منبع: مسابقه‌ی ACM  منطقه‌ای آسیا 2014 -  سایت تهران - مسأله‌ی Elevators

  [بازگشت به فهرست]

  

حل مسأله

  [بازگشت به فهرست]

طبقات و مسیرهایی بین آنها را می‌توان با استفاده از گراف مدل‌سازی کرد. به این ترتیب که هر طبقه یک گره و ارتباطات بین طبقات با یال مشخص می‌گردد. برای ساختن این گراف، تمامی گره‌های متناظر هر طبقه‌ی توقف آسانسور به سایر گره‌های متناظر طبقات دیگر همان آسانسور متصل می‌شوند. وزن هر یال نیز برابر اختلاف طبقات گره‌های متناظر آنهاست. با توجه به آنکه هزینه‌ی بالا رفتن و پایین آمدن یکی بوده و محدودیتی برای حرکت به سمت بالا یا پایین وجود ندارد، یال‌ها بدون جهت و با وزن مثبت در نظر گرفته می‌شوند. به عنوان مثال، گراف متناظر ورودی نمونه‌ی دوم مسأله  به این ترتیب خواهد شد:

      

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

      

    با توجه به این مدل‌سازی، حل مسأله تبدیل به یافتن کوتاهترین مسیر از گره طبقه‌ی مبدأ به گره طبقه‌ی مقصد می‌شود. پس می‌توان با استفاده الگوریتم دایکسترا با مرتبه‌ی زمانی $O(n^2)$  به نتیجه‌ی مطلوب رسید.

    نکته: الگوریتم فلوید-وارشال راهکار دیگری است که با مرتبه‌ی زمانی $\theta(n^3)$  کوتاهترین مسیر بین تمامی گره‌های گراف را محاسبه می‌کند. در این مسأله هدف یافتن کوتاهترین مسیر بین دو گره مشخص (و نه تمامی گره‌ها) است. بنابراین نیازی به استفاده از الگوریتم فلوید-وارشال با مرتبه‌ی بدتر از الگوریتم دایکسترا احساس نمی‌شود. اما با توجه به اندازه‌ی حد آستانه‌ی مقادیر ورودی مسأله، این الگوریتم نیز در زمان مناسب به جواب می‌رسد. مزیت الگوریتم فلوید-وارشال نسبت به الگوریتم دایکسترا پیاده‌سازی آسان و سریع آن است.


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        متن فارسی مسأله‌ی Encrypted SMS  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        متن فارسی مسأله‌ی Gholam's Simple Game  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010 ‌ منطقه‌ای سایت تهران
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی شماره‌ی 343  از UVa Online Judge ، ار سوالات تمرینی کتاب Art of Programming Contest
        معرفی الگوریتم جستجوی اول عمق (DFS)  برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        ویدئوهای آموزشی کلاس Programming Challenges  شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left