UC知道汉诺塔问题求助谢谢
来源：百度知道 编辑：UC知道 时间：2024/06/21 10:53:44
求助 关于汉诺塔公式的推导证明有些没看懂...
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
可得a[i]= 2^i-1; ;<-------这步是怎么得来的?这个式子.
那位能帮忙讲解下 先谢谢了....^_^
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
可得a[i]= 2^i-1; ;<-------这步是怎么得来的?这个式子.
那位能帮忙讲解下 先谢谢了....^_^
最简单的方法就是迭代:
a[n] = a[n-1] * 2 + 1; 这是一个递推公式，说的是相邻两项之间的关系。
a1=1； (2^1-1;)
a2=a1*2+1=3； （=2^2-1;）
a3=a2*2+1=7； (=2^3-1;)
a4=a3*2+1=15； (=2^4-1;)
......
由以上关系，容易看出：a[i]=2^i-1;
楼上所说的就是迭代.这种简单的递推关系可以用迭代.稍微复杂点的递推关系有公式可以得到,例如斐波那契数
a[n] = a[n-1] * 2 + 1; 这是一个递推公式，说的是相邻两项之间的关系。
a1=1； (2^1-1;)
a2=a1*2+1=3； （=2^2-1;）
a3=a2*2+1=7； (=2^3-1;)
a4=a3*2+1=15； (=2^4-1;)
......
由以上关系，容易看出：a[i]=2^i-1;
这也是可以证明的，怎么证明你自己想想吧。归纳法。