دکتری ۹۴ رنگ آمیزی - نسخه‌ی قابل چاپ

دکتری ۹۴ رنگ آمیزی - arash691 - 13 فروردین ۱۳۹۶ ۱۱:۱۸ ق.ظ سلام . اگه ایده ای برای حل دارید بگید ، این مسئله ربطی به رنگ آمیزی گراف داره ؟ جزء کدوم مبحث طراحی الگوریتم هستش ؟ کلید سنجش : گزینه ۱

RE: دکتری ۹۴ رنگ آمیزی - alireza01 - 13 فروردین ۱۳۹۶ ۰۲:۴۳ ب.ظ سلام و وقت بخیر ... برای رنگ آمیزی اعداد ۱ تا ۱۳۹۳ به طوری که سوال میخواد باید وسط این داده ها رنگی که دارد با رنگ بقیه فرق کنه ، یعنی ابتدا وسط داده ها را رنگ کنیم ( و این نکته مهمه که رنگ نقطه وسطی با سمت چپ و راستش متفاوت باشه ) سپس سمت چپ و راستش رو جدا کرده و به همین ترتیب ( وسطی رنگ شده سپس چپ و راست ) ادامه دهیم (که البته رنگ وسطی سمت چپ و وسطی سمت راست میتونه یکسان باشه ) اگر دقت کنیم میبینیم که برای انجام این کار به حداقل [tex]\lceil\: Lgn\: \rceil[/tex] رنگ نیاز داریم و با توجه به اینکه مقدار نقطه های ۱۳۹۳ است تعداد رنگ های لازم برابر با [tex]\lceil\: Lg1393\: \rceil\: =\: \lceil\: 10.443\: \rceil\: =\: 11[/tex] میباشد یعنی گزینه اول ، این مساله ارتباط خیلی نزدیکی با بحث تقسیم و حل در طراحی الگوریتم داره که از روش حل هم میشه برداشت کرد ...