بناء مستطيل من حجم nx2 مع أحجار الدومينو و على شكل حرف L trominos [مكررة]

Question

هذا السؤال سبق الجواب هنا:

الدومينو و Tromino جنبا إلى جنب تبليط (1 إجابة)

مغلقة منذ 4 أشهر.

السؤال هو من DP تبليط أ 2xN البلاط مع L شكل البلاط 2x1 البلاط ؟ أريد تفسير عن هذا السؤال أو نظرية

Answer 1

• دع $ f [m] $ يكون عدد الطرق لتغطية الشكل الموضح أدناه، $ m $ بواسطة $ 2 $ مستطيل. هدفنا النهائي هو $ f [n] $ .

giveacodicetagpre.

• دع $ g [m] $ يكون عدد الطرق لتغطية الشكل الأول المعروض أدناه، $ m $ بواسطة $ 2 $ مستطيل مع مربع 1x1 إضافي في الزاوية العلوية اليمنى. بالتناظر، $ g [m] $ هو أيضا عدد الطرق لتغطية الشكل الثاني الموضح أدناه.

giveacodicetagpre.

للعثور على علاقة تكرار، حاول تغطية المساحة في أقصى الحدود للأشكال المذكورة أعلاه بكل الطرق الممكنة.

النظر في $ f [m] $ . لدينا 4 طرق التالية لتغطية مساحة أقصى اليمين.

giveacodicetagpre.

لذلك، لدينا $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ for $ m \ ge2 $ .

النظر في $ g [m] $ . لدينا 2 طرق التالية لتغطية مساحة أقصى اليمين الشكل الأول.

giveacodicetagpre.

لذلك لدينا $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ for $ m \ ge1 $ .

تطبيق معادلات التكرار أعلاه، يمكننا حساب جميع $ f [m] $ و $ g [m] $ ، من أجل زيادة $ m $ ، بدءا من $ m= 2 $ ، بالنظر إلى الشروط الأولية، $ f [0]= 1 $ ، $ f [1]= 1 $ ، $ g [0]= 0 $ و $ g [1]= 1 $ . giveacodicetagpre.

---

هنا طريقة لاستقبال علاقة تكرار أبسط تتضمن $ f $ فقط.

href="https://cs.stackexchange.com/a/1126239"> إجابة Glorfidel's يشرح كيفية حساب عدد الأنماط عن طريق "قطع كتلة أقصى اليمين." إلى RECAP، هناك كتلة ابتدائية واحدة من الحجم $ 1 \ Times2 $ ، كتلة ابتدائية واحدة من $ 2 \ Times2 $ واثنين من الكتل الابتدائية من $ n \ times2 $ for $ n \ ge3 $ . دع $ f (n) $ يكون عدد أنماط $ 2 \ مرات N $ . لدينا الحالات الأساسية التالية وعلاقة تكرار، $$ F (0)= 1، \ f (1)= 1، \ f (2)= 2، $ $$ f (n)= f (n-1) + f (n-2) + 2f (n-3) + 2f (n-4) + \ cdots + 2f ( 0)، \ text {for} n \ ge3 $$

الصيغ أعلاه يؤدي إلى خوارزمية تقوم بتحسين $ f (n) $ مع $ o (n ^ 2) $ تعقيد الوقت و $ O (n) $ تعقيد الفضاء.

يمكننا أن نفعل أفضل. استبدال $ n $ مع $ N-1 $ ، لدينا $$ f (n-1)= f (n-2) + f (n-3) + 2f (n-4) + 2f (n-5) + \ cdots + 2F (0)، \ text {for} n \ ge4 $$

طرح المعادلات المذكورة أعلاه، نحصل $$ f (n) -f (n-1)= f (n-1) + f (n-3) $ لذلك لدينا ل $ n \ ge4 $ ، $$ f (n)= 2f (n-1) + f (n-3) \ tag {simple} $ منذ $ F (3)= 5= 2F (2) + f (0) $ ، تعقد العلاقة المتكررة أعلاه لجميع $ n \ ge3 $ . يؤدي هذا إلى وجود خوارزمية يحسب $ f (n) $ مع $ O (n) $ time- تعقيد و $ O (1) $ تعقيد الفضاء.

giveacodicetagpre.

---

يمكننا أيضا أن نستمد العلاقة المتكررة البسيطة مباشرة من أول علاقات متبادلة متبادلة بين $ f $ و $ g $ .

المساواة $ g [m]= f [m - 1] + g [m-1] $ أخبرنا $ f [m-1]= g [m] -g [m-1] $ ، ومن ثم، $ f [m]= g [m + 1] -g [m] $ و $ f [m-2]= g [m-1] -g [m-2] $ . تطبيقها على القضاء على $ f $ بعيدا في $ f [m]= f [m - 1] + f [m - 2] + G [M - 2] \ CDOT 2 $ ، نحصل على $ g [m + 1]= 2g [m] + g [m-2] $ .

منذ $ f [m] $ هو مزيج خطي من $ g [m + 1] $ و $ g [m] $ ، $ f $ مضايق

وفاق نفس النوع من العلاقة المتكررة، أي، $ f [m]= 2F [m-1] + f [m-3] $ .التحقق من النطاق الصالح للفهرس $ M $ ، ونحن نرى أنه قيمة لجميع $ m \ ge3 $ .

Answer 2

طريقة واحدة للتفكير في أنه سيكون الابتدائية بنات ، أيالكتل التي لا يمكن تقسيم بالقص عموديا.

• هناك واحد الابتدائية كتلة من حجم 1x2 (واحد عمودي ب).
• هناك واحد الابتدائية كتلة من حجم 2x2 (اثنين الأفقي Bs).
• هناك نوعان الابتدائية كتل من حجم 3x2 (الأخيرين هو مبين في الشكل الخاص بك, على سبيل المثال أنا).
• هناك نوعان الابتدائية كتل من حجم 4x2 (كلاهما تظهر في النهائي نمط المثال الثاني).
• بشكل عام, هناك نوعان من الابتدائية كتل من حجم $n \مرات 2$, $n \قه 3$.

الآن ، $n \مرات 2$ مستطيل يمكن تقسيمها إلى اثنين من كتل أصغر طريق قطع اليمين الابتدائية كتلة.(وهذا يشمل حال الابتدائية كتلة كامل المستطيل).

• 0x2 مستطيل يمكن القرميد في 1 طريقة.
• من 1x2 مستطيل ، يمكننا قطع اليمين الابتدائية كتلة (لدينا 1 منهم) نحن مع اليسار 0x2 مستطيل ، لذلك يمكن أن يكون البلاط في 1 طريقة.
• من 2x2 مستطيل ، يمكننا إما قطع 2 × 2 بلوك (1) ، أو قطع 1x2 كتلة يكون تركت مع 1x2 المستطيل (1 * 1 = 1 طريقة), مجموعه 2 طرق.
• من 3x2 المستطيل:
  • قطع 3x2 كتلة (2 طرق)
  • قطع 2x2 بلوك (1) وكان يكون تركت مع 1x2 المستطيل (1) ،
  • قطع 1x2 بلوك (1) وكان مع 2x2 المستطيل (2 طرق)
  • المجموع:2 + 1 * 1 + 1 * 2 = 5 طرق.

بهذه الطريقة, يمكنك العمل على طول الطريق إلى 10x2.

بعد الحوسبة بعض المصطلحات وجدت تسلسل A052980 في موسوعة صحيح متواليات:

a(n) هو عدد ممكن tilings من 2 X n المجلس ، وذلك باستخدام أحجار الدومينو و على شكل حرف L trominos.- مايكل Tulskikh, Aug 21 2019

لذلك الجواب النهائي هو 1255 بالنسبة $n=10$.