描述标尺长度的递归关系
Recurrence relation that describes the length of a ruler
在之前的数据结构和算法考试中，我被问到以下问题：
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
在之前的数据结构和算法考试中，我被问到以下问题：
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