تالار گفتمان مانشت

به چند طریق می توان یک ستون 4*2*2 را با استفاده از آجرهای 2*1*1 ساخت؟
"این سوالم شبیه سوال قبلیم بود ولی نمیتونم این مساله رو حل کنم."

سلام. این سوال، سوال خیلی سختیه. اون سوال قبلی هم ساده نبود. اینجور سوالات رو باید عموماً با یه رابطه بازگشتی حل کنیم. ولی اگه اندازه مساله کوچیک بود روشهای ترکیبیاتی هم جواب میده. سوال قبلی رو به همین دلیل با روشهای ترکیبیاتی حل کردم. وگرنه رابطه بازگشتی اون هم خیلی سخت محاسبه میشه.
رابطه بازگشتی این مساله مشابه رابطه بازگشنی اعداد کاتالانه که جمله iام باید در جمله n-iام ضرب بشه، مقداردهی اولیش هم فرق میکنه و یه رابطه بازگشتی کمکی هم احتیاج داره.
جواب رو من ۸۱ حساب کردم ولی نوشتن راه حلش خیلی سخته. سوال رو از کجا آوردید؟

جواب سوالو دارم ،حق با شماست از طریق بازگشتی حل کرده ولی من متوجه نشدم

(07 فروردین 1395 02:54 ب.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. این سوال، سوال خیلی سختیه. اون سوال قبلی هم ساده نبود. اینجور سوالات رو باید عموماً با یه رابطه بازگشتی حل کنیم. ولی اگه اندازه مساله کوچیک بود روشهای ترکیبیاتی هم جواب میده. سوال قبلی رو به همین دلیل با روشهای ترکیبیاتی حل کردم. وگرنه رابطه بازگشتی اون هم خیلی سخت محاسبه میشه.
رابطه بازگشتی این مساله مشابه رابطه بازگشنی اعداد کاتالانه که جمله iام باید در جمله n-iام ضرب بشه، مقداردهی اولیش هم فرق میکنه و یه رابطه بازگشتی کمکی هم احتیاج داره.
جواب رو من ۸۱ حساب کردم ولی نوشتن راه حلش خیلی سخته. سوال رو از کجا آوردید؟

جواب 121 دزسته. توی مقداردهی اولیه یه اشتباهی داشتم که الآن به همین جواب رسید. ولی رابطه بازگشتیم متفاوت بود.
راه حل خیلی قشنگی بود و مساله رو خیلی ساده تر از چیزی که به نظرم میرسید حل کرد. قبول دارید که یک ستون به ارتفاع n رو اگه از بالا نگاه کنیم یکی از 7 شکل بالایی رو خواهیم دید؟
شکل سمت چپ نشون دهنده حالتیه که 4 آجر عمودی کنار هم قرار گرفتن. پس زیر اون یه ستون به ارتفاع n-2 داریم. شکلهای دوم و سوم از سمت چپ هم با قرار دادن 2 آجر افقی کنار هم ایجاد شدن. پس 2 حالت از ستون به ارتفاع n-1 داریم. 4 حالت دیگه هم از قرار دادن یک آجر افقی در کنار دو آجر عمودی حاصل شدن. حالا اگه آجر افقی رو برداریم چی میمونه؟ یک ستون به ارتفاع n که در بالای اون یه اختلاف ارتفاع داریم (یعنی یک آجر افقی در بالای اون کمه). به این حالت Tn میگیم.
رابطه بازگشتی Tn رو هم خیلی ساده بیان کرده.

توضیحاتی که دادید رو متوجه شدم ولی نمیدونم چرا گفته Tn=Sn-1+Tn-1؟ شکل مربوط به این فرمولو هم نفهمیدم

(07 فروردین 1395 10:10 ب.ظ)Jooybari نوشته شده توسط: [ -> ]رابطه بازگشتی Tn رو هم خیلی ساده بیان کرده.

(08 فروردین 1395 01:19 ق.ظ)peace2013 نوشته شده توسط: [ -> ]توضیحاتی که دادید رو متوجه شدم ولی نمیدونم چرا گفته Tn=Sn-1+Tn-1؟ شکل مربوط به این فرمولو هم نفهمیدم

(07 فروردین 1395 10:10 ب.ظ)Jooybari نوشته شده توسط: [ -> ]رابطه بازگشتی Tn رو هم خیلی ساده بیان کرده.

شکل پایینی نحوه تشکیلش رو نشون داده. Tn ستونیه که در قسمت بالایی اون یک آجر افقی کم داره. این ستون میتونه یا اضافه کردن یک آجر افقی به یک ستون کامل به ارتفاع n-1 ساخته بشه یا با یک جفت آجر عمودی به یک ستونی که خودش یک آجر افقی کم داره (یعنی اون جفت آجر عمودی روی قسمت پایین تر قرار میگیرن و قسمت بالاتر رو تشکیل میدن).