时间戳

首页 > 解决方案 > JavaScript中的增量正确性递归算法

javascript - JavaScript中的增量正确性递归算法

问题描述

使用递归算法递增自然数的伪代码如下所示（来自 Steven S. Skiena 的算法设计手册的示例）：

Increment(y)
 if y = 0 then return(1) else
  if (y mod 2) = 1 then
      return(2 * Increment(y/2))
  else return(y + 1)

我在这里用 JavaScript 实现了它：https ://repl.it/@danielmai/IncrementalNaturalNumbers

function increment(y) {
  if(y == 0) return 1
  if(y % 2 == 1) {
    return 2 * increment(y / 2)
  }
  else return y + 1
}

它不适用于奇数。我发现 JavaScript 会将 0.5 或更高的数字四舍五入，所以如果y是奇数，它将增加两次，即5 -> 7.

我可以用Math.floor(y/2)它来四舍五入，但我认为这个函数应该不管向上还是向下舍入都可以工作。所以我的问题是，有没有办法在不使用 JS 的情况下纠正这个递归函数Math.floor？

标签： javascriptalgorithmmath

解决方案

这与 javascript 将数字向上舍入 0.5 或更高无关。

您的增量函数假设 x / 2 将返回一个整数，但在 javascript 中，这将在奇数时给出一个十进制数。因此，在执行增量（3）时，您正在递归调用增量（1.5）。由于 1.5 % 2 = 1.5，它不是 == 1，所以它最终返回 2.5。所以最后，你最终会返回 2.5 * 2 = 5。

这个函数确实适用于 c++，如果你使用整数，除法将修剪尾随小数。但是，在 javascript 中，加法 +、减法 -、乘法 *、除法 /、幂 ** 和模 % 都将 JavaScript 中的数字视为双精度数。只有二​​元运算符将 JavaScript 中的数字视为带符号的 32 位整数。

推荐阅读