从另一个方向下手的话.. 假设 c_n 是长度n, 结尾为1,2,3之一的数的个数 d_n 是长度n, 结尾为0的数的个数 得 a_n = c_n + d_n, c_1 = 3, d_1 = 1 c_n = 3c_{n-1} + 2d_{n-1} //c可以再接1,2,3 d只能接1,2 d_n = c_{n-1} + d_{n-1} //结尾接0 然後...想办法化简\囧/ d_n = c_{n-1} + d_{n-1} = a_{n-1} c_n = 3(c_{n-1} + d_{n-1}) - d_{n-1} = 3a_{n-1} - a_{n-2} 最後终於 a_n = c_n + d_n = 4a_{n-1} - a_{n-2} - 以上绕了一圈 对不起 从比较数学的想法的话... a_n 是长度 n 且 0 後面不接 3 的数的个数 所以 a_n = 4a_{n-1} - a_{n-2} 不管前一个结尾是什麽 但是0後面的不能接3 总之0,1,2,3全部乱接 所以就是扣掉长度n-2的接0 如果有学程式的话,可以多看一些Dynamic Programming的问题帮助思考 不过写程式很多情况下是直接分 case 讨论...有时候不容易化成简单的递回式 ※ 引述《metalalive (想玩音乐)》之铭言： : Let a_n be the number of n-digit quaternary {0,1,2,3} sequances : in which there is never a 3 immediately to the right of a 0 : find a recurrence relation for a_n : 这题是说 0後面不可以接3 : ex. : 033 <--- invalid : 013 <--- valid : 这样对吗? : 如果是 : 不知道这题要怎麽思考它的情况 @@ : 感激不尽 : 对递回的观念真的非常弱 : 常常题目条件一变换就解不出来了 : 不知有无有效的练习方式? : 谢谢 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.34.87