F＃ - 從...返回一個值。do

我有一組（隨機）數字，我想決定任何給定的數字，數字是否爲複合數字（意味着它可以由兩個其他數字創建相同的給定集合）。
我的函數的數學定義：F＃ - 從...返回一個值。do

當前代碼：

let task1 (M : seq<'T>, r : 'T) : bool = 
    if not(Seq.exists((=) r) M) then 
     failwith "nope!" 
    else 
     for s in M do 
      for t in M do 
       if s + t = r then 
        true   // error 
     false

問題：
我無法從我的迭代返回一個布爾值，當元素r已被'發現'爲兩個元素的總和s和t。

我怎樣才能儘可能有效地解決給定的問題？

如果有人發現有總運行時間爲O（N²）小的算法，那麼它也沒意見。
[所有調用的方法也必須比O（N²）更快]

來源

2016-04-23 Unknown6656

這是偶然的作業嗎？當有人問大O的限制算法時，我只需要問。 O（n2）對於這個問題是顯而易見的。 –

@GuyCoder：嗯，這是一個任務，可以在後面的考試中提出，我正在嘗試寫在F＃中;）謝謝你的第二個評論，主席先生 - 我意識到我忘記了一個'不' – Unknown6656

在這種情況下，使用Seq.find而不是循環 –

通常，您不希望使用循環來實現F＃中的複雜迭代/遞歸函數。這就是尾遞歸函數的優點。

爲了得到低於O（n2）的計算複雜度，怎麼樣：考慮一組候選加數，它是最初的一組完整數字。現在看看這個集合中最大和最小數字的總和。如果該總和大於目標號碼，則最大號碼不會與任何事物的目標號碼相加。反過來也是如此。

繼續從候選組中刪除最小或最大的數字，直到該組爲空或已找到匹配。

的代碼看起來是這樣的：

let rec f M x = 
    if Set.isEmpty M then false else 
    let biggest, smallest = Set.maxElement M, Set.minElement M 
    let sum = biggest + smallest 
    if sum > x then f (Set.remove biggest M) x 
    elif sum < x then f (Set.remove smallest M) x 
    elif sum = x then true 
    else failwith "Encountered failure to compare numbers/NaN"

當我看的數學定義，它似乎並不爲目標數是集合的要求。但是，如果這個問題，只是事先檢查：

let fChecked M x = 
    if Set.contains x M then f M x 
    else invalidArg "x" "Target number is not contained in set."

湯姆使這個通用在可比的類型，功能可以被標記inline。

設置的操作是O（log n），我們遍歷整個事情，乘以O（n），使得總複雜度爲O（n log n）（其中n是集合中元素的數量）。

有效極速版

如果它是關於實際速度，而不是「只是」計算複雜，數組可能更快，比一成不變套。下面是一個使用數組索引版本：

/// Version where M is types as an unsorted array we're allowed to sort 
let f M x = 
    Array.sortInPlace M 
    let rec iter iLow iHigh = 
     if iLow > iHigh then false else 
     let sum = M.[iLow] + M.[iHigh] 
     if sum > x then iter iLow (iHigh - 1) 
     elif sum < x then iter (iLow + 1) iHigh 
     elif sum = x then true 
     else failwith "Encountered failure to compare numbers/NaN" 
    iter 0 (M.Length - 1)

需要注意的是，我們可以在數組，如果同組中重複使用預先排序，使這項工作的複雜每次調用同一組下降到爲O（n）。

來源

2016-04-23 21:23:09 Vandroiy

我非常喜歡這個解決方案，雖然我認爲我更喜歡@TheInnerLight的一個，因爲它的簡單性....但是我認爲你的性能更好:) – Unknown6656

@ Unknown6656那麼，你要求的計算複雜度小於O（ N²）。我認爲這將是更有趣的練習。：P – Vandroiy

先生，你是對的。然而，明天我會接受一個答案（還沒有），給別人發佈其他'練習'的機會;） – Unknown6656

你不能做你想要做什麼，因爲F＃是使用表達式，而不是語句的語言。 F＃表達式總是評估爲一個值（儘管該值可能是單位：()）。

您最初發布的代碼不會被編譯，因爲預計有類型unit，這是因爲您的if/then表達式沒有else分支。考慮以下幾點：

let a = if x > 5 then 10

該代碼會產生一個編譯器錯誤，因爲我們還沒有指定的a整數值可能是什麼，如果x不大於5

當然，這是顯而易見的，這段代碼編譯：

let a = if x > 5 then 10 else 5

如果你提供和if沒有else，F＃編譯器將假定類型爲單元，這也是有效的代碼：

let a = if x > 5 then()

這是因爲這兩種情況仍然只是返回unit，沒有類型不匹配。

因爲F＃使用表達式，所有東西都必須可以綁定到一個值。

無論如何，你可以通過使用嵌套Seq.exists語句解決這個問題，這樣你可以檢查值的每個組合。

let inline task1 items r = 
    items |> Seq.exists (fun s -> 
     items |> Seq.exists(fun t -> s + t = r))

我已經改變了一些命名約定的（這是慣用的被駝峯格式F＃功能參數），並取得了你的函數inline所以它會在支持添加任何類型的工作。

來源

2016-04-23 21:22:45 TheInnerLight

F＃ - 從...返回一個值。do

回答

相關問題