11

这是来自Project Euler的一个问题，并且这个问题包含一些源代码，因此请将此视为您的剧透警报，以防您有兴趣自己解决它。不鼓励分发问题的解决方案，这不是我想要的。我只需要在正确的方向上善意地推动和指导。

问题如下：

2^15 = 32768，其数字之和为 3 + 2 + 7 + 6 + 8 = 26。

2^1000的各位数字之和是多少？

我理解问题的前提和数学，但我一周前才开始练习 C#，所以我的编程充其量是不稳定的。

我知道 int、long 和 double 对于精确地保存 2^1000 的 300+（以 10 为底）数字是完全不够的，所以需要一些策略。我的策略是设置一个逐位获取数字的计算，并希望编译器能够弄清楚如何计算每个数字而不会出现溢出等错误：

using System;
using System.IO;
using System.Windows.Forms;

namespace euler016
{
    class DigitSum
    {
        // sum all the (base 10) digits of 2^powerOfTwo
        [STAThread]
        static void Main(string[] args)
        {
            int powerOfTwo = 1000;
            int sum = 0;

            // iterate through each (base 10) digit of 2^powerOfTwo, from right to left
            for (int digit = 0; Math.Pow(10, digit) < Math.Pow(2, powerOfTwo); digit++)
            {
                // add next rightmost digit to sum
                sum += (int)((Math.Pow(2, powerOfTwo) / Math.Pow(10, digit) % 10));
            }
            // write output to console, and save solution to clipboard
            Console.Write("Power of two: {0} Sum of digits: {1}\n", powerOfTwo, sum);
            Clipboard.SetText(sum.ToString());
            Console.WriteLine("Answer copied to clipboard. Press any key to exit.");
            Console.ReadKey();
        }
    }
}

它似乎对 powerOfTwo < 34 非常有效。我的计算器用完了有效数字，所以我无法测试更高的幂。但是跟踪程序，似乎没有发生溢出：计算的位数随着 powerOfTwo = 1000 的增加而逐渐增加，并且位数的总和也（平均）随着 powerOfTwo 的增加而增加。

对于我应该执行的实际计算，我得到输出：

2 的幂：1000 数字总和：1189

但 1189 不是正确答案。我的程序有什么问题？我对任何和所有建设性的批评持开放态度。

4

11 回答 11

13

要计算如此大数字的值，您不仅需要成为一名优秀的程序员，还需要成为一名优秀的数学家。这是给您的提示，有熟悉的公式 a x = e x ln a，或者如果您愿意，可以使用 a x = 10 x log a。

更具体到您的问题 2 1000找到 2 的常见（以 10 为底）对数，并将其乘以 1000；这是 10 的幂。如果你得到类似 10 53.142 (53.142 = log 2 value * 1000) 的东西——你很可能会得到——那么就是 10 53 x 10 0.142；只需评估 10 0.142，您将得到一个介于 1 和 10 之间的数字；并将其乘以 10 53，但这 10 53将没有用，因为 53 零和将仅为零。

用于 C# 中的日志计算 

Math.Log(num, base);

为了获得更高的准确性，您可以使用 Big Integer 的 Log 和 Pow 函数。

现在休息编程帮助我相信你可以从你身边得到。

于 2013-10-11T04:28:51.153 回答
9

正常int无法帮助您处理如此大的数字。甚至没有long。它们从未被设计为处理如此庞大的数字。int可以存储大约 10 位数字（精确最大值：2,147,483,647）和long大约 19 位数字（精确最大值：9,223,372,036,854,775,807）。但是，内置 Windows 计算器的快速计算告诉我2^1000有 300 多个数字。

（旁注：确切的值可以分别从int.MAX_VALUE和long.MAX_VALUE获得）

当您想要精确的数字总和时， even floatordouble类型将不起作用，因为它们只存储几位到几十位的有效数字。（7浮点数，15-16双精度数）。阅读此处了解有关浮点表示、双精度的更多信息

但是，C# 为任意精度提供了内置算法 BigInteger，这应该适合您的（测试）需求。即可以进行任意位数的算术运算（理论上当然。实际上它确实受到物理机器内存的限制，并且取决于您的 CPU 能力也需要时间）

回到你的代码，我认为问题出在这里

Math.Pow(2, powerOfTwo)

这溢出了计算。好吧，不是真的，但double正如我所说，精度并不能精确地代表结果的实际值。

于 2013-10-11T04:22:46.657 回答
2

不使用 BigInteger 类的解决方案是将每个数字存储在它自己的 int 中，然后手动进行乘法运算。

static void Problem16()
{
    int[] digits = new int[350];

    //we're doing multiplication so start with a value of 1
    digits[0] = 1;
    //2^1000 so we'll be multiplying 1000 times
    for (int i = 0; i < 1000; i++)
    {
        //run down the entire array multiplying each digit by 2
        for (int j = digits.Length - 2; j >= 0; j--)
        {
            //multiply
            digits[j] *= 2;
            //carry
            digits[j + 1] += digits[j] / 10;
            //reduce
            digits[j] %= 10;
        }
    }

    //now just collect the result
    long result = 0;
    for (int i = 0; i < digits.Length; i++)
    {
        result += digits[i];
    }

    Console.WriteLine(result);
    Console.ReadKey();
}
于 2014-01-29T00:39:50.110 回答
1

我使用了向左移位。然后转换为数组并对其元素求和。我的最终结果是 1366，不要忘记添加对 System.Numerics 的引用；

BigInteger i = 1;
         i = i << 1000;
        char[] myBigInt = i.ToString().ToCharArray();
        long sum = long.Parse(myBigInt[0].ToString());
        for (int a = 0; a < myBigInt.Length - 1; a++)
        {
            sum += long.Parse(myBigInt[a + 1].ToString());
        }
        Console.WriteLine(sum);
于 2013-10-11T05:13:09.140 回答
1

因为问题是 c# 特定的，所以使用 bigInt 可能会完成这项工作。在 java 和 python 中它也可以工作，但是在像 c 和 c++ 这样的语言中，如果该工具不可用，你必须采用一个数组并进行乘法运算。在数组中取一个大数字并将其乘以 2。这很简单，并且有助于提高您的逻辑技能。并来投影欧拉。有一个问题，你必须找到 100！您可能也想为此应用相同的逻辑。

于 2013-12-31T06:24:13.847 回答
0

尝试使用 BigInteger type， 2^100 最终会变成一个非常大的数字，甚至可以处理双倍。

于 2013-10-11T10:26:05.700 回答
0 
BigInteger bi= new BigInteger("2"); 
bi=bi.pow(1000); 
// System.out.println("Val:"+bi.toString()); 
String stringArr[]=bi.toString().split(""); 
int sum=0; 
for (String string : stringArr) 
{ if(!string.isEmpty()) sum+=Integer.parseInt(string); } 
System.out.println("Sum:"+sum);
------------------------------------------------------------------------
output :=> Sum:1366
于 2014-03-13T09:45:33.130 回答
0

这是我在JavaScript中的解决方案

(function (exponent) {
  const num = BigInt(Math.pow(2, exponent))
  let arr = num.toString().split('')
  arr.slice(arr.length - 1)
  const result = arr.reduce((r,c)=> parseInt(r)+parseInt(c))
  console.log(result)
})(1000)

于 2021-03-02T12:40:15.457 回答
-1

这不是一个严肃的答案——只是一个观察。

尽管尝试仅使用一种编程语言击败 Project Euler 是一个很好的挑战，但我相信该站点旨在进一步拓宽所有尝试它的程序员的视野。换句话说，考虑使用不同的编程语言。

该问题的 Common Lisp解决方案可能很简单

(defun sum_digits (x)
    (if (= x 0)
        0
        (+ (mod x 10) (sum_digits (truncate (/ x 10))))))

(print (sum_digits (expt 2 1000)))
于 2013-10-11T04:51:55.510 回答
-1 
 main()
 {
   char c[60];
  int k=0;
     while(k<=59)
      {
    c[k]='0';
   k++;

    }
       c[59]='2';
       int n=1;
     while(n<=999)
       {
       k=0;
     while(k<=59)
      {
        c[k]=(c[k]*2)-48;
        k++;
      } 
    k=0;
     while(k<=59)
        {
        if(c[k]>57){ c[k-1]+=1;c[k]-=10;   }
       k++;
         }
       if(c[0]>57)
        {
         k=0;
         while(k<=59)
           {
         c[k]=c[k]/2;
          k++;
           }
           printf("%s",c);
             exit(0);
           }

            n++;
            }
          printf("%s",c);
              }
于 2014-06-21T08:37:00.393 回答
-1

Python 使得使用 oneliner 计算它变得非常简单：

print sum(int(digit) for digit in str(2**1000))

或者使用地图：

print sum(map(int,str(2**1000)))
于 2014-11-06T20:35:47.333 回答