مبانی روابط بازگشتی
ببعییی میخواد یه راهرو رو کاشی کاری کنه، عرض راهرو 1 متره و طولش 13 متر. ببعییی 2 مدل کاشی داره یکیش 1×2 متره و یکی دیگه 1×1 متر. ببعییی به چند حالت میتونه راهرو را کاشی کاری کنه؟
بعضی وقت ها هست که پیدا کردن جواب مسئله به صورت مستقیم سخت و پیچیده میشه. خب توی این مواقع میتونیم به صورت غیر مستقیم مسائل رو حل کنیم. مثلا توی مسئله بالای صفحه، اگه ببعییی اولین کاشی ای که میذاره 1×1 باشه تعداد روش ها میشه تعداد روش های همین مسئله با فرق اینکه طول راهرو 12 متر باشه و اگه اولین کاشی 2×1 باشه تعداد روش ها دوباره میشه همین مسئله با فرق اینکه طول راهرو 11 متر باشه، پس میتونیم اول مسئله رو برای راهرویی به طول 11 متر و 12 متر حل کنیم و بعد جمع جواب هاشون میشه جواب راهرویی با طول 13 متر. (طبق اصل جمع)
حالا اگه بخوایم اینو خوشگل تر بنویسیم میتونیم An جواب مسئله در صورتی که طول راهرو n متر باشه در نظر بگیریم، اینطوری جواب اصلی مسئله میشه A13 و
An = An-1 + An-2 (n >= 2)
A0 = 1, A1 = 1
(چون اگه طول راهرو 1 باشه فقط میشه یدونه کاشی 1×1 گذاشت و اگه طول راهرو 0 باشه تنها راه اینه که کاشی نذاشت)
حالا به صورت بازگشتی جواب مسئله رو حساب میکنیم.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
رابطه بازگشتی An شبیه رابطه بازگشتی فیبوناچی عه فقط با این تفاوت که در فیبوناچی F0 برابر 0 است. برای اینکه با رابطه بازگشتی فیبوناچی آشنا بشید میتونید توی ویکیپدیا "اعداد فیبوناچی" رو جست و جو کنید.
فرض کنید an تعداد اعداد n رقمی با رقم های 1 و 2 باشد به طوری که هیچ جا دو رقم 1 در این اعداد مجاور نباشند. a13 رو بدست بیار.
بیا یه بار در نظر بگیر رقم اول 2 باشه و به بار دیگه در نظر بگیر که 1 باشه. (توی حالت دوم رقم دوم حتما باید 2 باشه)
پاسخ - 610
- یا اینکه رقم اول
2است، اینطوری بقیه عددan-1حالت داره. - یا اینکه رقم اول
1عه و اینجوری حتما باید رقم دوم2باشه و بقیه عددan-2حالت داره.
خب پس طبق اصل جمع رابطه بازگشتی برابر میشه با
an = an-1 + an-2
فقط باید حواست باشه که رابطه بازگشتی کافی نیست و باید برای رابطه بازگشتی پایه هم بنویسی (چون مثلا توی همین مسئله اگه ندونیم a0 و a1 چنده چجوری میخوایم a13 رو بدست بیاریم)
a0 = 1, a1 = 2
البته لازم نیست حتما پایه ها a0 و a1 باشند، میتونه a1 و a2 هم باشند.
حالا طبق پایه ها و رابطه بازگشتی، a13 رو حساب میکنیم.
n سکه یکسان در اختیار داریم. این سکه ها رو در یک ردیف یا دو ردیف می چینیم که در ردیف دوم هر سکه درست با دو سکه زیرش در تماس باشد. فرض کنید bn تعداد راه های چیدن این n سکه به صورت مورد نظر باشد. مثلا:
n |
شکل |
1 |
 |
2 |
 |
3 |
 |
4 |
 |
b13 رو بدست بیار.
بیا سمت چپ ترین سکه رو در نظر بگیر؛ یا اینکه روش سکه ی دیگه ای نیست یا یه سکه هست. (منظور از روش، ردیف بالا بین خودش و سکه سمت راستیش عه)
پاسخ - 233
سمت چپ ترین سکه را در نظر میگیریم. یا اینکه سکه ی دیگه ای روش نیست که اون وقت میایم این سکه رو در نظر نمیگیریم و بقیه سکه ها رو به bn-1 حالت میچینیم.
یا اینکه یک سکه روشه. توی این حالت خود سکه با اون سکه بالاییشو در نظر نمیگیریم و بقیه رو به bn-2 حالت میچینیم.
پس طبق اصل جمع bn = bn-1 + bn-2 میشه.
پایه های رابطه بازگشتی را هم که خود مسئله به عنوان مثال داده.
(برج هانوی) سه پایه و برجی از n دیسک با اندازه های دو به دو متفاوت در یکی از سه پایه در اختیار داریم. در این برج هر دیسک روی دیسکی بزرگ تر از خود قرار دارد. میخواهیم تمام این دیسک ها رو به پایه ی دیگری منتقل کنیم، به طوری که در هر مرتبه بالاترین دیسک از یک پایه رو به پایه دیگر منتقل کنیم و در ضمن هیچ گاه دیسکی رو روی دیسک با اندازه کوچک تر قرار ندهیم.
فرض کنید cn کمترین تعداد حرکت های لازم برای انتقال n دیسک به پایه ای دیگر باشد. c13 رو بدست بیاورید.
بیا مرحله ای رو در نظر بگیر که قراره بزرگ ترین دیسک رو به یک پایه دیگه منتقل کنی.
پاسخ - 8191
میایم مرحله ای رو در نظر میگیریم که قراره بزرگ ترین دیسک رو به یک پایه دیگه منتقل کنیم. توی این مرحله باید تمامی n - 1 دیسک دیگه توی یک پایه باشند پس تعداد مراحلی که تا الان انجام داده ایم cn-1 تاست. حالا یک مرحله هم برای منتقل کردن بزرگ ترین دیسک انجام میدیم و بعدش باید بقیه دیسک هارو بذاریم روی بزرگ ترین دیسک که دوباره cn-1 مرحله دیگه میخواد.
cn = 2 × cn-1 + 1
c0 = 0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n خط مستقیم در صفحه داده شده است، به طوری که هیچ دو خطی موازی نیستند و هیچ سه خطی از یک نقطه نمی گذرند. فرض کنید dn تعداد ناحیه های ایجاد شده با این خطوط در صفحه باشد.
مثلا d1 = 2, d2 = 4, d3 = 7.
d13 رو بدست بیار.
پاسخ - 92
هر خط با دقیقا n - 1 خط دیگه نقطه تقاطع دارد.
n - 1 خط از n خط صفحه رو به dn-1 ناحیه تقسیم میکنه. حالا اون یکی خط رو در نظر میگیریم؛ به خاطر اینکه هیچ دو خطی موازی نیستند و هیچ سه خطی همدیگه رو قطع نمیکنند، این خط با n - 1 خط دیگه دقیقا n - 1 نقطه تقاطع داره پس n ناحیه رو قطع میکنه و خب باعث میشه به ناحیه ها n تا اضافه بشه.
dn = dn-1 + n
d0 = 1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|