1

我被要求为课堂上的问题编写一组函数。我认为我写它们的方式比它们需要的要复杂一些。我必须自己实现所有功能，而不使用和预定义的功能。我想知道这些答案是否有任何简单的“单行”版本？

  1. 集合可以表示为列表。集合的成员可以以任何顺序出现在列表中，但列表中的元素不应出现超过一次。

(a) 定义 dif(A, B) 来计算 A 和 B, AB 的集合差。

(b) 定义笛卡尔(A, B) 来计算集合 A 和集合 B 的笛卡尔积，{ (a, b) | a∈A，b∈B}。

(c) 考虑以下数学归纳证明：如果集合 A 有 n 个元素，则 A 的幂集有 2n 个元素。在证明之后，定义 powerset(A) 来计算集合 A 的幂集，{ B | B ⊆ A }。

(d) 定义一个函数，给定一个集合 A 和一个自然数 k，返回 A 大小为 k 的所有子集的集合。

(* Takes in an element and a list and compares to see if element is in list*)

fun helperMem(x,[]) = false
|   helperMem(x,n::y) =
      if x=n then true
      else helperMem(x,y);

(* Takes in two lists and gives back a single list containing unique elements of each*)

fun helperUnion([],y) = y
|   helperUnion(a::x,y) =
       if helperMem(a,y) then helperUnion(x,y)
       else a::helperUnion(x,y);

(* Takes in an element and a list. Attaches new element to list or list of lists*)
 fun helperAttach(a,[]) = []
  helperAttach(a,b::y) = helperUnion([a],b)::helperAttach(a,y);


  (* Problem 1-a *)
fun myDifference([],y) = []
 |   myDifference(a::x,y) = 
    if helper(a,y) then myDifference(x,y)
    else a::myDifference(x,y);

 (* Problem 1-b *)
 fun myCartesian(xs, ys) =
    let fun first(x,[]) = []
    |       first(x, y::ys) = (x,y)::first(x,ys)
        fun second([], ys) = []
    |       second(x::xs, ys) = first(x, ys) @ second(xs,ys)
    in      second(xs,ys) 
    end;


 (* Problem 1-c *)
 fun power([]) = [[]]
 |   power(a::y) = union(power(y),insert(a,power(y)));

我从来没有遇到过一维问题，因为这些我花了一段时间才解决。有什么建议可以缩短这些吗？还有另一个我没有得到的问题，但我想知道如何为将来的测试解决它。

  1. （楼梯问题）你想上 n (>0) 级的楼梯。一次，您可以走一步、两步或三步。但是，例如，如果还剩一步，您只能走一步，而不是两步或三步。上楼梯有多少种不同的方式？用 sml 解决这个问题。(a) 递归求解。(b) 迭代求解。

关于如何解决这个问题的任何帮助？

4

1 回答 1

2

你的设置功能看起来不错。除了它们的格式和命名之外，我不会更改它们的任何主要内容：

fun member (x, [])    = false
  | member (x, y::ys) = x = y orelse member (x, ys)

fun dif ([],   B) = []
  | dif (a::A, B) = if member (a, B) then dif (A, B) else a::dif(A, B)

fun union ([],   B) = B
  | union (a::A, B) = if member (a, B) then union (A, B) else a::union(A, B)

(* Your cartesian looks nice as it is. Here is how you could do it using map: *)
local val concat = List.concat
      val map = List.map
in fun cartesian (A, B) = concat (map (fn a => map (fn b => (a,b)) B) A) end

你的电源也很整齐。如果你调用你的函数insert，它值得评论关于在许多列表中插入一些东西。也许insertEach或类似是一个更好的名字。

在您的最后一项任务中，由于这是一个计数问题，您不需要生成实际的步骤组合（例如，作为步骤列表），只需计算它们。使用递归方法，尝试将基本案例写下来，就像它们在问题描述中一样。

即，制作一个函数steps : int -> int，其中预先计算了采取 0、1 和 2 步的方式的数量，但是对于n步，n > 2，你知道有一组以 1、2 开头的步骤组合或 3 步加上分别采取n-1、n-2和n-3步的数量组合。

使用迭代方法，从底部开始并使用参数化计数变量。（对不起这里的模糊提示。）

于 2013-10-12T11:17:40.807 回答