Java中的Euler项目＃8

Question

挑战在这里列出：

1000位数字中乘积最大的四个相邻数字为9×9×8×9 = 5832。

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

查找1000位数字中具有最大乘积的13位相邻数字。该产品的价值是什么？

我已经编写了与给定4位数字示例兼容的代码，但不适用于13位数字。我怀疑存在某种类型的数据溢出，但是我不确定。我的超级低效率代码如下。

public class Euler8 {
    public static void main(String[]args){
        String num = "/*number listed above*/";
        int n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13;
        long sum=0, newSum;
        for(int n=0; n<=987; n++){
            n1=Character.getNumericValue(num.charAt(n));
            n2=Character.getNumericValue(num.charAt(n+1));
            n3=Character.getNumericValue(num.charAt(n+2));
            n4=Character.getNumericValue(num.charAt(n+3));
            n5=Character.getNumericValue(num.charAt(n+4));
            n6=Character.getNumericValue(num.charAt(n+5));
            n7=Character.getNumericValue(num.charAt(n+6));
            n8=Character.getNumericValue(num.charAt(n+7));
            n9=Character.getNumericValue(num.charAt(n+8));
            n10=Character.getNumericValue(num.charAt(n+9));
            n11=Character.getNumericValue(num.charAt(n+10));
            n12=Character.getNumericValue(num.charAt(n+11));
            n13=Character.getNumericValue(num.charAt(n+12));
            newSum= (long)(n1*n2*n3*n4*n5*n6*n7*n8*n9*n10*n11*n12*n13);
            if(newSum>=sum)
                sum=newSum;
        }
        System.out.println(sum);
    } 
}

我的代码输出此号码：

2091059712

Answer 1

您的代码对long进行强制转换为时已晚：在执行强制转换时，乘法已经以32位整数完成，可以预料会引起溢出。

如下更改代码以解决问题：

// newSum should be called newProd, because you use multiplication, not addition
newSum= ((long)n1)*n2*n3*n4*n5*n6*n7*n8*n9*n10*n11*n12*n13;

[请注意，您的算法不是最有效的：如果观察到位置i+1 .. i+13的乘积可以从位置i ... [C0的乘积中计算出]，则可以快13倍。 ]，方法是将i+12处的值除以i处的值。

当然，您必须小心不要被零除。您可以通过观察到任何时候遇到零为零来解决此问题，接下来的13个乘积将全部为零，因此您可以直接跳过它们，然后转到下一个非零的“序列”。

Answer 2

问题是i+13溢出是因为：

• 它们都是n1*n2*n3*n4*n5*n6*n7*n8*n9*n10*n11*n12*n13变量，和
• int乘以int得出int。

int的大小写适用于整个产品，并且（因此）发生得太晚了，以至于无法使用long算术完成计算并避免了溢出问题。

对该特定问题的简单解决方案是将long变量声明为n。 @dasblinkelights的代码（广播long）可能会更快...但是您需要对其进行基准测试以确保。还有比这更有意义的优化。