یک چالش ریاضی برای برنامه نویس های عزیز

چند وقت پیش در اتوبوس بین شهری کنار برنامه نویسی بودم.مثل اینکه محلی که در آن کار می کرد به مسئله ای برخورد کرده بودند و آن را به صورت یک مسئله ریاضی مدل و ساده کرده بودند و او ماموریت داشت بهینه ترین و سریع ترین الگوریتم را برای حل این مسئله پیدا کند.

منم که خط خطی کردن های او را دیدم، با او هم صحبت شدم و از مسئله ش عکس گرفتم تا در وقت بیکاریم روی آن فکر کنم.

البته خودم حس می کنم مسئله یکسری شرایط دیگر هم داشته که فراموش کرده به من توضیح بده ولی خب فتم شاید برای شما هم حل این مسئله جالب باشه.

صفحه مختصات زیر را با نقاط نمایش داده شده فرض کنید که در آن هر نقطه مختصات یک ساختمان را نشان می دهد.همچنین این ساختمان ها دارای یک ارتفاع به اندازه ی تصادفی هستند ، که ارتفاع مجاز این ساختمان ها بین 8 متر تا 20 متر است.

تعدادی ساختمان (نقطه مختصات) در این صفحه مختصات نشان داده نشده است.

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

مسئله از شما موارد زیر را می خواهد :

  • محدوده تراکم نقاط (مختصات طول و عرض محدوده تراکم)
  • (مختصات) ساختمان هایی که در صفحه مختصات وجود ندارند را همراه با ارتفاع آن ها پیش بینی کنید.


صفحه مختصات
صفحه مختصات

اگر دوست داشتید ، می توانید راه حل خودتون را همین جا مطرح کنید.?