1

所以首先我很抱歉问这个问题。但是“逃离 Zurg”文章对我帮助很大，我可以编写自己的解决方案来解决 Wolf Goat Cabbage Problem。我在下面放置我的代码。我要你告诉我

  1. 如果我的代码是按照 F# 和函数式编程的真正精神编写的

  2. 这是解决问题的最佳和良好的解决方案

    open System

(* 
  The type direction determines which direction the human is present.
  Left means that Human is present on the left side of the bank.
  Right means human is present on the right side of the bank.
*)
type Direction =
  | Left
  | Right

(*
  Master list of animals
*)
let Animals = ["Wolf"; "Goat"; "Cabbage"]

let DeadlyCombinations = [["Wolf"; "Goat"];["Goat"; "Cabbage"];]

let isMoveDeadly list1 list2 =
  List.exists (fun n -> n = list1) list2

let rec MoveRight animals =
  match animals with
    | [] -> []
    | head::tail -> 
      if (isMoveDeadly tail DeadlyCombinations) then
        MoveRight tail @ [head]
      else
        Console.WriteLine("Going to move " + head)
        tail

let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) list1) list2

let MoveLeft animals = 
  let RightList = ListDiff animals Animals 
  let ShouldTakeAnimal = isMoveDeadly RightList DeadlyCombinations
  if (ShouldTakeAnimal) then
    let x = List.head RightList
    Console.WriteLine("Going to move " + x + " back")
    [x]
  else
    Console.WriteLine("Farmer goes back alone")
    []

let rec Solve direction animals =
    match animals with 
    | [] -> Console.WriteLine("Solved")
    | _ ->
        match direction with
        | Left -> Solve Right (MoveRight animals) 
        | Right -> Solve Left (animals @ (MoveLeft animals))

[<EntryPoint>]
let main args =
    Solve Left Animals
    0
4

1 回答 1

6

代码看起来很实用。我会做一些改变。首先，我会使用集合来表示动作，还有一些小建议......

表示。您使用列表表示致命组合，因此["Goat"; "Wolf"]与["Wolf"; "Goat"]您的算法以其他顺序生成移动不同，它不会将其检测为致命移动。您应该尝试找到不会发生这种情况的表示，因此我会更改表示以使用集合：

let DeadlyCombinations = [set ["Wolf"; "Goat"]; set ["Goat"; "Cabbage"];]

在isMoveDeadly函数中，您可以使用以下方法将移动转换为集合（但最好将代码更改为在任何地方使用集合）：

let move = set list1

不必要的概括。除此之外，该函数isMoveDeadly始终DeadlyMoves作为第二个参数，所以我不会将它作为参数传递（这是不需要的概括），我会写：

let isMoveDeadly list = 
  let move = set list
  DeadlyCombinations |> List.exists (fun n -> n = move)

效率提示。在MoveRight函数中，您使用的list @ [element]模式非常低效。这意味着您需要复制整个list以将元素附加到末尾。使用（较少复制）将元素添加到前面element::list然后反转列表更有效。如果您将致命动作表示为一组，我想您甚至不需要反转列表，所以我会写：

let rec MoveRight animals = 
  match animals with 
    | [] -> [] 
    | head::tail ->  
      if (isMoveDeadly tail) then 
        head :: (MoveRight tail)
      else 
        Console.WriteLine("Going to move " + head) 
        tail

代表（再次）。您实现了自己的ListDiff函数来找出给定列表中没有的动物。这表明使用集合（而不是列表）确实是一种更好的表示形式。如果您切换到集合，则可以改用内置函数Set.difference。

于 2012-07-15T11:24:18.220 回答