时间戳

首页 > 解决方案 > 这种分而治之的算法有什么作用？

algorithm - 这种分而治之的算法有什么作用？

问题描述

我敢肯定这很简单，这就是为什么我很沮丧。我在一次采访中得到了这段代码，有人问我这段代码计算了什么，复杂性是什么。我仍然很困惑。我尝试将输出写为 2 的底数，但我仍然没有找到模式。这是代码：

def mystery(n):
  if n == 0:
    return 0
  if n % 2 == 0:
    return mystery(n/2)
  else:
    return mystery(2(n-1)) + 1

我知道第二行正在测试它何时是偶数，但是，我仍然不明白这个函数的整体作用。有任何想法吗？**编辑：将 A 更改为神秘。

标签： algorithmrecursion

解决方案

假设As 应该是对 的递归调用mystery，那么：

这并不是真正的分而治之的算法。它只n是以某种迂回的方式返回 1 的二进制表示中的位数。

如果您了解n奇怪时会发生什么，就会更容易理解。然后n=2x+1对于一些x, 和mystery(n)= mystery(4x)+1= mystery(2x)+1= mystery(x)+1=mystery(floor(n/2))+1

推荐阅读