1

これは数学関連の質問でもありますが、C++ で実装したいと思います...そのため、フォーム2^nに数値があり、その桁の合計を計算する必要があります (基数 10;P )。私の考えは、次の式で計算することです。

sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...

すべての桁について: floor(n/floor(log2(10))).

第1項はべき乗剰余で簡単に計算できるのですが、それ以外は困っています。は大きいのでn、大きな整数ライブラリを使用したくないため、pow(2,n)モジュロなしでは計算できません。第 1 項のコード スニペット:

while (n--){
    temp = (temp << 1) % 10;
};

しかし、2番目にはわかりません。floor「0」（2/10）になるため、個別に指定することもできません。これを達成することは可能ですか？（http://www.mathblog.dk/project-euler-16/より簡単な解決策。）もちろん、この方法で実行できない場合は、他の方法を探します。（たとえば、リンクのコメントのように、数字をバイト配列に格納します）。

編集：既存の回答に感謝しますが、数学的に解決する方法を探しています。bignum や digit-vector なしで実装できる 1 つのアイデアを思いついたので、それが機能するかどうかをテストします。

したがって、合計については上記の式があります。しかし、どちらが2^n/10^kのように書くことができます。次に、小数部分とその整数部分を取り、整数部分で剰余累乗を行います。最後の反復の後、10 を法とする分数も掛けます。うまくいかない場合、または上記のアイデアのどこかが間違っている場合は、ベクトル ソリューションに固執し、答えを受け入れます。2^n/2^(log2 10^k)2^(n-k*log2 10)2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10))

編集：わかりました、非整数​​モジュロで剰余べき乗を行うことはできないようです（？）（または私はそれについて何も見つけていません）。だから、私は数字/ベクトルベースのソリューションをやっています。

コードが完全に機能しません!

適切な値が得られません: (1366 ではなく 1390):

typedef long double ldb;

ldb mod(ldb x, ldb y){             //accepts doubles
    ldb c(0);
    ldb tempx(x);
    while (tempx > y){
        tempx -= y;
        c++;
    };
    return (x - c*y);
};

int sumofdigs(unsigned short exp2){
    int s = 0;
    int nd = floor((exp2) * (log10(2.0))) + 1;
    int c = 0;
    while (true){
        ldb temp = 1.0;
        int expInt = floor(exp2 - c * log2((ldb)10.0));
        ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
        while (expInt>0){
           temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
                //floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
            expInt--;
        };
        ldb r = pow(2.0, expFrac);
        temp = (temp * r);
        temp = mod(temp,10.0);
        s += floor(temp);
        c++;
        if (c == nd) break;
    };
    return s;
};
4

3 に答える 3

2

this other question ( C++ get each digit in int ) で言及されているいくつかの手法を使用して数字のベクトルを作成し、そのベクトルを繰り返し処理してすべてを加算することができます。

于 2014-01-23T00:04:58.133 に答える
1

あなたが言及したリンクには、n <= 63 の任意の数に対してそのまま機能する答えがあります。

自分ですべてをプログラミングする必要がある場合は、2 進数の除算の計算方法と非常に大きな数の処理方法を知る必要があります。すべてをプログラムする必要がない場合は、大きな整数用のライブラリを入手して、リンクに示されているアルゴリズムを適用してください。

BigNumber big_number;
big_number = 1;
big_number <<= n;
int result = 0;
while(big_number != 0) {
    result += big_number % 10;
    big_number /= 10;
}
return result;

さて、BigNumber を実装するのは楽しいでしょう。アルゴリズムから、代入、左シフト、等しくない、モジュロ、除算が必要であることがわかります。BigNumber クラスは完全に動的であり、整数のバッファを割り当てて、大きな数を適合させることができます。また、固定サイズで記述することもできます (たとえば、テンプレートとして)。しかし、時間がない場合は、おそらくこれで十分です。

https://mattmccutchen.net/bigint/

于 2014-01-23T03:28:46.523 に答える