解决递归递归
解决递归递归
提问于 2013-04-17 03:30:05
好吧，我正在努力学习Knuth的具体数学，还有一些我还不理解的例子。
J(n) = 2*J(n/2) -1
它来自第一章。具体来说，它为那些可能熟悉具体数学的人解决了Josephus问题。给出了一个解决方案，但绝对没有解释。我试着用迭代法来解决它。到目前为止，我想出了以下方法
J(n) = (2^k)*J(n/ (2^k )) -(2^k- 1)
而我却被困在这里。任何帮助或提示都将不胜感激。
回答 2
Stack Overflow用户
发布于 2013-04-17 11:10:43
从几个简单的例子开始，猜测，然后使用归纳来证明你的猜测。
考虑n= 2的某个幂。
J(2^0) =1(给定)
J(2^1) = 2J(2^0) -1=1
J(2^2) = 2J(2^1) -1=1
好的，让我们猜测对于所有n个>= 1，J(n) =1。
基本情况: J(1) = 1，根据定义这是真的。
归纳步骤:假设对任意k有J(k) = 1，则J(2k) = 2J(k) -1=1。
因此，通过归纳，对于所有n，J(n) =1(假设除法向下舍入为整数)。
Stack Overflow用户
发布于 2013-06-03 22:40:33
J(n)=2*J(n/2)-1
J(n)-1=2*J(n/2)-2
J(n)-1=2*(J(n/2)-1)
T(n)=2*T(n/2)，其中T(n)=J(n)-1
T(n)=2^log2(n)*T(1)
J(n)=2^log2(n)*(J(1)-1)+1
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16045494
复制相关文章
相似问题
腾讯云开发者
