6

お気づきかもしれませんが、この質問はProject Eulerの問題 16です。C# 4.0 の新しい "bigInt" 機能を使用して解決しましたが、これはかなり単純でしたが、必要なすべてを実際に学習しているわけではありません。2 ^ 1000 であるため、何らかのビット シフト ソリューションがあると想定していますが、それがどのように機能するのか正確にはわかりません。

bigint を使わずに 2^1000 を計算する方法を知っている人はいますか?

4

8 に答える 8

3

この問題の最も難しい部分は計算ではなく (1 から始めて 1000 倍にするだけです)、答えを 10 進数で表示します。これを念頭に置いて、base-1000 などの何らかの形式の BCD 表現で計算を実行する方が概念的に簡単であることに気付くかもしれません。次に、長い乗算を 2 で 1000 回実行します。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')
于 2010-07-13T10:59:56.867 に答える
2

これは、数字のリスト（または配列）を使用するだけで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)))
于 2010-07-13T10:54:25.287 に答える
1 
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();

        }
    }
}
于 2012-07-26T12:11:00.027 に答える
1

問題は実際には 2^1000 を基数 10 に変換することです。簡単な方法の 1 つは、任意の長さの BCD (Binary Coded Decimal) を実装し、BCD で 2^1000 を計算することです。250 バイトの配列で十分です。次に、任意の長さの BCD 番号に対して *2 を実行するメソッドを作成し、それを 1000 回呼び出すだけです)。次に、数字の抽出と合計は簡単です。

これは、C などの言語でも非常に簡単に実装できます。

于 2010-07-13T11:01:21.950 に答える
1

BigInt を自分で実装すると、バグが発生する可能性があり、ソリューションが大幅に遅くなる可能性があります。典型的な実装では、基数 2^16 などの高い基数を使用して、自分で (桁ごとに) 手動で計算を実行します。

于 2010-07-13T10:40:55.950 に答える
0

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

それを格納する方法を知りたい場合、マシンには正確な値を格納する精度がありません。つまりBigInt、または倍精度の近似値Math.Pow(2, 1000)です。

編集：コメントから、数字の合計だけが必要なことがわかりました。解決策の 1 つを参照してください。

于 2010-07-13T10:57:05.287 に答える
0

多くのコードを渡さずに答えてみます...

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

印刷物

Notepad-Coding here...誰かがバグを見つけたら修正してください。

于 2010-07-13T11:03:55.537 に答える
0

OKここに行きます：

1 << 1000

さらに深刻なことに、x ビット整数で保持できる最大値は1<<x-1です。実際に計算1<<1000するには、1000 ビットのプロセッサが必要です (技術的には 1001 ビットですが、現時点では誰が数えているのでしょうか)。それは実行可能ではないため、唯一の選択肢はそれをエミュレートすることです (これが bigint の機能です)。

于 2010-07-13T10:45:12.743 に答える