3

それで、私はプロジェクトオイラーで問題＃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

文字列として表現します。つまり、次の2つのコードを記述する必要があります。

  1. 数値を文字列として指定して、数値を2倍にするコードを記述する必要があります。

  2. 文字列として表される数値の桁を合計するコードを記述する必要があります。

これらの2つの部分で、それは簡単です。

于 2013-01-19T00:16:12.710 に答える
8

この問題について知っておく価値のある1つの優れたアルゴリズム：

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

2 ^ 1000を表すには、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 に答える