项目欧拉#16 - C#2.0

Question

我一直在与C#2.0中的Project Euler Problem#16搏斗.问题的关键在于你必须计算并迭代一个长度为604位(或那里)的数字中的每个数字.然后,您将这些数字相加以产生答案.

这提出了一个问题:C#2.0 没有可以处理这种计算精度的内置数据类型.我可以使用第三方库,但这会破坏尝试以编程方式解决它而无需外部库的目的.我可以在Perl中解决它; 但是我试图在C#2.0中解决它(我将在下一次项目Euler问题的试运行中尝试使用C#3.0 ).

题

你有什么建议(不是答案!)来解决C#2.0中的项目Euler#16？有哪些方法可行？

注意:如果您决定发布答案,请在尝试前添加一个在其前面写有### Spoiler的块引用.

Answer 1

一系列数字.32位无符号整数是32位二进制数.字符串"12345"是一系列5位数字.数字可以以多种方式存储:作为位,字符,数组元素等.C#中具有完全精度的最大"本机"数据类型可能是十进制类型(128位,28-29位).只需选择自己的数字存储方法,即可存储更大的数字.

至于其余的,这会给你一个线索:

2 ¹ = 2
2 ² = 2 ¹ + 2 ¹
2 ³ = 2 ² + 2 ²

例:

The sum of digits of 2^100000 is 135178
Ran in 4875 ms

The sum of digits of 2^10000 is 13561
Ran in 51 ms

The sum of digits of 2^1000 is 1366
Ran in 2 ms

SPOILER ALERT:C#中的算法和解决方案如下.

基本上,提到一个数字只不过是一个数字数组.这可以通过两种方式轻松表示:

• 作为一个字符串;
• 作为字符或数字的数组.

正如其他人所提到的,实际上建议以相反的顺序存储数字.它使计算更容易.我尝试了上述两种方法.我发现字符串和字符算法很烦人(在C/C++中它更容易;语法在C#中简直令人讨厌).

首先要注意的是,您可以使用一个数组执行此操作.您不需要在每次迭代时分配更多存储空间.如上所述,你可以通过将之前的2的幂加倍来找到2的幂.所以你可以通过加倍1千次来找到2 ¹⁰⁰⁰.可以使用通用算法完成加倍:

carry = 0
foreach digit in array
  sum = digit + digit + carry
  if sum > 10 then
    carry = 1
    sum -= 10
  else
    carry = 0
  end if
  digit = sum
end foreach

对于使用字符串或数组,此算法基本相同.最后你只需加上数字.一个简单的实现可能会在每次迭代时将结果添加到新数组或字符串中.馊主意.真的慢了下来.如上所述,它可以在适当的位置完成.

但阵列应该有多大？那也很容易.在数学上你可以将2 ^ a转换为10 ^ f(a)其中f(a)是一个简单的对数转换,你需要的数字是从10的幂的下一个更高的整数.为简单起见,你可以使用:

digits required = ceil(power of 2 / 3)

这是一个近似和充分的近似.

你可以真正优化的地方是使用更大的数字.32位有符号int可以存储+/- 20亿之间的数字(大约9个数字等于10亿,所以你可以使用32位int(有符号或无符号)基本上是10亿"数字".你可以工作你需要多少个int,创建那个数组,这就是运行整个算法所需的所有存储空间(130个字节),所有内容都已完成.

解决方案如下(在相当粗略的C#中):

    static void problem16a()
    {
        const int limit = 1000;
        int ints = limit / 29;
        int[] number = new int[ints + 1];
        number[0] = 2;
        for (int i = 2; i <= limit; i++)
        {
            doubleNumber(number);
        }
        String text = NumberToString(number);
        Console.WriteLine(text);
        Console.WriteLine("The sum of digits of 2^" + limit + " is " + sumDigits(text));
    }

    static void doubleNumber(int[] n)
    {
        int carry = 0;
        for (int i = 0; i < n.Length; i++)
        {
            n[i] <<= 1;
            n[i] += carry;
            if (n[i] >= 1000000000)
            {
                carry = 1;
                n[i] -= 1000000000;
            }
            else
            {
                carry = 0;
            }
        }
    }

    static String NumberToString(int[] n)
    {
        int i = n.Length;
        while (i > 0 && n[--i] == 0)
            ;
        String ret = "" + n[i--];
        while (i >= 0)
        {
            ret += String.Format("{0:000000000}", n[i--]);
        }
        return ret;
    }