如何乘以两个大数字

Question

您将获得n个数字的列表L=<a_1, a_2,...a_n>.它们中的每一个都是0或+/- 2 ^k形式,0 <= k <= 30.描述并实现一个返回连续子列表的最大乘积的算法 p=a_i*a_i+1*...*a_j, 1 <= i <= j <= n.

例如,对于输入,<8 0 -4 -2 0 1>它应返回8(8或(-4)*( - 2)).

您可以使用任何标准的编程语言,可以假定列表在任何标准数据结构给出,例如int[], vector<int>,List<Integer>等.

算法的计算复杂度是多少？

Answer 1

在我的第一个回答中,我解决了OP在"乘以两个大数字"中的问题.事实证明,这个愿望只是我现在要讨论的一个更大问题的一小部分:

"我仍然没有到达我算法的最后骨架,我想知道你是否可以帮我解决这个问题."

(参见问题描述的问题)

我要做的就是解释Amnon提出的更详细的方法,所以所有的功劳都归功于他.

你必须从2的幂的整数列表中找到连续子列表的最大乘积.这个想法是:

1. 计算每个连续子列表的乘积.
2. 返回所有这些产品中最大的.

您可以通过其代表子表start和end索引.因为start=0有n-1个可能的值end,即0..n-1.这将生成从索引0开始的所有子列表.在下一次迭代中,您递增start1并重复该过程(这次,有n-2个可能的值end).这样您就可以生成所有可能的子列表.

现在,对于这些子列表中的每一个,您必须计算其元素的乘积 - 这是一种方法computeProduct(List wholeList, int startIndex, int endIndex).您可以使用内置BigInteger类(应该能够处理由您的赋值提供的输入)来避免进一步的麻烦,或尝试实现其他人所描述的更有效的乘法方式.(我会从更简单的方法开始,因为它更容易看出你的算法是否正常工作,然后首先尝试优化它.)

现在您可以迭代所有子列表并计算其元素的乘积,确定具有最大乘积的子列表应该是最简单的部分.

如果您仍然难以在两个步骤之间建立连接,请告诉我们 - 但是,当您处理问题时,请同时向我们提供您的代码草稿,以便我们不会最终逐步构建解决方案复制并粘贴它.

编辑:算法骨架

public BigInteger listingSublist(BigInteger[] biArray)
{       
    int start = 0;
    int end = biArray.length-1;
    BigInteger maximum;

    for (int i = start; i <= end; i++)
    {
        for (int j = i; j <= end; j++)
        {
            //insert logic to determine the maximum product.
            computeProduct(biArray, i, j);
        }
    }

    return maximum;                
}

public BigInteger computeProduct(BigInteger[] wholeList, int startIndex, 
                                                         int endIndex)
{
    //insert logic here to return
    //wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
    //    wholeList[endIndex]);       
}

Answer 2

我想将 Amnon 对 2 的乘方的观察与我对子列表的观察结合起来。

列表以 0 硬终止。我们可以将问题分解为找到每个子列表中最大的产品，然后找到其中的最大值。（其他人也提到过这一点）。

这是我对这篇文章的第三次修订。但3的魅力...

方法

给定一个非 0 数字列表（这需要大量思考），有 3 种子情况：

1. 该列表包含偶数个负数（可能是 0）。这是简单的情况，最佳结果是所有数字的乘积，并保证为正数。

2. 该列表包含奇数个负数，因此所有数字的乘积将为负数。要改变符号，就必须牺牲包含负数的子序列。两个子案例：

   A。牺牲从左边到最左边的负数（包括最左边的负数）的数字；或者

   b. 牺牲从右到右的数字（包括最右边的负数）。

   无论哪种情况，都返回剩余数字的乘积。恰好牺牲了一个负数，结果肯定是正数。选择 (a) 和 (b) 的获胜者。

执行

输入需要分割成以 0 分隔的子序列。如果构建驱动程序方法来循环遍历列表并挑选出非 0 序列的开头和结尾，则可以就地处理该列表。

以长整型进行数学计算只会使可能的范围加倍。转换为 log2 使大型乘积的算术变得更容易。它可以防止程序在大数序列上失败。或者，也可以在 Bignum 中完成所有数学运算，但这可能会表现不佳。

最后，最终结果仍然是一个 log2 数字，需要转换为可打印的形式。Bignum 在那里派上用场。有new BigInteger("2").pow(log);2 的 次方 log。

复杂

该算法按顺序处理子列表，仅对每个子列表处理一次。在每个子列表中，都有将输入转换为 log2 并将结果转换回来的烦人的工作，但工作量与列表的大小呈线性关系。在最坏的情况下，列表中大部分内容的总和会被计算两次，但这也是线性复杂度。