6

你们中的一些人可能会注意到这个问题是Project Euler的问题 16。我已经使用 C# 4.0 的新“bigInt”特性解决了这个问题，该特性相当简单，但也没有真正学习我应该学习的一切。我假设因为它是 2 ^ 1000，所以会有某种位移解决方案，但我无法弄清楚它究竟是如何工作的。

有人知道不使用 bigint 计算 2^1000 的方法吗？

4

8 回答 8

3

The hardest part of this problem is not the computation (just start with 1 and double it 1000 times), but displaying the answer in decimal. With this in mind, you might find it conceptually easier to perform the computation in some form of BCD representation, such as base-1000. Then perform long multiplication by 2 a thousand times. Here's a Python solution:

def mul2(n):
    result = []
    carry = 0
    for i in n:
        i = i * 2 + carry
        carry = 0 if i < 1000 else 1
        result.append(i % 1000)
    if carry: result.append(1)
    return result

n = [1]
for _ in range(1000):
    n = mul2(n)

print ''.join('{0:03}'.format(i) for i in reversed(n)).lstrip('0')
于 2010-07-13T10:59:56.867 回答
2

这是在python中使用数字列表（或数组）的一种相当幼稚的方法

digits = [1]
for n in range(1000):
    newdigits = []
    carry = 0
    for digit in digits:
        s = 2*digit+carry
        carry = s/10
        s = s%10
        newdigits.append(s)
    if carry:
        newdigits.append(carry)
    digits = newdigits
print "".join(map(str,reversed(digits)))
于 2010-07-13T10:54:25.287 回答
1

您可以自己实现 BigInt，可能会引入错误并可能导致解决方案速度慢得多。一个典型的实现是自己手动执行数学运算（基于每个数字），具有一些高基数，例如基数 2^16 数字。

于 2010-07-13T10:40:55.950 回答
1

The problem is really conversion of 2^1000 to base 10. One easy way could be to implement some kind of BCD (Binary Coded Decimal) of arbitrary length and compute 2^1000 in BCD. An array of 250 bytes would be more than enough. Then you just have to write the method to perform *2 on a BCD number of arbitrary length and call it 1000 times). Then extracting and suming the digits is easy.

That's very easy to implement even in languages such as C.

于 2010-07-13T11:01:21.950 回答
1 
class Program
{
    static void Main(string[] args)
    {
        double sum=0;
        for (int i = 1000; i <=1000; i++)
        {
            double pow = Math.Pow(2, i);
            string power = pow.ToString();
            for (int j = 0; j < power.Length; j++)
            {
                 sum = sum+pow % 10;
                 StringBuilder t = new StringBuilder(pow.ToString());
                 int len = t.Length;
                 if (len != 1)
                 {
                     t.Remove(len - 1, 1);
                 }
                 pow = Convert.ToDouble(t.ToString());
            }
             Console.WriteLine(sum);
                Console.WriteLine();

        }
    }
}
于 2012-07-26T12:11:00.027 回答
0

好的，这里是：

1 << 1000

更严肃地说，您可以在 x 位整数中保存的最大值是1<<x-1. 要实际计算1<<1000，您需要一个 1000 位处理器（技术上是 1001 位，但此时谁在计算）。由于这不可行，您唯一的选择就是模仿它（这就是 bigint 所做的）。

于 2010-07-13T10:45:12.743 回答
0

实际上没有什么可计算的：2^1000 = (1000...[994]...000)[Base2]. 这已经是一个“结果”了。

如果您想知道如何存储它，您的机器没有存储其确切值的精度。所以它要么是 a BigInt，要么是双重近似值Math.Pow(2, 1000)。

编辑：我现在从评论中看到你只想要数字的总和。查看其中一种解决方案。

于 2010-07-13T10:57:05.287 回答
0

I'll try and answer without giving away much code...

1) Use a String to hold the Product

2) Perform Long Multiplication (like you did in school)

Prod = "1"
for n = 1 to 1000
        carry = 0
        newprod = ""
        for i = strlen(prod) - 1 to 0 step - 1
                digit = int(prod[i])
                p = digit * 2 + carry
                newprod = (p % 10) & newprod // append
                carry = p / 10
        next
        if( carry > 0) newprod = carry & newprod
        prod = newprod
next

print prod

Notepad-Coding here...so if anyone finds bugs please correct them.

于 2010-07-13T11:03:55.537 回答