برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار – راهنمای کاربردی

در این مطلب، روش نوشتن برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ پی» (PHP) انجام شده است.

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار

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

مثال زیر، به درک بهتر این مطلب، کمک می‌کند.

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time (time between 11:00 to 11:20)

نیاز به پیدا کردن حداقل تعداد قطارهایی است که در هر بار، در یک ایستگاه قطار وجود دارند. یک راهکار ساده، هر بار در نظر گرفتن یک وقفه (فاصله | فرجه) و سپس، پیدا کردن تعداد وقفه‌هایی است که با آن وقفه هم‌پوشانی دارند. بدین صورت، ردیابی حداکثر تعداد وقفه‌هایی که با یک وقفه هم‌پوشانی دارند، ادامه پیدا می‌کند. پیچیدگی زمانی این روش از درجه O(n^۲)‎ است.

فیلم آموزش محاسبات عددی با متلب MATLAB در فرادرس

کلیک کنید

می‌توان این مسئله را در زمانی از درجه O(N Log N)‎ حل کرد. ایده آن است که همه رویدادها به صورت مرتب شده‌ای در نظر گرفته شوند. هنگامی که همه رویدادها به صورت مرتب شده باشند، می‌توان تعداد کل قطارها و تعداد قطارهایی که رسیده‌اند را پیگیری کرد؛ اما نمی‌توان این کار را برای قطارهای خروجی انجام داد. برای درک بهتر مطلب، مثال زیر قابل توجه است.

  arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}
    dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

All events sorted by time.
Total platforms at any time can be obtained by subtracting total 
departures from total arrivals by that time.
 Time     Event Type     Total Platforms Needed at this Time                               
 9:00       Arrival                  1
 9:10       Departure                0
 9:40       Arrival                  1
 9:50       Arrival                  2
 11:00      Arrival                  3 
 11:20      Departure                2
 11:30      Departure                1
 12:00      Departure                0
 15:00      Arrival                  1
 18:00      Arrival                  2 
 19:00      Departure                1
 20:00      Departure                0

Minimum Platforms needed on railway station = Maximum platforms 
                                              needed at any time 
                                           = 3

در ادامه، پیاده‌سازی رویکرد بالا ارائه شده است. شایان ذکر است که پیاده‌سازی ارائه شده، یک لیست مجرد مرتب‌سازی شاده از همه رویدادها نمی‌سازد. بلکه، به طور جداگانه‌ای آرایه‌های arr[]‎ و dep[]‎ مرتب می‌شوند و سپس، از فرایند ادغام موجود در «مرتب سازی ادغامی» (Merge Sort) استفاده می‌شود. شایان ذکر است که در این رویکرد، فرض بر این است که همه قطارها در تاریخ یکسانی، ورود و خروج دارند.

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار در ++C

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار در جاوا

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار در پایتون ۳

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار در #C

برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار در PHP

خروجی قطعه کدهای بالا، به صورت زیر است.

Minimum Number of Platforms Required = 3

در روش ارائه شده در بالا، از «برنامه‌نویسی پویا» (Dynamic Programming) استفاده شده است.

پیچیدگی زمانی این روش، با فرض اینکه الگوریتم مرتب‌سازی برای مرتب کردن arr[]‎ و dep[]‎ از درجه O(N Log N)‎ باشد، از درجه O(N Log N)‎ است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده