2

私はProjectEulerに取り組んでおり、次の学期に予定されているプログラミングの課題に備えて、C ++コーディングスキルを磨き上げています（Pythonを使用できないため、ブー！）。

私は＃16にいます、そして私は2¹°°°のために本当の精度を保つ方法を見つけようとしています

例えば：

int main(){
    double num = pow(2, 1000);
    printf("%.0f", num):
    return 0;
}

プリント

107150860718626732094842504906000181056140500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

（Pythonからの）ほとんどの数字が欠落しています：

>>> 2**1000

107150860718626732094842504906000181056140481170553360744375038837035105112493612249319837881569585812759467291755314682518714528569231404359845775746985748039345677748242309854210746050623711418779541821530464749835819412673987675591655439460770629145711964776865421676

確かに、Python1ライナーを使用してプログラムを作成できます

sum(int(_) for _ in str(2**1000))

それですぐに結果が得られますが、C++でそれを行う方法を見つけようとしています。ポインタはありますか？（はは...）

編集：

標準ライブラリの外にあるものは私には価値がありません-これらのコンテストではデッドツリーコードのみが許可されており、おそらく10,000行の外部コードを出力することはありません...

4

7 に答える 7

8

char配列の各桁を追跡するだけであれば、これは簡単です。桁を2倍にするのは簡単です。結果が10より大きい場合は、10を引いて、次の桁に桁上げを追加します。値1から始めて、ダブリング関数を1000回ループすると、完了です。で必要な桁数を予測することも、ceil(1000*log(2)/log(10))動的に追加することもできます。

ネタバレ注意：誰かが私を信じる前に、私はコードを示さなければならないようです。これは、DoubleとDisplayの2つの関数を持つbignumの単純な実装です。簡単にするためにクラスにしませんでした。数字はリトルエンディアン形式で格納され、最下位桁が最初になります。




typedef std::vector<char> bignum;

void Double(bignum & num)
{
    int carry = 0;
    for (bignum::iterator p = num.begin();  p != num.end();  ++p)
    {
        *p *= 2;
        *p += carry;
        carry = (*p >= 10);
        *p -= carry * 10;
    }
    if (carry != 0)
        num.push_back(carry);
}

void Display(bignum & num)
{
    for (bignum::reverse_iterator p = num.rbegin();  p != num.rend();  ++p)
        std::cout << static_cast<int>(*p);
}

int main(int argc, char* argv[])
{
    bignum num;
    num.push_back(1);
    for (int i = 0;  i < 1000;  ++i)
        Double(num);
    Display(num);
    std::cout << std::endl;
    return 0;
}
于 2010-08-02T16:22:51.300 に答える
3

このようなbignumライブラリが必要です。

于 2010-08-02T15:31:08.190 に答える
3

おそらくここにポインタが必要です（しゃれを意図しています）

C ++では、Pythonと同じように実行するために、独自のbigintlibを作成する必要があります。

于 2010-08-02T15:31:27.527 に答える
2

C / C ++は、基本的なデータ型で動作します。double1000ビットの数値を格納するために64ビットしかないを使用しています。double有効数字に51ビット、大きさに11ビットを使用します。

唯一の解決策は、他の場所で言及されているbignumのようなライブラリを使用するか、独自のライブラリを展開することです。

于 2010-08-02T15:37:03.093 に答える
2

更新：オイラー問題サイトを閲覧したところ、問題13は大きな整数の合計に関するものであることがわかりました。反復メソッドはしばらくすると非常にトリッキーになる可能性があるため、問題＃13のコードを使用することをお勧めします。これは、すでにこれを解決する必要があるためです。2**N => 2**(N-1) + 2**(N-1)

bignumsを使用することは不正行為であり、解決策ではありません。また、結果を得るために2**1000などを計算する必要はありません。ヒントをあげましょう：

2**Nの最初のいくつかの値を取ります。

0 1 2 4 8 16 32 64 128 256 ...

次に、数字ごとにその桁の合計を書き留めます。

1 2 4 8 7 5 10 11 13 ...

x~=y（ xとyの桁数が同じであることを意味します）に注意してください。

1+1=2, 1+(1+2)=4, 1+(1+2+4)=8, 1+(1+2+4+8)=16~=7 1+(1+2+4+8+7)=23~=5

次に、ループを記述します。

プロジェクトオイラー=計算する前に考えてください！

于 2010-08-02T16:07:38.250 に答える
1

この種のことを実際に実行したい場合は、任意精度の算術パッケージを探しています。NTL、リップ、GMP、MIRACLなど、さまざまなものがあります。

プロジェクトオイラーのために何かをしたい場合は、パワーを上げるための独自のコードを書くことができます。基本的な考え方は、かなりの数の小さなピースにあなたの多数を保存し、ピースの間にあなた自身のキャリー、ボローなどを実装することです。

于 2010-08-02T15:33:24.803 に答える
0

pow(2, 1000)基本的に、2つだけを1000回左シフトしているのではありませんか？ダブルフロートで正確なバイナリ表現が必要です。bignumライブラリは必要ありません。

于 2010-08-02T15:38:32.767 に答える