在LispWorks中进行编程26：生成所有可能的答案

生成所有可能的答案

接下来，我们将生成每个可能的候选答案，包括六个数字和四个运算符的每个可能组合。

由于我们只允许使用每个数字，因此我们需要一个过程来检查数字是否已在表达式中使用过。我们将使用一个过程  find-tree，它可以递归定义，如下所示：

要检查表达式是否包含指定的数字：

• 如果表达式是原子，如果表达式是数字，则答案为真。
• 否则，如果我们在表达式的第一个元素或表达式的其余部分中找到数字，则答案为真。

在Lisp中，这变为：

(defun find-tree (number expression)  (if (atom expression) (eq number expression)      (or (find-tree number (first expression))          (find-tree number (rest expression)))))

我们可以测试如下：

CL-USER > (find-tree 4 ‘(* (+ 4 1) (* 2 3)))T CL-USER > (find-tree 5 ‘(* (+ 4 1) (* 2 3)))NIL

接下来，我们定义一个过程next-states来构建所有可能的表达式：

(defun next-states (expression)  (let ((result nil))    (dolist (i countdown-numbers)      (if (find-tree i expression) nil        (setf result (cons (cons i expression) result))))    (if (>= (length expression) 2)        (dolist (i countdown-operators)          (let ((new (list i (first expression) (second expression))))              (if (eval new)                  (setf result                        (cons (cons new (rest (rest expression))) result))))))    result))

这将采用部分表达式，并生成包含附加运算符或数字的新部分表达式列表。表达式被添加到变量result中，该变量最初由let语句设置为nil。

该过程的前半部分将每个未使用的数字添加到表达式的开头。例如：

CL-USER > (next-states ‘(1))((4 1) (25 1) (50 1) (100 1) (75 1))

如果表达式中有两个或更多项，则过程的后半部分将表达式中的前两个数字与每个运算符组合在一起，并将这些数字添加到结果列表中。如果他们不这样做表达式只添加EVAL到零：

CL-USER > (next-states ‘(4 1))(((?- 4 1)) ((?+ 4 1)) (25 4 1) (50 4 1) (100 4 1) (75 4 1))

结果列表包含完整的表达式，例如：

((?- 4 1))

和部分表达式，例如：

(25 4 1)

完整的表达式通过下面的目标-p进行测试，看看他们是否评估目标数量。

寻找解决方案

最后，我们定义例程树搜索  来搜索解决方案：

(defun tree-search (expressions)  (cond   ((null expressions) nil)   ((goal-p (first expressions)) (first expressions))   (t (tree-search       (append        (next-states (first expressions))        (rest expressions))))))

此过程树搜索采用列表列表; 每个列表都是部分或完整的候选表达式。它说：

• 如果没有更多要检查的表达式，请返回nil。
• 如果第一个表达式满足目标，则返回它。
• 否则，将第一个表达式替换为第一个表达式的next-states，并解决该问题。

这是检查表达式是否解决问题的过程

(defun goal-p (rule)  (and (= (length rule) 1)       (eq (eval (first rule)) countdown-target)))

解决原始问题

最后，让我们用我们最初的问题运行  树搜索。要搜索所有表达式，我们使用包含nil的列表调用tree-search：

CL-USER > (tree-search ‘(nil))

几秒钟后，程序返回答案：

((?/ (?- (?* (?- 75 4) 25) 1) (?/ 100 50)))

这对应于以下解决方案：

找到了！

扩展项目

候选人重复

一个扩展是删除所有候选号码必须不同的限制。最简单的方法是在列表中提供它们，并通过列表中的索引访问它们。可以测试索引以确保它们是唯一的，但数字不一定必须。