項目歐拉＃類型溢出5

2520是可以由每個號碼沒有任何除盡從1到10的最小數目。

可以被1到20的所有數字均分的最小正數是多少？

這裏是我的代碼：

open System 

let rec gcd a b = 
    match b with 
     | x when x = 0 -> a 
     | _ -> gcd b (a % b) 

let lcm a b = (a * b)/(gcd a b)   
let result = Seq.fold lcm 1 [1..20] 

[<EntryPoint>] 
let main(args : string[]) = 
    printfn "result = %d" result 
    0

它正常工作與數[1..19]，但我得到錯誤的結果與數字[1..20]。我試圖找出錯誤的原因並發現：

$ Seq.fold lcm 1 [1..19] 
232792560 // right 
$ lcm 232792560 20 
18044195 // wrong

它看起來像類型的溢出。我該如何解決這個錯誤？

來源

2011-06-24 demas

另一個解決辦法是由略小數乘法重新定義略有LCM功能

let lcm a b = let m = b/(gcd a b) in a * m;;

既然你，它不會溢出。歐拉問題也與數學有關：p

來源

2011-06-24 12:47:26

使用BigInt，這是一個不會溢出的整數類型。如果您要更換0與0I在gcd（該I後綴用於BigInt文字），那麼這兩個gcd和lcm將infered與BigInt！而非int s到工作。

來源

2011-06-24 12:36:19

而不是步驟1，你也可以用'0I'代替'0'。 –

@Ramon Snir - 實際上，我將修改我的答案以表明相反，因爲無論如何您都無法擁有遞歸內聯函數。 –

在其他語言中，可以使用4字節整數直到它溢出，然後運行時升級整數，然後按計劃進行。

我不知道我們是否可以在F＃中做同樣的事情來優化性能。

來源

2011-06-24 14:33:36 GregC

爲了好玩，試着計算3^N，然後打印這些值。在Ruby中。 – GregC

你可以用任何語言做同樣的事情，但表現很糟糕。整數溢出在實踐中非常罕見，因此不值得犧牲所有整數算術的性能特徵。 –

您可以使用LanguagePrimitives.GenericZero而不是文字0.這樣，gcd函數和lcm函數是通用的，並且可以與任何數字類型一起使用。這裏使用int64的解決方案：

module Problem5 = 
    let rec greatestCommonDivisor a b = // Euclidean algorithm 
     if b = LanguagePrimitives.GenericZero then a 
     else greatestCommonDivisor b (a % b) 
    let leastCommonMultiple a b = (a * b)/(greatestCommonDivisor a b) 
    // Take the least common multiple of all numbers from 1 to 20. 
    let solution = [1L..20L] |> List.fold leastCommonMultiple 1L

來源

2014-02-28 21:35:27

項目歐拉＃類型溢出5

回答

相關問題