4

我正在尝试解决 Project Euler 问题 #16，我需要对 2^1000 的所有数字求和。我已经被困在处理这么大的数字了。我的程序适用于 10^16 以下的任何数字，但后来失败了。这告诉我我的逻辑是正确的。我继续将所有变量和方法转换为 BigDecimal，但现在程序无法正常运行。它按原样编译并且没有错误；它只是不会终止。有人知道我在哪里出错了吗？

import java.math.BigDecimal;
import java.math.RoundingMode;

public class Powerdigitsum {

    private static final BigDecimal one = new BigDecimal("1");
    private static final BigDecimal ten = new BigDecimal("10");

    private static BigDecimal sumofDigits(BigDecimal n){

        BigDecimal sum = new BigDecimal("0");

        while(n.compareTo(one) == 1 || n.compareTo(one) == 0){

            sum.add(n.remainder(ten));

            n.divide(ten);

            n = n.setScale(0, RoundingMode.FLOOR);

        }

    return sum;

    }

    public static void main(String[] args) {

        final double the_number = Math.pow(2,1000);

        final double test = 15;

        final BigDecimal two_to_the_thousandth_power = new BigDecimal(test);

        System.out.println(sumofDigits(two_to_the_thousandth_power));

    }

}
4

8 回答 8

6

只要BigInteger正确使用：

BigInteger a = new BigInteger("2").pow(1000);

于 2012-12-25T10:53:29.423 回答
3

整个方法有点错误。看到这个：

private static BigInteger sumOfDigits(BigInteger n) {
    BigInteger sum = BigInteger.ZERO;
    while (n.compareTo(BigInteger.ZERO) == 1) {
        sum = sum.add(n.remainder(ten));
        n = n.divide(ten);
    }
    return sum;
}

你需要比较零，而不是一。而且您需要为 BigIntegers 和 BigDecimals 分配值，它们的方法自己什么都不做，这些类的实例是不可变的。

对于整数，通常最好使用BigInteger. 小数部分（从除法中得到）被丢弃了。

于 2012-12-25T10:52:16.257 回答
1 
final double the_number = Math.pow(2,1000);

这不起作用，因为the_number不足以获取结果。您需要将pow呼叫转换为BigInteger：

BigInteger result = new BigInteger("2").pow(1000);

但请注意..这可能需要一些时间..

于 2012-12-25T10:55:48.043 回答
1

不要使用BigDecimal(double)构造函数：它受double原始类型的限制，不能表示 2^1000。

您可以使用BigInteger. 这些方面的东西应该可以工作（可能不是最理想的，但是......）：

public static void main(final String... args)
{
    // 2^1000
    final BigInteger oneTo2000 = BigInteger.ONE.shiftLeft(1000);

    BigInteger digitSum = BigInteger.ZERO;

    // We don't want to split against the empty string, the first element would be ""
    for (final String digit: oneTo2000.toString().split("(?<=.)"))
        digitSum = digitSum.add(new BigInteger(digit));

    System.out.println(digitSum);
}
于 2012-12-25T11:01:40.480 回答
0 
import java.math.BigInteger;

public class Problem16 {
public static void main(String[] args) {

   BigInteger number2 = new BigInteger("2");   
   BigInteger number3 = new  BigInteger("0");
   number3 =number2.pow(1000);

   String str = number3.toString();
BigInteger sum = new BigInteger("0");

 for(int i=0; i<str.length(); i++)
  {
    char c= str.charAt(i); 

    int value = Character.getNumericValue(c);
    BigInteger value2 = new BigInteger(Integer.toString(value));
     sum =sum.add(value2) ; 
  }
System.out.println(sum);

}

}
于 2013-03-11T09:33:23.677 回答
0

如果您认为 BIINTEGER 在作弊和/或不想使用它/学习如何使用它，那么这个算法就是正确的选择。

想想你将如何手动计算 2^1000。您将从 2^1 开始并重复乘以 2。现在请注意，2 的幂的位数至少每 3 个幂增加 1（可能在 4 个幂之后，例如 1024 到 8192）。所以像这样制作一个锯齿状的二维数组

int a[][]= new int[1000][];
for(int i=0;i<1000;i++)
{
    a[i]= new int[1+(i/3)];
}

然后将 a[0][0] 初始化为 2。在此之后，您要编写一个 for 循环，以便从最右边的位置填充每一行。所以让两个变量“数字”和“进位”。数字是您将输入到您正在处理的行中的数字，进位是您将要进行下一次计算并添加到 2 的乘积和您要与之相乘的任何数字的数字。请注意更新数字的顺序，并在每次计算后将它们重新初始化为零。我认为最难的部分是提出 for 循环的限制，以便它适合每 3 个权力的事情。您可以通过制作一个每行递增一个的三角形锯齿状数组来简化此操作。我是这样做的。这是我的整个代码。

import java.util.*;
public class ProjectEuler16 
{
    public static void main(String[] args) 
    {
        long t1=System.currentTimeMillis();
        ProjectEuler16 obj = new ProjectEuler16();
        System.out.println(obj.bigNumHandler());
        long t2= System.currentTimeMillis();
        System.out.println(t2-t1);
    }
    int bigNumHandler()
    {
        int a[][] = new int[1000][];
        for(int i=0;i<1000;i++)
        {
            a[i]= new int[1+(i/3)];
        }
        a[0][0]=2;
        for(int i=1;i<1000;i++)
        {   
            int carry=0;
            int digit=0;
            int f=0;
            if(i%3==0)
            {
                f=1;
            }
            for(int j=a[i-1].length-1+f;j>=0;j--)
            {
                if(j==0&f==1)
                {
                    a[i][0]=carry;
                }
                else
                {
                     digit=((2*a[i-1][j-f])+carry)%10;
                     carry=((2*a[i-1][j-f])+carry)/10;
                     a[i][j]=digit;
                }
            }

        }
        int sum=0;
        for(int k=0;k<a[999].length;k++)
        {
           sum=sum+a[999][k];
        }
        return sum;
   }
}

请注意，最后一行列出了 2^1000 的数字。我认为您可以弄清楚如何对数字求和。程序用了大约 5 秒钟才得出答案。

于 2014-02-15T21:48:05.663 回答
0

解决方案：：：：

import java.math.BigInteger;

public class PR9 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BigInteger zero=BigInteger.valueOf(0);
        BigInteger ten=BigInteger.valueOf(10);
        BigInteger sum=zero;
        BigInteger a = new BigInteger("2").pow(1000);

        while(a.compareTo(zero)>0){
            sum=sum.add(a.mod(ten));
            a=a.divide(ten);
        }
        System.out.println(sum);


       }
    }

输出:::::
1366

于 2016-07-08T19:49:06.477 回答
0 
import java.math.BigInteger;

public class P16 {

    public static BigInteger digitSum(int n) {
        BigInteger sum = BigInteger.ZERO;
        BigInteger number = new BigInteger("2").pow(n);

        while (number.compareTo(BigInteger.ZERO) == 1) {
            BigInteger remainder = number.remainder(BigInteger.TEN);
            sum = sum.add(remainder);
            number = number.divide(BigInteger.TEN);
        }

        return sum;
    }

    public static void main(String[] args) {
        final double START = System.nanoTime();
        System.out.println(digitSum(Integer.parseInt(args[0])));
        final double DURATION = System.nanoTime() - START;
        System.out.println("Duration: " + DURATION / 1000000 + "ms.");
    }
}

虽然可能有一种方法可以在不使用 BigIntegers 的情况下解决这个问题，但很明显它们使代码运行得更快。我只花了大约 4 毫秒就找到了答案。

于 2017-01-08T19:09:35.690 回答