java - 在java中实现埃及算法

Question

我想在Java中递归地找到两个数字的乘法，只使用加法、减法和比较。所以，我用谷歌搜索，发现Egyptian Algorithm符合问题要求。

但是，我不确定在达到base case.

例子：

13 x  30

1  -- 30

2  -- 60

4  -- 120

8  -- 240 //we stop here because the double of 8 is larger than 13

为了找到结果，我们将left column等于 13的数字相加1+4+8，另一方面，我们将其相反的数字相加，right column即30+120+240 = 390结果。

但是现在如何以编程方式完成最后一部分？如何检查要添加的数字？我希望你们明白我的意思。只需要提示。

Answer 1

这是解决问题的伪代码：

function egyptian(left, right)
  prod := 0
  while (left > 0)
    if (left is odd)
      prod := prod + right
    left := halve(left)
    right := double(right)
  return prod

基本上，与其等到最后，不如在创建模板时检查模板的每一行并对其是否属于输出进行求和。我在我的博客上讨论了这个算法。

Answer 2

好的，我使用蛮力算法做到了。不过，这是一个 BigO-(n)。我确信有更有效的方法来实现它。目前。我正在解决这个问题。

多谢你们！

Answer 3

以相反的顺序循环遍历创建的结果

每次，如果您的乘数余数（开始等于您的乘数）大于左列中的数字，则从您的乘数中减去左列并将右列添加到您的结果（从零开始）。

Answer 4

您可能已经找到了这篇 Wikipedia文章。

看一下“分解”部分的最后一部分。你会发现你必须实现的子算法。