11

これは Project Euler の問題であり、この質問にはいくつかのソース コードが含まれているため、自分で解決することに興味がある場合は、ネタバレ注意を考慮してください。問題の解決策を配布することはお勧めできません。それは私が望んでいることではありません。誠意を持って、正しい方向への少しのナッジとガイダンスが必要です。

問題は次のように書かれています。

2^15 = 32768 で、その桁の合計は 3 + 2 + 7 + 6 + 8 = 26 です。

2^1000 の桁数の和は何桁ですか?

問題の前提と計算は理解していますが、C# の練習を始めてまだ 1 週間も経っていないので、私のプログラミングはせいぜい不安定です。

int、long、および double は、2^1000 の 300 桁以上 (基数 10) を正確に保持するには絶望的に不十分であることを知っているため、何らかの戦略が必要です。私の戦略は、桁を 1 つずつ取得する計算を設定し、コンパイラがオーバーフローのようなエラーなしで各桁を計算する方法を見つけられることを期待することでした。

using System;
using System.IO;
using System.Windows.Forms;

namespace euler016
{
    class DigitSum
    {
        // sum all the (base 10) digits of 2^powerOfTwo
        [STAThread]
        static void Main(string[] args)
        {
            int powerOfTwo = 1000;
            int sum = 0;

            // iterate through each (base 10) digit of 2^powerOfTwo, from right to left
            for (int digit = 0; Math.Pow(10, digit) < Math.Pow(2, powerOfTwo); digit++)
            {
                // add next rightmost digit to sum
                sum += (int)((Math.Pow(2, powerOfTwo) / Math.Pow(10, digit) % 10));
            }
            // write output to console, and save solution to clipboard
            Console.Write("Power of two: {0} Sum of digits: {1}\n", powerOfTwo, sum);
            Clipboard.SetText(sum.ToString());
            Console.WriteLine("Answer copied to clipboard. Press any key to exit.");
            Console.ReadKey();
        }
    }
}

powerOfTwo < 34 では完全に機能するようです。私の計算機はそれ以上の有効桁数を使い果たしたので、それ以上のべき乗をテストできませんでした。しかし、プログラムをトレースすると、オーバーフローが発生していないように見えます。powerOfTwo = 1000 が増加するにつれて、計算される桁数が徐々に増加し、桁数の合計も (平均して) powerOfTwo の増加とともに増加します。

私が実行することになっている実際の計算では、次の出力が得られます。

2 のべき乗: 1000 桁の合計: 1189

しかし、1189 は正しい答えではありません。プログラムの何が問題になっていますか? 私はあらゆる建設的な批判を受け入れます。

4

11 に答える 11

13

このような大きな数の値を計算するには、優れたプログラマーであるだけでなく、優れた数学者でもある必要があります。ここにヒントがあります。おなじみの式 a x = e x ln a、または必要に応じて a x = 10 x log a があります。

より具体的な問題 2 1000 2の共通 (基数 10) の対数を求め、それに 1000 を掛けます。これは 10 の累乗です。 10 53.142 (53.142 = log 2 value * 1000) のような結果が得られた場合 (おそらくそうなるでしょう)、それは 10 53 x 10 0.142です。10 0.142を評価するだけで、1 から 10 までの数値が得られます。それに 10 53を掛けますが、この 10 53は役に立ちません。53 ゼロサムはゼロだけになるからです。

C#での対数計算用 

Math.Log(num, base);

精度を高めるには、Big Integer の Log および Pow 関数を使用できます。

今、残りのプログラミングの助けがあなたの側から得られると信じています。

于 2013-10-11T04:28:51.153 に答える
2

BigInteger クラスを使用しない解決策は、各桁を独自の int に格納してから、手動で乗算を行うことです。

static void Problem16()
{
    int[] digits = new int[350];

    //we're doing multiplication so start with a value of 1
    digits[0] = 1;
    //2^1000 so we'll be multiplying 1000 times
    for (int i = 0; i < 1000; i++)
    {
        //run down the entire array multiplying each digit by 2
        for (int j = digits.Length - 2; j >= 0; j--)
        {
            //multiply
            digits[j] *= 2;
            //carry
            digits[j + 1] += digits[j] / 10;
            //reduce
            digits[j] %= 10;
        }
    }

    //now just collect the result
    long result = 0;
    for (int i = 0; i < digits.Length; i++)
    {
        result += digits[i];
    }

    Console.WriteLine(result);
    Console.ReadKey();
}
于 2014-01-29T00:39:50.110 に答える
1

質問はc＃固有であるため、bigIntを使用するとうまくいく可能性があります。JavaとPythonでも機能しますが、機能が利用できないcやc ++のような言語では、配列を取得して乗算を行う必要があります。配列の大きな数字を取り、それを 2 で乗算します。これは簡単で、論理的スキルを向上させるのに役立ちます。プロジェクトオイラーに来ています。100を求める問題があります！それにも同じロジックを適用したいかもしれません。

于 2013-12-31T06:24:13.847 に答える
1

ビットごとの左シフトを使用しました。次に、配列に変換し、その要素を合計します。私の最終結果は 1366 です。System.Numerics への参照を追加することを忘れないでください。

BigInteger i = 1;
         i = i << 1000;
        char[] myBigInt = i.ToString().ToCharArray();
        long sum = long.Parse(myBigInt[0].ToString());
        for (int a = 0; a < myBigInt.Length - 1; a++)
        {
            sum += long.Parse(myBigInt[a + 1].ToString());
        }
        Console.WriteLine(sum);
于 2013-10-11T05:13:09.140 に答える
0

BigInteger を使用してみてくださいtype。2^100 は倍精度でも非常に大きな数値になります。

于 2013-10-11T10:26:05.700 に答える
0 
BigInteger bi= new BigInteger("2"); 
bi=bi.pow(1000); 
// System.out.println("Val:"+bi.toString()); 
String stringArr[]=bi.toString().split(""); 
int sum=0; 
for (String string : stringArr) 
{ if(!string.isEmpty()) sum+=Integer.parseInt(string); } 
System.out.println("Sum:"+sum);
------------------------------------------------------------------------
output :=> Sum:1366
于 2014-03-13T09:45:33.130 に答える
-1

Python では、ワンライナーを使用してこれを非常に簡単に計算できます。

print sum(int(digit) for digit in str(2**1000))

または代わりにマップを使用：

print sum(map(int,str(2**1000)))
于 2014-11-06T20:35:47.333 に答える