0

定义一个函数，给定一个列表 L、一个对象 x 和一个正整数 k，如果 x 在 L 中至少出现 k 次，则返回 x 在 L 中第 k 次出现的位置，否则返回 0。例如，如果 L为 [#"a", #"b", #"c", #"b"]，x 为 #"b"，k 为 2，则函数返回 4。

对于这个问题，我不能使用任何辅助功能，也不能使用长度功能。关于我将如何解决它的任何想法？

4

1 回答 1

2

假设find是您必须实现的功能。从描述中可以直接看出两件事：

  • find返回一个整数
  • find至少需要三个参数（L、x和k）

此外，列表上的函数通常区分两种情况：给定列表为空 ( []) 或包含至少一个元素 ( y::ys)。因此，我们可以使用以下骨架find

fun find   []    x k = ...
  | find (y::ys) x k = ...

您应该首先考虑在这两种情况下该怎么做。如果L为空，则其中肯定没有出现x，因此结果为0。否则，L由一个 head-elementy和剩余的 list组成ys。如果x等于y，我们只是找到了一个出现的x，否则我们要继续搜索ys。据此，骨架可细化为

fun find   []    x k = 0
  | find (y::ys) x k =
      if x = y then ...
      else find ys x k

此时唯一剩下的部分是 whenL不为空和x = y。但是由于我们对k第 -th 的出现感兴趣x，我们必须检查是否找到它。这可以通过k每次我们发现 的 出现时减少来完成x，最后，当我们发现同时出现k的1时候，我们找到了所需的k第 - 次出现x。

fun find   []    x k = 0
  | find (y::ys) x k =
       if x = y andalso k > 1 then find ys x (k - 1)
       else if x = y then ...
       else find ys x k

剩下的情况是我们发现 的k第 - 次出现x。所以我们应该返回这个事件的索引i。但是我们应该i从哪里得到呢？在某种程度上，我们必须在我们的函数中计算它。如何做到这一点，由您来了解。

于 2013-09-24T06:57:35.210 回答