プロジェクトオイラー＃8シリーズ中の最大の製品

Question

私はProject Eulerの問題＃8に取り組んでいます。「この1000桁の数字のうち、最大の製品を持つ13の数字を探してください。この製品？"

ここは私のC++コードです。何らかの理由で、それは私に間違った答えを与え続けて、間違ったデータ型を使って私と何か関係があると強く疑う。どんな助けでも大歓迎です。

{ 
    int n = 0; 
    unsigned long long x, y; 
    signed char num[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; 
    while(n <= 1000) 
    { 
     x = (num[n] - 48) * (num[n + 1] - 48) * (num[n + 2] - 48) * (num[n + 3] - 48) * (num[n + 4] - 48) * (num[n + 5] - 48) * (num[n + 6] - 48) * (num[n + 7] - 48) * (num[n + 8] - 48) * (num[n + 9] - 48) * (num[n + 10] - 48) * (num[n + 11] - 48) * (num[n + 12] - 48); 
     std::cout << "x" << x << std::endl; 
     if(x > y) 
     { 
      y = x; 
     } 
     n = n + 1; 
    } 
    std::cout << "y" << y << std::endl; 
    std::cout << "n" << n << std::endl; 
} 

Answer 1

一つの大きな問題で積を計算するいくつかの重複があります認識し、さらに場合は、それを改善することができforを使用して、あなたの結果は以下のように取られるということですの最大値を超え、間違った答えにつながるInt32の最大値を超えています.を計算する行は、現在進行中のことを追跡するのが難しく、維持が難しいです。

私が最初にこれは、あなたもwhileループを修正する必要があり、今の仕事を行う必要があります13

const int adjacentDigits = 13; 

あなたのケースで希望隣接する桁の値を持つことになります定数整数を作成することをお勧め：

ここで

while (n <= 1000 - adjacentDigits) 

我々は、コードは、我々は単にそれだけのための応答変数を変更することができ、隣接する桁数の異なる量のために仕事をしたい場合は、我々は以前のように宣言したのconstを使用しています。

あなたは今、私たちは、私が以前の話を聞いた長蛇の列を参照してくださいwhileループに入るy

unsigned long long y = 0; 

に開始値を与える必要があります。

for (int i = n; i < n + adjacentDigits; i++) 
    { 
     x *= (num[i] - '0'); 
    } 

これは、読みやすく、キャストの使用を取り除きます。あなたの現在の変数 'x'の設定に関する1つの問題は、外側のスコープ（ループの外側）で宣言されています。ここでは変数の値を設定するだけではなく、変数を0に戻す必要がありますいったん乗算が完了すると。これを行うには2つの方法があります。ループの終わりにゼロに設定するか、好きなwhileループで単に宣言することができます。それは、我々は、単に我々が新しい番号を発見したかどうかを判断し、あなたのオリジナルのチェックを保つ。.. 0の代わりに1にxの値を入れても、この後

unsigned long long x = 1; 

重要です。終わり

if (x > y) 
{ 
    y = x; 
} 

私たちはここでy

を印刷する完全なコードがあります：あなたはまた、もう少し合理的な名前xとyを使用する場合があります

const int adjacentDigits = 13; 
int n = 0; 
unsigned long long y = 0; 
signed char num[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; 
while (n <= 1000 - adjacentDigits) 
{ 
    unsigned long long x = 1; 
    for (int i = n; i < n+ adjacentDigits; i++) 
    { 
     x *= (num[i] - '0'); 
    } 
    if (x > y) 
    { 
     y = x; 
    } 
    n++; 
} 
std::cout << y << std::endl; 

のような少し聞こえますグリッドで使用される変数。例えば、yをmaxNumberとyからtempNumberに変更するだけです。

Answer 2

まず、コメントに記載されているようにyを初期化していません。 expresionがで計算されるように、int型より小さいタイプは、算術演算に

x = (unsigned long long)(num[n] - '0') * (num[n + 1] - '0') * ... 

へ

変更を行う前にintに昇格されますので、

第二に、この表現(num[n] - 48) * (num[n + 1] - 48) * (num[n + 2] - 48) * ...は、int精度で行われますunsigned long long精度。意図がより明確に言われ、それがの値に関係なく動作するので、48の代わりに '0'を使用してください。

n> = 1000-12のときにアウトオブバウンドアクセスがあります。代わりに

int len = strlen(num); 
for (n = 0; n < len - 12; n++) 

あなたはあなたが他の回答で指摘したように、各反復

Answer 3

Scala;次に、より良いソリューションを投稿してアドバイスしてください。

var a = "73167176531330624919225119674426574742355349194934" 
    var b = "96983520312774506326239578318016984801869478851843" 
    var c = "85861560789112949495459501737958331952853208805511" 
    var d = "12540698747158523863050715693290963295227443043557" 
    var e = "66896648950445244523161731856403098711121722383113" 
    var f = "62229893423380308135336276614282806444486645238749" 
    var g = "30358907296290491560440772390713810515859307960866" 
    var h = "70172427121883998797908792274921901699720888093776" 
    var i = "65727333001053367881220235421809751254540594752243" 
    var j = "52584907711670556013604839586446706324415722155397" 
    var k = "53697817977846174064955149290862569321978468622482" 
    var l = "83972241375657056057490261407972968652414535100474" 
    var m = "82166370484403199890008895243450658541227588666881" 
    var n = "16427171479924442928230863465674813919123162824586" 
    var o = "17866458359124566529476545682848912883142607690042" 
    var p = "24219022671055626321111109370544217506941658960408" 
    var q = "07198403850962455444362981230987879927244284909188" 
    var r = "84580156166097919133875499200524063689912560717606" 
    var s = "05886116467109405077541002256983155200055935729725" 
    var t = "71636269561882670428252483600823257530420752963450" 

    var z = a+ b+ c+ d+ e+ f+ g+ h+ i+ j+ k+ l+ m+ n+ o+ p+ q+ r+ s+ t 
    var z3 = 0L 
    var L1:List[Long] = List() 
    for(x <- 1 to (1000)) 
    { 
    var z2 = z.substring(x,if((x+13) > 1000) 1000 else (x+13)) 
    if (z2 matches ".*0.*") 
     None 
     else 
     { var z3 = z2.toList.map(_.toString.toLong).reduce(_ * _) 
     L1 = L1 :+ z3 
     } 
    } 
    L1.max 
    L1.min 

Answer 4

私は自分のソリューションと他のScalaソリューションを要求した回答を共有したいと思います。私はこれがどんなやり方であっても、ちょっと違うアプローチだと言っているわけではありません。また、私はString.substring()が遅い（線形時間の複雑さ）と思うので、私はそれを使用しないことにしました。

また、次の（13）桁に0がある場合は0が含まれているため、これらすべての桁をスキップすることができます範囲も同様です。

import scala.annotation.tailrec 

object Problem8 extends App { 
    val input = """ 
    73167176531330624919225119674426574742355349194934 
    96983520312774506326239578318016984801869478851843 
    85861560789112949495459501737958331952853208805511 
    12540698747158523863050715693290963295227443043557 
    66896648950445244523161731856403098711121722383113 
    62229893423380308135336276614282806444486645238749 
    30358907296290491560440772390713810515859307960866 
    70172427121883998797908792274921901699720888093776 
    65727333001053367881220235421809751254540594752243 
    52584907711670556013604839586446706324415722155397 
    53697817977846174064955149290862569321978468622482 
    83972241375657056057490261407972968652414535100474 
    82166370484403199890008895243450658541227588666881 
    16427171479924442928230863465674813919123162824586 
    17866458359124566529476545682848912883142607690042 
    24219022671055626321111109370544217506941658960408 
    07198403850962455444362981230987879927244284909188 
    84580156166097919133875499200524063689912560717606 
    05886116467109405077541002256983155200055935729725 
    71636269561882670428252483600823257530420752963450 
    """ 

    val digits = input.filterNot(_.isWhitespace).map(_.asDigit) 

    // val adjacentDigits = 4 
    val adjacentDigits = 13 

    @tailrec 
    def largestProduct(digits: Seq[Int], 
        largestSoFar: BigInt, 
        previousWasZero: Boolean 
        ): BigInt = { 
    digits.take(adjacentDigits) match { 
     case Nil  => largestSoFar 
     case nextDigits => 
     val product = nextDigits.foldLeft(BigInt(1))(_ * _) 
     if (product.equals(BigInt(0))) { 
      val indexOfZero = if (previousWasZero) nextDigits.indexOf(0) else adjacentDigits - 1 
      largestProduct(digits.drop(indexOfZero + 1), largestSoFar, true) 
     } else { 
      val largest = if (product > largestSoFar) product else largestSoFar 
      largestProduct(digits.tail, largest, false) 
     } 
    } 
    } 

    println(largestProduct(digits, BigInt(0), true)) 
}