1

我正在编写一个程序，将机器人从 BST 引导到目标编号。该程序有两个输入参数，一个整数形式的目的地，以及一个表示机器人可以遵循的所有路径的地图。

即：（机器人64'（53（（）（64（）（））））））

其中 64 是目的地，53 ( () ( 64 () () ) )) 是 BST。

我需要帮助编写方法。这是我最初的工作。

(define (robot goal map)
  (let ((x (car map)))
    (define empty? '())
    (display x)
    (cond (empty? x)
          (robot goal (cadr map)))
    (cond ((= goal x)) (display x))
    (cond (< x goal)
          (robot goal (cadr map)))
    (cond (> x goal)
          (robot goal (caddr map)))
    ;(display "NULL")
  ) 
)

它应该搜索 BST，如果找到路径，它会打印（找到：# T # T ... # T #），如果您的目的地在树中但不是根（# 是位置编号和 T是 L 或 R，表示您在位置 # 处左转或右转。

注意：直到昨天我才使用 Lisp，如果我看起来有点迷茫，很抱歉。

4

1 回答 1

1

对于手头的问题，该过程的结构不正确 - 您没有正确处理递归，并且您没有为请求的输出构建一个列表。这也不是正确的使用方式cond，你不应该重新定义现有的程序map和empty?. 另外，如果元素不在树中会发生什么？(car tree)在确定树是非空的之前，你不能这样做。

我将提供解决方案的正确结构并给您一些提示，以便您自己制定解决方案，如果在树中找不到该元素，我们将返回一个列表，其中的值not-found位于最后一个位置。

(define (robot goal tree)
  (cond ((empty? tree)     ; if the tree is empty
         '(not-found))     ; return special value indicating it
        ((= <???> goal)    ; if the current element is goal
         <???>)            ; return a list with current element
        ((< goal <???>)    ; if goal is less than current element
         (cons <???>       ; cons current element
               (cons <???> ; with L and advance the recursion
                     (robot goal <???>))))   ; going to the left
        (else              ; otherwise
         (cons <???>       ; cons current element
               (cons <???> ; with R and advance the recursion
                     (robot goal <???>)))))) ; going to the right

请注意，搜索 BST 的正确方法始终是：

  1. 检查树是否为空
  2. 如果不是，请检查当前元素是否是我们正在寻找的元素
  3. 如果不是，检查我们要查找的元素是否小于当前元素，如果是则转到左子树
  4. 否则转到右子树

作为最后的建议，不要忘记测试您的解决方案：

(robot 64 '(53 () (64 () ())))
=> '(53 R 64)

(robot 42 '(53 () (64 () ())))
=> '(53 L not-found)
于 2013-04-23T19:01:13.377 回答