问答题
n位三进制数中，没有1在任何2的右边的序列的数目记为h
n
，求h
n
满足的递推关系。
【正确答案】
考虑最左边位上的情况。若此位上是1，则余下n-1位上的满足要求的三进制数数目为h
n-1
；若此位上是2，则余下n-1位上都不能出现1，满足要求的三进制数数目为2
n-1
。因此
h
n
=h
n-1
+2
n-1
h
1
=2
【答案解析】
提交答案
关闭