الگوریتم ترکانیدن بادکنک ها در راستای مختلف - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۶۰ نفر آنلاین
۰ عضو و ۱۶۰ مهمان در سایت حاضرند

الگوریتم ترکانیدن بادکنک ها در راستای مختلف

+1 امتیاز
106 بازدید
سلام

ما n تا بادکنک داریم که به صورت دایره ای هستند . میخواهیم با کمترین تعداد تیری که همشون از مبدا پرتاب میشن این بادکنکارو بترکانیم .

این تیرها فقط در جهت مثب پرتاب میشن و قدرت اینو دارن که تموم بادکنکای درراستاشون را بترکانن . هر تیری هم در راستای زاویه پرتاب شده حرکت میکنه

اگرم دوتا بادکنک مماس باشن هر دو میترکن . از دایره ها شعاع و مرکز داده میشه .

سوالم اینه که دراین صفحه باید الگوریتم دایره هایی که با هم مماس میشن و به تعدادشون از تعداد تیرها کم میشه را چجوری محاسبه کنیم ؟

کلا الگوریتمشو مشکل دارم .

ممنون میشم یکی توضیح بده .
سوال شده اردیبهشت 18, 1394  بوسیله ی Azar (امتیاز 813)   4 18 58
به عبارتی دیگه میخواید ببینید که برای ترکانیدن بادکنک های مماس چند تا تیر نیاز میشه ؟
(مثلا برای ترکاندین ۵ تا بادکنک که ۳ تاشون مماس هستند ۳ تا تیر لازمه)
فضای ۳ بعدی یا ۲ بعدی ؟
کلا که میخوام ببین برای ترکانیدن کل بادکنک ها چند تا دیر لازم میشه ؟
گفتم صفحه (یعنی دو بعدی )
(مثلا برای ترکانیدن 5 تا بادکنک که چهار تاشون دو به دو با هم بازه مشترک دارند (یعنی یا مماس هستند یا بازه دارند ) 3 تا تیر لازم میشه )

2 پاسخ

0 امتیاز

 

اول اینکه بیاید برای هر دایره ۲ تا خط فرضی داشته باشید. طبق شکل بالا ۲ تا خط قرمز برای  دایره شماره ۱ و ۲ تا خط آبی برای دایره شماره ۲..

بین هر ۲ خط فرضی فضایی بوجود میاد. حالا باید ببینید که آیا فضای بوجود اومده توسط ۲ خط آبی داخل فضای بوحود اومده ی قرمز هست یا نه ؟ درواقع باید اشتراک این ۲ تا رو حساب کنید. اگر داخل بود که یعنی با یک تیر میشه این ۲ تا دایره رو ترکانید.

برای تعداد بیشتر دایره ها هم همینطور میشه. فقط باید فضاهای مشترک قبلی رو داشته باشید و ببنید که دایره جدید با فضای قبلی اشتراکی داره یا نه ؟ اگر داشت پس اون دایره هم میشه با همون تیر زد ! به همین ترتیب باید از نزدیک ترین دایره شروع کرد به حساب کردن .

نکته دیگه اینه که باید دایره های حساب شده برای هر تیر رو دوباره برای تیر دیگه ای استفاده نکنید . و دوباره نکته دیگه اینه که باید برای هر تیر بهترین جالت رو از اشتراک ها انتخاب کنید. خودمم زیاد نمیدونم چی نوشتم ولی فکر میکنم بشه چیزی ازش فهمید/

پاسخ داده شده اردیبهشت 26, 1394 بوسیله ی Ali Rahbar (امتیاز 4,809)   5 14 46
0 امتیاز

هر بادکنک که در مسئله داده شده است را راس یک گراف در نظر بگیرید.

بین دو راس یال رسم می کنیم اگر و فقط اگر بتوان با پرتاب یک تیر هر دو بادکنک را زد.

 

لم: اگر n بازه متناهی داشته باشیم که هر دو تایی باهم اشتراک داشته باشند. نقطه ای وجود دارد که همه ی بازه ها آن را دارند.

 

 ادعا می کنم تنها زمانی می توان با یک تیر m بادکنک را زد که زیر گراف القایی این m بادکنک در گراف خوشه (گراف کامل) باشد.

 

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

 

طرف دوم حکم: اگر در گراف خوشه m تایی وجود داشته باشد. می توان تیری زد که همه ی این m بادکنک بترکند. برای هر کدام از این m بادکنک بازه ای در نظر بگیرید که نشان دهنده ی زاویه هایی است که اگر تیر در آن زاویه های باشد آن بادکنک می ترکد. حال می دانیم اگر دو بادکنک با یک تیر زده شوند. بازه های آن ها با هم اشتراک دارد. چون زیر گراف القایی این m بادکنک خوشه است یعنی در این m بازه هر دوتایی با هم اشتراک دارد. پس طبق لم زاویه ای هست که همه ی آن ها دارند. پس با پرتاب تیر در آن زاویه همه ی بادکنک ها می ترکند.

 

حال مسئله ساده شد. چون به اندازه ی تعداد خوشه های ماکسیمال گراف حداقل باید تیر پرتاب کنیم.

 

نکته: توجه کنبد مهم است که دایره ها بالای محور x ها باشد چون در غیر این صورت ممکن است بازه ها متناهی نشود.

 

برای دوستان اهل کد زدن جالب است که پیچیدگی این الگوریتم از اردر n*e است!

پاسخ داده شده اردیبهشت 31, 1394 بوسیله ی Amin (امتیاز 804)   2 8 43
...