سلام دوستان
لطفا راهنماییم کنید:
فرض کنید (h(n تعداد اعداد n رقمی با ارقام ۱،۲،۳،۴،۵ باشد بطوریکه هردو رقم مجاور در این اعداد برابر باشند یا حداقل یکی از این دو برابر ۱ باشد، در اینصورت رابطه بازگشتی آن معادل با کدام گزینه است؟
۱) (h(n) = 3h(n-1) + 2h(n-2
۲) (h(n) = 2h(n-1) + 3h(n-2
۳) (h(n) = 3h(n-1) + 3h(n-2
۴) (h(n) = 2h(n-1) + 2h(n-2
جواب گزینه ۲/
[/code]
سلام. درنظر بگیرید An تعداد اعداد بطول n هستن که شرط مسئله رو دارن و به ۱ ختم میشن و Bn هم همین رشته ها که به ۲و۳و۴و۵ ختم میشن. 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]