c++ 项目Euler #8系列中最大的产品

wqsoz72f  于 2022-12-15  发布在  其他
关注(0)|答案(4)|浏览(108)

我正在处理欧拉计划的第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;
}
eaf3rand

eaf3rand1#

首先,你没有像其他人在评论中说的那样初始化y。
第二,这个表达式(num[n] - 48) * (num[n + 1] - 48) * (num[n + 2] - 48) * ...将以int精度完成,因为小于int的类型将在执行算术运算之前提升为int
改成

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

以便以unsigned long long精度计算表达式。使用“0”而不是48,因为它更清楚地表达了意图,并且无论'0'的值如何,它都将工作
当n〉= 1000-12时,您还可以进行越界访问。请改用for

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

如果您认识到在每次迭代中计算乘积时存在一些重叠,则可以进一步改进它

gojuced7

gojuced72#

One major problem as pointed in the other answer, is that your result will be taken as int , exceeding the maximum value of Int32 leading to the wrong answer.Your while will iterate 1 extra index too.The line where you calculate x can be done much better currently it's hard to follow what's going on and it's hard to maintain.
I recommend first creating a constant integer which will have the value of the desired adjacent digits in your case 13.

const int adjacentDigits = 13;

This should do the job now you should also fix the while loop :

while (n <= 1000 - adjacentDigits)

Here we use the const we declared earlier so if we want the code to work for a different amount of adjacent digits we can simply just change the variable responsive for that.
You should give a starting value to y

unsigned long long y = 0;

Now going into the while loop we see the long line I spoke of earlier. We can easily edit this to something like :

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

This is much easier to read and it will remove the use of casting. Now one problem with your current set up your variable 'x' is declared in the outer scope (outside of the loop), and here rather than just setting the variable value we are multiplying it which means we need to reset the variable back to 0 once we are done multiplying. There are 2 ways that you can do this you can either set it to zero at the end of the loop or simply declare it in the while loop which I prefer. It's also important to put the value of x to 1 instead of 0..

unsigned long long x = 1;

After this we simply keep your original check that determines whether we have found a new number.

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

At the end we just print y
Here's the full code :

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;

You might also want to use a little bit more reasonable names x and y sound a little bit like variables that are used in a grid.. For example You can simply change y to maxNumber and y to tempNumber .

kgsdhlau

kgsdhlau3#

我想我应该分享我的解决方案,以及一个要求其他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))
}
fivyi3re

fivyi3re4#

我用Golang解决了这个问题,实际上我所做的是从左右两侧(字符串的开始和结束)阅读系列,以获得一点性能:

package main

import (
    "fmt"
    "strconv"
)

func main() {

    numberOfAdjacentElements := 13
    series := `7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450`

    higher := findGreatestProductInSeries(series, numberOfAdjacentElements)

    fmt.Printf("Product is %v\n", higher)
}

func greater(a, b int) int {

    higher := b

    if a > b {
        higher = a
    }

    return higher
}

func calculateProduct(numbers []int) int {

    product := 1

    for _, number := range numbers {
        product *= number
    }

    return product
}

func findGreatestProductInSeries(series string, numberOfAdjacentElements int) int {

    higher := 0
    length := len(series)

    for index := 0; index < (length/2)-numberOfAdjacentElements; index++ {

        frontArr := []int{}
        tailArr := []int{}

        for row := index; row < index+numberOfAdjacentElements; row++ {
            front, frontError := strconv.Atoi(string(series[row]))
            tail, tailError := strconv.Atoi(string(series[length-1-row]))

            if frontError == nil {
                frontArr = append(frontArr, front)
            } else {
                fmt.Println(frontError)
            }

            if tailError == nil {
                tailArr = append(tailArr, tail)
            }
        }

        startProduct := calculateProduct(frontArr)
        endProduct := calculateProduct(tailArr)
        greatest := greater(startProduct, endProduct)

        if greatest > higher {
            higher = greatest
        }
    }

    return higher
}

相关问题