5

可能重复：
数字很大的除法

我需要重载 / 运算符来处理两个 HugeInt 对象，它们被简单地定义为 30 个短裤的数组。这是家庭作业，顺便说一句，但我已经为这个问题绞尽脑汁好几天了。

我已经重载了 * 运算符：

HugeInt HugeInt::operator*(const HugeInt &op2){
HugeInt temp;
short placeProducts[hugeIntSize + 1][hugeIntSize] = {0};
short product;
int carry = 0;
int k, leftSize, rightSize, numOfSumRows;

leftSize = getDigitLength();
rightSize = op2.getDigitLength();

if(leftSize <= rightSize) {

    numOfSumRows = leftSize;

    for(int i = (hugeIntSize - 1), k = 0; k < numOfSumRows; i--, k++) {

        for(int j = (hugeIntSize - 1); j >= k; j--) {

            product = integer[i] * op2.integer[j] + carry;

            if (product > 9) {

                carry = product / 10;

                product %= 10;

            } else {

                carry = 0;
            }
            placeProducts[k][j - k] = product;
        }
    }

} else {
    numOfSumRows = rightSize;

    for(int i = (hugeIntSize - 1), k = 0; k < numOfSumRows; i--, k++) {

        for(int j = (hugeIntSize - 1); j >= k; j--) {

            product = integer[j] * op2.integer[i] + carry;

            if (product > 9) {

                carry = product / 10;

                product %= 10;

            } else {

                carry = 0;
            }
            placeProducts[k][j - k] = product;
        }
    }
}
sumProductsArray(placeProducts, numOfSumRows);

for(int i = 0; i < hugeIntSize; i++)
{
    temp.integer[i] = placeProducts[hugeIntSize][i];
}

return temp;}

但是我如何重载 / op？我的主要问题不在于 C++ 代码或语法，而在于我的算法划分。当我相乘时，我能够逐位进行。我在我的二维数组中存储每个产品（也就是上面每个数字的 1 位数字，然后使用我的进位算法在上面每个 num 的 10 位数字时间）。每次我得到新产品时，它都会向左偏移 n + 1，这会将它“乘”以所需的 10 次方。然后我只是总结所有列。

I can't for the life of me figure out how to code the long division method. Since I'm dealing with two arrays it has to be digit by digit, and I suspect it might be as easy as reversing the multiplication algorithm. Nested loops and subtraction? I would need a variable for the quotient and reminder? Is there a better method? I just need to be pointed in the right direction.

4

1 回答 1

2

在整数的计算除法中，有一些有趣的结果：

  • 分子 < 分母意味着商 = 0
  • 分子 == 分母意味着商 = 1
  • 分子 > 分母，需要长除法来确定商。

前两个条件可以通过 for 循环来满足。您可以重载小于和等于关系运算符来封装此行为。

对于长除法，您将需要乘法运算符以及重载的小于和减法运算符，以及附加数字成员函数来执行运算。

这是蛮力，但应该完成工作。

于 2012-10-13T03:17:43.410 回答