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

سلام دوستان
لطفا راهنماییم کنید:
فرض کنید (h(n تعداد اعداد n رقمی با ارقام 1،2،3،4،5 باشد بطوریکه هردو رقم مجاور در این اعداد برابر باشند یا حداقل یکی از این دو برابر 1 باشد، در اینصورت رابطه بازگشتی آن معادل با کدام گزینه است؟

1) (h(n) = 3h(n-1) + 2h(n-2
2) (h(n) = 2h(n-1) + 3h(n-2
3) (h(n) = 3h(n-1) + 3h(n-2
4) (h(n) = 2h(n-1) + 2h(n-2

جواب گزینه 2.
[/code]

سلام. درنظر بگیرید An تعداد اعداد بطول n هستن که شرط مسئله رو دارن و به 1 ختم میشن و Bn هم همین رشته ها که به 2و3و4و5 ختم میشن. Hn هم تمام رشته های بطول n باشه. داریم:

[tex]A_n=A_{n-1} B_{n-1}=H_{n-1}[/tex]
[tex]B_n=4A_{n-1} B_{n-1}[/tex]
[tex]H_n=A_n B_n=5A_{n-1} 2B_{n-1}=2(A_{n-1} B_{n-1}) 3A_{n-1}=2H_{n-1} 3H_{n-2}[/tex]