(۱۶ آبان ۱۳۹۳ ۰۶:۳۷ ب.ظ)Ametrine نوشته شده توسط:  سلام،

این مساله از روش تقسیم و غلبه حل میشه توی کتاب طراحی مدرسان دیدمش.
ولی کاملاً متوجه نشدم.

ممکنه یه نفر اینو توضیح بده؟

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

(۱۶ آبان ۱۳۹۳ ۰۷:۰۸ ب.ظ)nazanin_sh نوشته شده توسط:  دوست عزیز لطفا سوال و راه حل مورد نظر رو قرار بدید تا بتونیم کمکتون کنیم

سوال نیست آخه. یعنی سوال مشخصی نیست. یه الگوریتمه.
پیچیدگیش میشه: [tex]T(n)=2T(\frac{n}{2}) O(n)[/tex]
یه مجموعه از نقاط توی صفحه مختصات دکارتی داریم به نام P
میخوایم نقطه هایی رو که کمترین فاصله رو با هم دارن، پیدا کنیم.
مجموعه نقاط رو با خط L به دو قسمت مساوی تقسیم میکنیم.
نقاط سمت چپ رو PL و نقاط سمت راست رو PR نامگذاری میکنیم.
تو هر قسمت کمترین فاصله رو پیدا میکنیم و اسمشونو به ترتیب dL و dR میذاریم.
بعد کمترین فاصله بین جفت نقاطی که یک نقطه تو PL باشه یکی تو PR رو پیدا میکنیم اسمشو میذاریم dLR
بعد بین این سه تا کمترین میشه جواب نهایی.
یه قسمت میاد یه فاصله ی d تعریف میکنه و ....
من اونجا رو متوجه نمیشم.

---

(۱۶ آبان ۱۳۹۳ ۰۷:۴۳ ب.ظ)ajabgol نوشته شده توسط:  طبق سوالی که من میبینم حل میکنیم جواب به دست میاد بعدش تحلیل میکنیم تثبیت شه

ممنون از تیکه بامزه‌ی شما.
این یه الگوریتمه اثبات شده هست.
اگر جواب رو نمیدونید بهتره اسپم نفرستید.

طبق سوالی که من میبینم حل میکنیم جواب به دست میاد بعدش تحلیل میکنیم تثبیت شه

فایلی که در لینک زیر هست رو دانلود کنید و مطالعه بفرماید دوست عزیز. امیدوارم بتونه کمک کنه. در صورتی که متوجه نشدید ابهامتون رو بگید در خدمتتون هستم

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

موفق باشید