پاسخ : مسئله قورباغه
با سلام
ما باید تعداد راه های حرکت روی 8 ضلعی به شرطی که قبل از مرحله 2nبه ضلع 5 نرسیده باشیم رو به دست بیاریم
خوب پس 8 ضلعی رو باز میکنیم و ضلع 5 رو از اون حذف میکنیم
خواهیم داشت 6 7 8 1 2 3 4 و 4 تابع بازگشتی تعریف میکنیم
fn = تعداد راه های رسیدن به راس 4 یا 6 بعد از n ثانیه
gn = تعداد راه های رسیدن به راس 3 یا 7 بعد از n ثانیه
tn = تعداد راه های رسیدن به راس 2 یا 8 بعد از n ثانیه
kn = تعداد راه های رسیدن به راس 1 بعد از n ثانیه
و واضح است که جواب مساله برابر f2n-1 خواهد بود زیرا اگر تعداد راه های رسیدن به راس 4 یا 6 را بعد از 2n-1 مرحله به دست آوریم در مرحله ی بعد به صورت یکتا به راس 5 میرویم حال هر یک از توابع را حساب میکنیم:
fn = gn-1
gn = fn-1 + tn-1
tn = gn-1 + kn-1
kn = tn-1
حال میتوان توابع را ساده کرد و به جواب رسید در ضمن مقادیر اولیه توابع هم به عهده ی خود شما
