3

所以，我试图在 Project Euler 上做问题 #16，如果你还没有看到的话，来自http://projecteuler.net 。如下：

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

我无法弄清楚如何在 C++ 中表示数字 2^1000。我猜这有一个技巧，但我真的被卡住了。我真的不想要这个问题的答案，我只想知道如何将该数字表示为一个变量，或者如果可能有一个技巧，也许有人可以让我知道？

4

6 回答 6

10

将其表示为字符串。这意味着您需要编写两段代码：

  1. 您需要编写一段代码来将数字加倍，给定该数字作为字符串。

  2. 您需要编写一段代码来对表示为字符串的数字的数字求和。

有了这两块，就很简单了。

于 2013-01-19T00:16:12.710 回答
8

对于这个问题，一个值得了解的好算法：

2^1 = 2
2^2 = 2 x 2 = 2 + 2
2^3 = 2 x (2 x 2) = (2 + 2) + (2 + 2)
2^4 = 2 x [2 x ( 2 x 2)] = [(2 + 2) + (2 + 2)] + [(2 + 2) + (2 + 2)]

因此，我们有一个recursive定义，用于根据操作计算 2 的幂addition：just add together two of the previous power of two.

这个链接很好地解决了这个问题。

于 2013-01-19T00:30:44.893 回答
2

这是一个完整的程序。数字保存在一个向量中。

#include <iostream>
#include <numeric>
#include <ostream>
#include <vector>

int main()
{
    std::vector<unsigned int> digits;
    digits.push_back(1);        // 2 ** 0 = 1

    const int limit = 1000;
    for (int i = 0; i != limit; ++i)
    {
        // Invariant: digits holds the individual digits of the number 2 ** i

        unsigned int carry = 0;
        for (auto iter = digits.begin(); iter != digits.end(); ++iter)
        {
            unsigned int d = *iter;
            d = 2 * d + carry;
            carry = d / 10;
            d = d % 10;
            *iter = d;
        }
        if (carry != 0)
        {
            digits.push_back(carry);
        }
    }

    unsigned int sum = std::accumulate(digits.cbegin(), digits.cend(), 0U);
    std::cout << sum << std::endl;

    return 0;
}
于 2013-01-19T02:56:10.687 回答
1

这个问题的重点是想出一种方法来做到这一点，而无需实际计算 2^1000。

但是，如果您确实想计算 2^1000（这可能是个好主意，因为这是测试您的其他算法是否正确的好方法），您将需要某种“bignum”库，例如gmp：

mpz_t two_to_1000;
mpz_ui_pow_ui(two_to_1000, 2, 1000);

或者，您可以使用C++ 接口来gmp. 它不做幂运算，所以第一部分变得稍微复杂而不是更少，但它使数字求和更简单：

mpz_class two_to_1000;
mpz_ui_pow_ui(two_to_1000.get_mpz_t(), 2, 1000);
mpz_class digitsum(0);
while (two_to_1000) {
    digitsum += two_to_1000 % 10;
    two_to_1000 /= 10;
}

（实际上没有理由在那里做digitsum，mpz所以你可能想弄清楚如何证明结果适合 32 位，将其添加为注释，然后使用longfor digitsum。）

话虽如此，我可能不会编写这段gmp代码来测试它，因为整个事情都是 Python 中的单行代码：

 print(sum(map(int, str(2**1000))))

而且，即使将 bignum 转换为字符串以将每个数字转换为 int 来总结它们可能是解决它的最不有效的方法，但在我这里最慢的机器上它仍然需要不到 200us。确实没有理由双重检查需要与实际解决方案使用相同的语言。

于 2013-01-19T01:17:07.310 回答
-1

您需要一个 1000 位机器整数来表示 2^1000；我从来没有听说过有这样的机器。但是周围有很多大整数包，它们根据需要对尽可能多的机器字进行算术运算。最简单的解决方案可能是使用其中之一。（尽管考虑到您需要的特定操作，但正如 David Schwartz 建议的那样，对字符串进行算术运算可能是合适的。在一般情况下，这不是一个好主意，但因为您所做的只是乘以 2，然后取小数位数，它可能会很好。）

于 2013-01-19T01:00:12.090 回答
-1

因为 2^10 大约是 10^3，并且 2^1000 = (2^10)^100 = (10^3)​​^100 = 10^300（大约）。所以分配一个数组

char digits[ 300 ]; // may be too few

并在每个字符中存储 0 .. 9 之间的值。

于 2013-01-19T01:04:12.293 回答