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

回答

相关问题