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

الف) اگر فاصله‌ی شهر اول و شهر آخر کم‌تر از ۱ واحد باشد، الگوریتمی با حداکثر مرتبه‌ی زمانی $nd$ طراحی کنید اکه این حداکثر فاصله‌ی کمینه را با دقت $d$‌رقم اعشار به‌دست آورد.

ب) بدون مفروضات قسمت الف، الگوریتمی با مرتبه‌ی زمانی چندجمله‌ای بر حسب $n$ و $k$ بیابید که محل احداث پمپ بنزین‌ها را به‌طور دقیق مشخص کند.

• سوال بعد
• سوال قبل