根据九连环的玩法我们可以知道，面对一个所有环都处于“下环“”的状态，如果我们想上前
n
n
n 环，那么我们首先要先上前
n
−
1
n-1
n−1 环，然后下前
n
−
2
n-2
n−2 环，然后上第
n
n
n 环，然后上前
n
−
2
n-2
n−2 环。因此，如果我们把上第
n
n
n 环所需步数记为
a
n
a_n
an ，那么数列
a
n
a_n
an满足：
a
n
=
a
n
−
1
+
2
a
n
−
2
+
1
(1)
a_n=a_{n-1}+2a_{n-2}+1\tag{1}
an=an−1+2an−2+1(1)
这里我们认为我们每次只能操作一个环，即不能同时上下前两个环
利用该递推公式编写 python 程序，可以很轻松的计算得到
a
n
=
341
a_n=341
an=341
def func(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return func(n-1) + 2*func(n-2)+1
res = func(9)
print(res)
那么如何得到
a
n
a_n
an 的通项公式呢，在广泛查阅资料后得知，
a
n
a_n
an 属于二阶线性常系数非齐次递推关系。可以通过公式计算得到。
具体计算方法可跳转到文末的参考资料
最终计算结果为
a
n
=
−
1
6
(
−
1
)
n
+
2
3
2
n
−
1
2
a_n=-\frac{1}{6}(-1)^n+\frac{2}{3}2^n-\frac{1}{2}
an=−61(−1)n+322n−21
同样得到
a
9
=
341
a_9=341
a9=341 与 python 计算结果一致。
参考资料：
百度文库–2.4 线性常系数非齐次递推关系
CSDN–python实现斐波那契数列