展开方法:当n = 0且2T(n-1)+ 1时,T(n)= 1

问题描述 投票:0回答:1

对于

  • 当n = 0时,T(n)= 1
  • 否则T(n)= 2T(n-1)+ 1

我知道我们应该寻找模式并理解问题,直到我们开始用不同的变量转换方程。然而,一旦我到达那里,我不明白它是如何完成的以及为什么某些事情已经完成。

我的问题是我们用2i·T(n-1)用n代替i。但是,完整的解释也很有用!

algorithm math recurrence
1个回答
0
投票

它与9999910相同的方式是10000010 - 1,1111112是1000002 - 1。

有两种方法可以解决这个问题。一个是从一些任意的n向后工作,你的描述已经涵盖了。我发现另一种有用的方法是从零开始,直到n:

  • T(0)= 1
  • T(1)= 1 << 1 + 1 = 3
  • T(2)= 3 << 1 + 1 = 7
  • ...

这里的<<是二进制数的“左移”运算符,相当于乘以2.该运算符在许多编程语言中相当常见。它有助于表明您只需在每一步添加1位。回到第一个断言,n个连续的1位相当于2n + 1 - 1。

你问题中的解释只是使用i作为从1到n的计数器。除了步数计数器之外,它不是等式的一部分。在最后一步中,i = n,因此您可能会对转换感到困惑。

© www.soinside.com 2019 - 2024. All rights reserved.