دوایر مسلط سوال مرحله دو ای توضیح کامل

آمار پرسش:

پرسیده شده: 2016-03-04 15:10:50 -0600
مشاهده شده: 393 بار
بروز شده: 2016-04-08 05:17:52 -0600

پرسش‌های مشابه:

سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک

بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳

وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳

گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳

انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳

یافتن کوچکترین پیچ و مهره با مقایسه آنها

دنباله و جادوگر - دوره ی 24 - مرحله ی 2

دوربین های عکاسی

مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23

بازی خاموش کردن چراغ ها

نکاتی در مورد نوشتن پاسخ:

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

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

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

برای این کار ابتدا مجموعه‌ی تهی S را در نظر می‌گیریم. سپس یکی از نقاط را به‌ دل‌خواه انتخاب می‌کنیم و در مجموعه‌ی S قرار می‌دهیم. در مرحله‌ی اول نقطه‌ای را به مجموعه‌ی S اضافه می‌کنیم که بیش‌ترین فاصله را با نقطه‌ی درون SS دارد؛ این فاصله را a1 می‌نامیم. به همین ترتیب در مرحله‌ی iiام نقطه‌ای را به مجموعه‌ی SS اضافه می‌کنیم که بیش‌ترین فاصله را از مجموعه‌ی SS دارد (فاصله‌ی یک نقطه‌ی دل‌خواهِ A از مجموعه نقاط S را فاصله‌ی AA تا نزدیک‌ترین نقطه‌ی S به A تعریف می‌کنیم). این بیش‌ترین فاصله را ai می نامیم. بعد از انجام k−1 مرحله، حال مجموعه‌ی S شامل k نقطه است و فاصله های a1، a2، …، و ak−1 تعیین شده اند. فرض کنید مرحله‌ی kام را نیز انجام دهیم ولی با این تفاوت که در این مرحله نقطه ی به دست آمده را به S اضافه نمی‌کنیم، و فقط فاصله‌ی ak را یادداشت می‌کنیم.

الف) ثابت کنید اگر k دایره به مراکز نقاط درون S و به شعاع ak در صفحه رسم کنیم، این دایره‌ها تمام n نقطه را در بر می‌گیرند.

ب) ثابت کنید به ازای هر عدد r، اگر k دایره‌ی دل‌خواه به شعاع r وجود داشته باشند که تمام n نقطه را در بر گیرند، آن‌گاه خواهیم داشت: ak≤2r

2016-03-04 15:10:50 -0600

کلیم 31 ● 2 ● 2 ● 3

پاک‌کردن ویرایش سوال

نظرات

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 08:49:24 -0600 امیر شکری

1 پاسخ

$قسمت الفنقاط S که در مرکز دایره قرار گرفتند، پس در دایره هستند، فاصله‌ی هر نقطه خارج از S، حداقل از یکی از نقاط داخل S کمتر یا مساوی با a_k است، پس هر نقطه درون یا روی محیط حداقل یکی از دایره‌ها قرار می‌گیرد.قسمت بلم۱: دنباله‌ی a_1,a_2,..,a_k یک دنباله‌ی نزولی است. اثبات لم: فرض کنید چنین نباشد پس a_i<a_(i+1) است، فرض کنید نقطه‌ای که فاصله‌ی آن در مرحله‌ی iام a_i بوده v و نقطه‌ای که در مرحله‌ی i+1ام، فاصله‌اش a_(i+1) بوده u باشد و W را مجموعه‌ی نقاط در مرحله‌ی iام تعریف می‌کنیم. فاصله‌ی نقطه‌ی u از W∪{v} برابر با a_(i+1) است. پس فاصله‌اش با W حداقل a_(i+1) است. پس در مرحله‌ی iام، باید نقطه‌ی u انتخاب می‌شد نه نقطه‌ی v پس این تناقض است. پس فرض خلف باطل و حکم ثابت است.اثبات مسئله:با استقرا بر روی k حکم را ثابت می‌کنیم:پایه: اگر k=1 باشد، حکم درست است، زیرا تنها یک دایره می‌توان کشید و این دایره باید هم یک نقطه‌ی درون S و نقطه‌ای که فاصله‌ی آن با S برابر با a_1 است را شامل شود، پس قطر دایره حداقل a_1 است، پس 2r≥a_1=a_k→a_k≤2r است.گام استقرا: اثبات می‌کنیم اگر حکم برای k<d برقرار باشد، حکم برای k=d نیز برقرار است.نقاط درون S را در نظر بگیرید. دو حالت وجود دارد: برای پوشاندن نقاط S از k دایره استفاده کرده باشیم:در این صورت یکی از دایره‌ها هم باید یکی از نقاط S را داشته باشد و هم نقطه‌ای که فاصله‌ی آن با S برابر با a_k است. پس قطر دایره حداقل a_k است. پس a_k≤2r و حکم در این حالت اثبات شد. برای پوشاندن نقاط S از حداکثر k-1 دایره استفاده کرده‌باشیم:در این حالت، طبق فرض استقرا برای پوشاندن نقاط S با دایره‌هایی به شعاع r، باید 2r≥a_(k-1) باشد. از طرفی طبق لم۱ داریم a_(k-1)≥a_k، پس 2r≥a_k است و در این حالت نیز حکم ثابت شد.پس گام استقرا ثابت شد. پس حکم برای تمام kهای طبیعی برقرار است.$

2016-04-08 05:17:52 -0600

توفیقی 1621 ● 17 ● 21 ● 42

پاک‌کردن ویرایش پاسخ

نظرات

همين جورى كه گفتيد نميشه مستقيم گفت؟ اگر دايره اى بود كه نقطه ak به همراه يكى از مجموعه S رو داشت كه حله. در غير اينصورت k-1 دايره و k نقطه از S هست پس دوتاشون حتما تو يه دايره ميفتن؛ حالا از بين اين دو تا نقطه يكيشون قديمى تره، پس فاصله نقطه جديدتر از نقطه قديمى تر طبق لمى كه اثبات شده حداقل ak

2016-04-09 11:22:49 -0600 خودخودم

@خودخودم متوجه منظورتون نمیشم.

2016-04-09 11:24:03 -0600 توفیقی

هست. 😄

2016-04-09 11:25:55 -0600 خودخودم

مينويسم ميفرستم الآن ببينيم درسته يا نه 😄

2016-04-09 11:26:43 -0600 خودخودم

آره آره! میشه گفت! ممنون که گفتی!

2016-04-09 11:30:28 -0600 توفیقی

اطلاعات بیشتر