بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی کاشیکاری - الگوریتمستان
الگوریتمستان
5014.545.00
  »  

       

بحث در مورد مسأله‌ی کاشیکاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل

آنچه در این نوشته می‌خوانید:

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

    فرض کنید قطعه زمین مربعی شکل با ابعادی از توان عدد دو داریم. مثلا با ابعاد 16  متر:

      

مسأله‌ی کاشیکاری

      

    هدف فرش کردن این قطعه زمین با استفاده از موزاییک‌هایی با شکل‌های زیر است:

      

مسأله‌ی کاشیکاری

      

    به قسمی که یکی از خانه‌های زمین شطرنجی شده‌ی فوق پوشیده نشود. می‌توان فرض کرد از این خانه برای احداث باغچه یا حوضچه‌ی کوچکی استفاده خواهد شد. توجه داشته باشید که اندازه‌ی اضلاع مربع‌های کوچک موزاییک‌ها نیز همانند صفحه‌ی شطرنجی فوق یک متر است. در ضمن حق شکستن این موزاییک‌ها به تکه‌های کوچکتر را نداریم.

    به عنوان مثال، فرض کنید زمینی با ابعاد چهار متر داریم که می‌خواهیم خانه‌ی مشخص شده زیر پوشیده نشود:

      

مسأله‌ی کاشیکاری

      

    می‌توان این زمین را به صورت زیر فرش کرد:

      

مسأله‌ی کاشیکاری

      

    اما راه حل کلی مسأله چیست؟

    با توجه به اینکه ابعاد زمین توانی از عدد دو است، روش تقسیم و حل را برای پوشانیدن این قطعه زمین امتحان می‌کنیم. بر اساس تعریف روش تقسیم و حل، باید بتوان مسأله را به زیرمسائلی از نوع خود مسأله تقسیم کرد و با ادغام نتایج حاصل از آنها، به نتیجه‌ی اصلی دست پیدا کرد. چون ابعاد این قطعه زمین توانی از عدد دو است، پس می‌توان آن را به دو قسمت تقسیم کرد. با تقسیم طول و عرض زمین به دو قسمت، چهار قطعه زمین کوچکتر به دست می‌آید:

      

مسأله‌ی کاشیکاری

      

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

      

مسأله‌ی کاشیکاری

      

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

      

مسأله‌ی کاشیکاری

      

    اگر قطعه زمین‌های کوچکتر از ابعاد دو باشند، به سادگی با قرار دادن یک موزاییک می‌توان آن را پوشانید:

      

مسأله‌ی کاشیکاری

      

    پس به طور خلاصه، برای حل مسأله باید به این صورت عمل کنیم:

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

      

مسأله‌ی کاشیکاری

      

تعداد موزاییک‌ها

  [بازگشت به فهرست]

یکی از سوالات مهم این است که برای پوشانیدن قطعه زمین با توجه به شرایط مسأله چند موزاییک لازم است؟

    فرض کنید $ T(n) $  تعداد موزاییک‌های لازم برای پوشانیدن زمینی با ابعاد n  باشد. با توجه به استفاده از روش تقسیم و حل، هر قطعه زمین به چهار قطعه زمین با ابعاد نصف تبدیل می‌شود. اما برای این تبدیل از یک موزاییک استفاده می‌کنیم. پس می‌توان نوشت:

      

\[ T( n ) = 4 T( \frac{n}{2} ) + 1 \]

  

    اگر ابعاد قطعه زمین دو متر باشد، تنها یک موزاییک برای پوشانیدن آن کافی است:

      

\[ T( 2 ) = 1 \]

      

    پس می‌توان گفت تعداد موزاییک‌های لازم برای پوشش زمینی با ابعاد n  از رابطه‌ی بازگشتی زیر به دست می‌آید:

      

\[ T( n ) = 4 T( \frac{n}{2} ) + 1 \qquad , \qquad T( 2 ) = 1 \]

      

    با حل این رابطه‌ی بازگشتی با استفاده از روش‌های متعارف ریاضی نتیجه‌ی زیر حاصل می‌شود:

      

\[ T( n ) = \frac{n^2 - 1}{3} \]

      

    برای  محاسبه‌ی $ T(n) $  راه ساده‌تری هم وجود دارد. در داخل قطعه زمینی با ابعاد n ، تعداد n 2 خانه‌ی مربعی شکل وجود دارد. یکی از این خانه‌ها نباید پوشانیده شود. پس n 2 - 1  خانه‌ی مربعی شکل کوچک داریم که باید توسط موزاییک‌ها پوشانیده شوند. هر موزاییک نیز سه خانه‌ی مربعی شکل کوچک را پوشش می‌دهد. پس در مجموع به $ \frac{n^2 - 1}{3} $  موزاییک نیاز خواهیم داشت.


نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History) ، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        بررسی مسأله‌ی آسانسورها (Elevators) ، از سوالات مسابقات برنامه‌نویسی ACM
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels) ، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» م

سه‌شنبه، ۲۳ آذر ماه ۱۳۹۵، ساعت ۱۷:۴۰
0808080808080808080808

» د

سه‌شنبه، ۲۳ آذر ماه ۱۳۹۵، ساعت ۱۷:۳۹
0606060606060606060606060606

» حسین

چهارشنبه، ۳۱ اردیبهشت ماه ۱۳۹۳، ساعت ۰۹:۲۴
سلام
ممنون از سایت خوبتون
خیلی خوبه
اما اگه امکانش هست برنامه c++ واسه کاشی کاری رو بذارید تو سایت

» سمیه

شنبه، ۷ اردیبهشت ماه ۱۳۹۲، ساعت ۱۹:۰۸
عالی بود
لطفا کد این الگوریتم رو برام میل کنید به زبان سی پلاس پلاس

» محمد

دوشنبه، ۱۸ دی ماه ۱۳۹۱، ساعت ۱۹:۵۳
با سلام و عرض تشکّر به خاطر کار زیباتون در راه اندازی این وب سایت.
باید عرض کنم که هرچند که منابع دیگری هم برای توضیح مساله ی کاشی کاری بود؛ ولی باز هم نیاز به منابع دیگری مثل سایت شما احساس می شه.

چون که آموزش دهنده ای، بیان خاصّ خودش رو داره و ممکنه که من مطلب رو از سایت های دیگه یا جزوه ی استاد نفهمم، ولی از سایت شما بفهمم.
نمونش هم همین کاشی کاری که از اسلایدهای استادم متوجّهش نشدم، ولی از سایت شما متوجّهش شدم. در کُل می خواستم تشکّر کنم ازتون. کارتون واقعاً ارزشمنده.01 06

» sheyda

جمعه، ۱۹ خرداد ماه ۱۳۹۱، ساعت ۱۶:۲۰
060606061206060606

» محمد

چهارشنبه، ۲۳ آذر ماه ۱۳۹۰، ساعت ۱۱:۳۷
اطفآ در کد نویسی کاشی کاری بیشتر کمک کنید.کدی اگه دارید بذارید.متشکر از وب پر بار و مفیدتان

» محمدرضا

یکشنبه، ۱۹ دی ماه ۱۳۸۹، ساعت ۰۲:۴۴
عالی بود.با یک بار خوندن متوجه شدم. بی تعارف نوشتنت هم مثل بیانت شیوا و دقیقه، بهت افتخار می کنم. 08

» r.z

پنجشنبه، ۲۰ آبان ماه ۱۳۸۹، ساعت ۱۹:۱۳
سلام
خسته نباشید
ببخشید من برنامه ی کامل برای مسئله ی کاشی کاری رو میخواستم اگه میشه برام بنویسید خیلی ممنون چون خیلی بهش احتیاج دارم ممنون03

» PARISA

جمعه، ۱۰ اردیبهشت ماه ۱۳۸۹، ساعت ۱۷:۲۴
عالی بود

» masood

چهارشنبه، ۸ اردیبهشت ماه ۱۳۸۹، ساعت ۱۱:۵۲
googooli magoooliii shodeh mer30 khak too saret

» میلاد خواجوی

دوشنبه، ۲۶ بهمن ماه ۱۳۸۸، ساعت ۰۹:۲۰
الگوریتم کاشی‌کاری به صورت گرافیکی
http://www3.amherst.edu/ ~nstarr/trom/puzzle-8by8/

The M-by-N puzzle Trominos ، نیاز به ماشین مجازی جاوا
http://www3.amherst.edu/ ~nstarr/puzzle-mbyn/trominos.html

ممنون، راهنمای خیلی خوبی بود. استفاده بردیم.


دوشنبه، ۲۶ بهمن ماه ۱۳۸۸، ساعت ۰۹:۳۷
مسعود:
خواهش می کنم. خوشحالم که استفاده کردید. من هم ممنونم بابت معرفی این آدرس. [«06 »]

» بابک

سه‌شنبه، ۱۳ بهمن ماه ۱۳۸۸، ساعت ۱۲:۰۵
اگه یک کتاب جامع برای مسابقات acm  معرفی کنید خیلی خوب میشه؟


جمعه، ۱۶ بهمن ماه ۱۳۸۸، ساعت ۱۰:۳۰
مسعود:
بابک خان، انجام شد.

» shima

دوشنبه، ۱۲ بهمن ماه ۱۳۸۸، ساعت ۱۱:۰۱
mishe algoritme bazie hex o behem bedin ?!

» رویا

دوشنبه، ۵ بهمن ماه ۱۳۸۸، ساعت ۱۵:۱۱
سلام با کمال تشکر از اطلاعات مفید شما
امکان اموزش درخت avl    اضافه کردن گرهها از روی کد ان به زباتن c++ وجود دارد؟در هر چهار حالت
ضمنا قبلا از لطف شما کمال تشکر را دارم.

» بهنام

جمعه، ۱۱ دی ماه ۱۳۸۸، ساعت ۲۲:۱۲
سلااااااام . 06

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

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

بازم یک دنیا تشکر
موفق باشید


جمعه، ۱۱ دی ماه ۱۳۸۸، ساعت ۲۲:۴۳
مسعود:
لطف داری بهنام جان. امیدوارم بتونی از این مطلب استفاده کنی. [«01 »]
اگر هم نقص یا جای ابهامی وجود داره خوشحال می شم با من مطرح کنی. [«06 »]