在之前的数据结构和算法考试中，我被问到以下问题:
Consider the following sequences of numbers which are the relative lengths of the subdivisions on a ruler.
Write a recurrence relation that describes the length of the ruler as a function of n and solve it.
1 (when n=1)
121 (when n=2)
1213121 (when n=3)
121312141213121 (when n=4)
我给出的答案是:
T(n)=2^(n)-1
但是，事实证明这是不正确的，我无法找到正确的答案。如果有人能够提供一些见解，那就太棒了!谢谢!
最佳答案
如果您要构建字符串本身，您可以这样表达:
S(n) := S(n-1)nS(n-1) where S(1) := 1
长度相似:
L(n) := L(n-1) + 1 + L(n-1) = 2L(n-1) + 1
递归关系是用前一项来表达的，这就是你的答案错误的原因。
https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf
关于relation - 描述尺子长度的递归关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29131771/