Bigintを使用せずに2 ^ 1000の合計に計算する

StackOverflow https://stackoverflow.com/questions/3236279

  •  14-09-2020
  •  | 
  •  

質問

あなたのいくつかはこの質問に気付くかもしれませんが、問題16 からhref="http://projecteule.net/" rel="nofollow noreferrer">プロジェクトeuler 。私は新しい「Bigint」機能を使って解決しました。それがどのように機能するかを理解することはできません。

BigIntを使用せずに2 ^ 1000を計算する方法を知っていますか？

役に立ちましたか？

解決

ここには、数字のリスト（または配列）を使用して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)))
.

他のヒント

この問題の最も難しい部分は計算ではありません（1から始まり、1000回は2倍になるだけです）が、答えを10進数で表示します。これを念頭に置いて、Base-1000などのBCD表現の形式で計算を実行する方が概念的に簡単に見つけることができます。その後、長い倍率を2万回実行してください。これがPythonソリューションです：

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')
.

あなたは自分自身を黙示して、バグを紹介し、潜在的に遅い解決策をもたらす可能性があります。典型的な実装は、基本2 ^ 16の数のようないくつかの高塩基を持つ、数学を手動で（1桁単位で）実行することです。

問題は本当に2 ^ 1000の基数10の変換である。一つの簡単な方法は、任意の長さのある種のBCD（バイナリ符号化10進）を実装し、BCDで2 ^ 1000を計算することである。250バイトの配列は十分です。その後、任意の長さのBCD数で* 2を実行する方法を書いて、1000回呼び出す方法を書いてください。その後、数字を抽出して収納することは簡単です。

Cなどの言語でも実装が簡単です。

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();

        }
    }
}
.

OKここに行きます：

1 << 1000
.

より深刻なメモでは、Xビット整数で保持できるほとんどが1<<x-1です。実際に1<<1000を計算するには、1000ビットプロセッサ（技術的に1001ビットですが、この時点でカウントしている）が必要です。それは引法ではないので、あなたの唯一の選択はそれをエミュレートすることです（そしてそれはBigintは何ですか）。

実際に計算するものは何もありません.2^1000 = (1000...[994]...000)[Base2]。それはもう「結果」です。

保管方法を知りたい場合は、正確な値を保存する精度はありません。そのため、BigInt、または双方向の値Math.Pow(2, 1000)のどちらかです。

編集：私はここであなたのコメントからを参照してくださいの合計を望みます。いずれかの解決策を見てください。

多くのコードを譲ることなく答えます...

1）積載文字を使用して製品を保持します

2）長い乗算を実行する（学校で行ったような）

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
.

印刷物prod

メモ帳コーディング...だから誰かがバグを見つけたらそれらを修正してください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top