java - 通过重复加法进行乘法

Question

我正在尝试通过重复加法将两个数字数组相乘。所以数字 324 = [4,2,3] 乘以 24 = [4,2]。我遇到的问题是迭代 324 和 324 的加法，将其作为 [8,4,6] 保存到数组中，然后重复加法过程以获得 [8,4,6]+[4,2,3] 等等等。这是我目前所拥有的:

BigInt result = new BigInt();
BigInt temp = new BigInt();
int sum = 0;
int carry = 0;
int size = digitList.size();
int k = 0; //k is our multiplier 
for (int i = otherBigInt.digitList.size()-1; i >=0; i--) {
    k = 10 * k + otherBigInt.digitList.get(i);
}

这是我逐位执行长加法的地方。

for (int i =0; i<size;i++) {
    sum = digitList.get(i) + digitList.get(i) + carry;
    if (sum > 9) {
        temp.digitList.add(sum%10);
        carry=1;
    } else {
        temp.digitList.add(sum);
        carry=0;
    }
    if (sum > 9 && i == size-1) {
        temp.digitList.add(sum/10);
    }
}

这是我卡住的地方。我在这里要做的是将 324 添加到临时数组，然后将其答案分配给结果数组。从这里我将结果分配给临时数组，以便我可以添加到存储的结果中。 eg: digitlist = 324, temp = 324. Result = 648 --> digitList=324, temp = 648. result = 972.

我清除了结果数组，因此我可以在每次迭代中存储更新的结果。此时我得到一个 nullpointerExeption，其中 index = 0 且 size =0。

for(int i=0;i<25;i++) {
    result.digitList.clear();
    for (int j=0; j<digitList.size();j++) {
        sum = digitList.get(j) + temp.digitList.get(j) + carry;
        if (sum > 9) {
            result.digitList.add(sum%10);
            carry=1;
        } else {
            result.digitList.add(sum);
            carry=0;
        }
        if (sum > 9 && j == size-1) {
            result.digitList.add(sum/10);
        }
    }
    temp.digitList = result.digitList;
    }
    return result;
}

这是一道家庭作业题，但我已经坚持了一段时间。对于这样一个简单的任务，我要找到的解决方案似乎太复杂了，有人可以引导我朝着正确的方向前进吗？

Answer 1

如果您使用其他变量名来帮助您，可能会更容易:

BigInt input1 = new BigInt();
BigInt multiplier = new BigInt();

BigInt nextResult = new BigInt();
BigInt lastResult = null;

while ( ... notdone ... ) {
    nextResult.digitList.clear();
    if (lastResult==null) {
        lastResult = input1;
    } else {
        ... the addition logic: nextResult = lastResult + input1 ...
    }
    ... the logic to remember that one addition step was done ...

    lastResult = nextResult;
    nextResult = new BigInt();
}

lastResult 始终是上一次迭代的结果。您必须小心，不要更改 lastResult 中的数字。 lastResult 的唯一更改必须是，当您从 input1 或 nextResult 分配它时。

当您开始添加时，您的 lastResult 没有数据，因为没有“最后一次迭代”。在这种情况下，您只需使用 input1 初始化 lastResult。

nextResult 是您在加法迭代中工作并将新数字存储到的地方。迭代完成后，将其设置为 lastResult 并准备一个新的 nextResult 以供处理。 (在您的代码中，您有时会使用 temp，有时会使用 result，这会增加您的困惑。)

有趣的是，记住你已经计算了多远。例如，在第一次迭代后使用“5 x 3”，您会得到一个结果，而“3”变为“2”，因为还剩下两次迭代。或者对于“123 x 15”，“15”随着每次迭代首先减少到“14”，然后是“13”，...“10”，“9”，... a.s.o.

这与 while 条件的“...未完成...”部分有关。

这里有几个可能的优化，我不想说太多，因为那肯定是你作业的一部分。也许您应该继续构建一些代码，直到它起作用。在此过程中，您可能已经有了如何让事情变得更容易的想法。如果您尝试在纸上执行添加步骤，它也可能会有所帮助。您可能会注意到哪些部分可以更轻松地完成。 (如果你没有找到优化，别担心 - 这需要练习，有时大脑处于这种情绪中，有时不是。而且你的结果必须是正确的，它们不应该被“巧妙地优化”然后有时是错误的。 )

更新:关于变量和对象实例

您需要区分变量和它们所引用的对象。

nextResult = new BigInt();

这条语句意味着两件事:1) 您创建了一个 BigInt() 的实例和 2) 您使用 lastResult 引用了那个 BigInt。

现在声明:

lastResult = nextResult;

仍然是相同的 BigInt，但现在 lastResult 和 nextResult 都指的是相同的 BigInt .如果您更改 lastResult 中的数字，您实际上更改了 BigInt 实例中的数字。由于 nextResult 和 lastResult 引用相同的 BigInt，因此在获取数字时两者将提供相同的值。

这也意味着您不需要复制数字。他们已经在那里了。

现在这个语句创建了一个新的 BigInt 实例:

nextResult = new BigInt();

现在在这三个语句之后，nextResult 引用了一个新的 BigInt 实例，它现在不同于 中的 BigInt lastResult.