Project Euler Q8系列中最大的产品 - 为什么我的代码错了？

Question

问题是(来源)......

具有最大乘积的1000位数字中的四个相邻数字是9×9×8×9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 7163626956188267042825248360082 3257530420752963450

找到具有最大产品的1000位数字中的十三个相邻数字.这个产品有什么价值？

我有以下F#...

let largestProduct n (s : string) =
  [ for i in [0..(s.Length - n)] do yield s.[i..(i + n - 1)]]
  |> Seq.map (fun s -> s, s |> Seq.fold (fun p c -> p * (int (string c))) 1)
  |> Seq.maxBy snd

您传递的位数和1000位数字作为字符串.第一行产生一系列n字符串,这些字符串通过管道输入到计算数字乘积的第二行.它包含在带有n个字符串的元组中,因此我可以看到哪个n个字符集产生了最高的产品.最后一行获得最大产品.

如果我运行如下...

largestProduct 4 nStr

...其中nStr是一个1000位数的字符串,它产生以下...

("9989", 5832)

...哪个是对的.但是,如果我将数字更改为13,以解决实际问题,它会给我...

("9781797784617", 2091059712)

......显然是错的.

任何人都知道为什么我的代码不起作用？我已经尝试了n的各种小值,看起来它在那里工作.我也用较短的琴弦试了一下,看起来效果很好.

Answer 1

此练习导致Int32溢出.任意长度类型bigint解决了这个问题,以获得通常足够的输入范围.例如:

let digitsToProduct inp =
    inp |> Seq.map (string >> bigint.Parse)
        |> Seq.fold (*) 1I

let largestProduct n : (seq<char> -> bigint) =
    Seq.windowed n >> Seq.map digitsToProduct >> Seq.max

编辑:注意largestProduct采用第二个参数:1000位数字符串(或任何字符序列).

从中可以学到什么？

这是一个值得思考的基本问题.根据经验,功能应该是正确的或失败的,至少对于合理的输入.我认为,在开发人员可能犯这样错误的任何情况下,仅使用64位整数的答案是临界错误的.毕竟,它仍然会在太大的输入上无声地失败.

如果要对此类函数使用32位或64位整数,请验证输入!

例如,粗略验证可能是:

// 32b version
if n > 9 then invalidArg "n" "number of digits too large for Int32."
// 64b version
if n > 19L then invalidArg "n" "number of digits too large for Int64."

这将导致您的程序正常失败,而不是默默地产生无意义的结果.