مساله 76 - صفحه 74 کتاب «مساله‌های الگوریتمی»: مسیر حرکت ماشین‌ها

n ماشین در n نقطه‌ی متمایز از مسیری دایره‌ای شکل به محیط 100 کیلومتر قرار گرفته‌اند. سرعت حرکت همه‌ی این ماشین‌ها ثابت و برابر 1 کیلومتر در دقیقه است. در لحظه‌ی صفر، هر کدام از ماشین‌ها با این سرعت ثابت در جهتی دلخواه (جهت مثبت یا منفی مثلثاتی) دور دایره شروع به حرکت می‌کنند. هرگاه دو ماشین به هم برخورد کنند، هر دو بدون تاخیر یا کم شدن سرعت جهت خود را برعکس می‌کنند و به حرکت خود ادامه می‌دهند.

مسیر حرکت ماشین‌ها

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

در سطر اول فایل ورودی، عدد n (n ≤ 20) و در n سطر بعد، در هر سطر ابتدا عددی حقیقی که نشان دهنده‌ی محل ماشین و سپس عدد +1 یا -1 بسته به اینکه جهت حرکت اولیه در جهت مثبت یا منفی مثلثاتی باشد نوشته شده است. محل ماشین نسبت به یک نقطه‌ی ثابت سنجیده می‌شود و عددی حقیقی، نامنفی و کمتر از 100 است. در بقیه‌ی سطرهای فایل، در هر سطر یک عدد t نوشته شده است که عددی حقیقی و کمتر از 10000 است و زمان را بر حسب دقیقه نشان می‌دهد.

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

از آنجایی‌که سرعت حرکت ماشین‌ها ثابت و برابر 1 کیلومتر در دقیقه است، لذا می‌توان گفت که بعنوان مثال پس از 10 ثانیه هر یک از ماشین‌ها 10 کیلومتر مسیر طی کرده‌اند اما سوال اینجاست که این 10 کیلومتر طی مسیر چقدر جابجایی را به‌همراه داشته است؟ یعنی ممکن است 3 کیلومتر در جهت مثبت حرکت کرده و به ماشینی که از روبرو می‌آمده برخورد کرده و تغییر مسیر بدهد و 7 کیلومتر باقیمانده را در جهت منفی طی کند. بنابراین با وجود 10 کیلومتر حرکت، کل جابجایی 4 کیلومتر در جهت منفی می‌باشد.

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

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

حالت اول: برخورد بعد از زمان t اتفاق می‌افتد (یا در لحظه t)، لذا کار به ساده‌ترین شکل ممکن قابل انجام است و کافی است مکان هر ماشین پس از گذشت زمان t را محاسبه کنیم:

که در آن P_i مکان ماشین iاُم در لحظه t، P_0i مکان اولیه‌ی ماشین iاُم و t لحظه‌ای است که مساله از ما خواسته تا مکان ماشین‌ها را در آن محاسبه کنیم. وجود علامت ± به این علت است که برحسب جهت حرکت ماشین (که یکی از اعداد +1 یا -1 است)، می‌تواند به سمت مثبت یا منفی‌حرکت کند. اگر جهت حرکت ماشین iاُم را با D_i نشان دهیم، داریم:

حالت دوم: برخورد قبل از زمان t مثلا در لحظه t₁ اتفاق می‌افتد که البته این حالت نیز ساده است. کافی است مکان و جهت حرکت ماشین‌ها را در لحظه t₁ محاسبه کنیم و لحظه‌ی t₁ را مبداء زمان قرار دهیم. یعنی فرض را بر این می‌گیریم که مکان اولیه و جهت حرکت ماشین‌ها از ابتدا همین مقادیری بودند که در لحظه‌ی t₁ محاسبه کردیم. البته یک تغییر مهم و کلیدی هم داریم و آن کم کردن از مقدار t به اندازه‌ی t₁ است. چون اگر مبداء زمان را از صفر به t₁ شیفت دادیم، یعنی به اندازه t₁ جلو آمده‌ایم و زمان t را نیز باید به همان اندازه به جلو بیاوریم (به اندازه‌ی t₁ از t کم کنیم).

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

یک مطلب مهم در این مساله جهت حرکت ماشین‌هاست که اگر دو ماشین در یک جهت حرکت می‌کنند، امکان برخورد با یکدیگر را ندارند اما در مورد ماشین‌هایی که در خلاف جهت هم حرکت می‌کنند، تشخیص برخورد کمی پیچیده است و این تشخیص وقتی پیچیده‌تر می‌شود که مسیر حرکت دایره شکل است و ماشینی که به کیلومتر 100 می‌رسد در واقع به کیلومتر 0 رسیده و به حرکت خود ادامه می‌دهد. درواقع کاری که باید بکنیم اینست که تشخیص بدهیم ماشین‌هایی که در خلاف جهت هم حرکت می‌کنند از همدیگر دور می‌شوند یا به طرف هم می‌آیند.
تاکید بیشتر من بخاطر حالت‌های خاص است مثلا ماشینی که در 5 کیلومتری مبدا در جهت منفی در حرکت است با ماشینی که در 90 کیلومتری مبدا در جهت مثبت حرکت می‌کند، 15 کیلومتر از هم فاصله دارند و بعد از 7.5 دقیقه به هم برخورد می‌کنند.