在LispWorks中进行编程25：倒数

Category:UI界面编写 Tags : 在LispWorks中进行编程

倒数

Number Countdown是一款在英国着名电视节目Countdown上播放的游戏。参赛者将获得六个数字和一个三位数的目标，目的是通过使用加法，减法，乘法和除法组合六个数字来尝试达到目标。在计算的任何阶段只能使用整数，每个数字只能使用一次。

举个例子，这是一个特别难的问题。这六个数字是：

目标是：

在阅读下面的答案之前尝试解决它！

在这个项目中，我们将编写一个Lisp程序来解决任何Number Countdown问题。我们使用的方法可以扩展到解决许多类型的数学，逻辑和单词问题，例如杂志和拼图书中出现的问题。

完整列表

该方法

解决此类问题的典型方法如下：

• 使用六个候选数字和四个运算符组合构建每个可能的等式。
• 测试每个等式以查看它是否符合目标。

然而，由于存在大量可能的方程，这通常需要不可避免的大量计算时间，因此该方法的一个重要部分是通过消除不能求解的方程来减少我们必须考虑的方程的数量，或者复制现有的等式。

代表问题

我们将使用全局变量来表示问题的数字，运算符和目标：

(defparameter countdown-numbers ‘(75 100 50 25 1 4)) (defparameter countdown-operators ‘(?+ ?- ?* ?/)) (defparameter countdown-target 887)

请注意，为简单起见，我们假设数字都不同。如果我们想要删除这个限制，它会使编程更复杂一些。

对于运算符，我们将定义自己的过程，称为？+，？ – ，？*和？/。稍后会详细介绍。

代表答案

解决这样的问题的一个好的起点是决定我们如何表示答案，假设我们可以找到它。对于这个问题，我们将使用标准的Lisp表达式; 例如：

(* (+ 4 1) (* 2 3))

将使用数字1,2,3和4获得30目标的解决方案。我们可以通过执行以下操作来检查：

CL-USER > (eval ‘(* (+ 4 1) (* 2 3)))30

减少候选人人数

通过观察：我们可以减少可能的候选方程的数量：

• 如果b大于a，则可以消除（+ ab），因为它与（+ ba）相同。
• 如果b大于a，则可以消除（* ab），因为它与（* ba）相同。
• 如果b大于a，则可以消除（ – ab），因为我们对负数不感兴趣。
• 如果b为1，则可以消除（* ab），因为它相当于a。
• 如果b为零，则可以消除（+ ab），因为它等于a。
• 如果b为零，则可以消除（* ab），因为在表达式中零是多余的。
• 如果b为零，则可以消除（/ ab），因为除以零将导致错误。
• （/ ab）可以被删除，除非它是一个整数，因为规则不允许分数。

其中许多大致将候选表达式的数量减半，因此应用它们会导致我们必须考虑的候选表达式数量的急剧减少。

我们将通过定义我们自己的四个算术运算版本来实现这些优化，称为？+，？ – ，？*和？/。如果我们想要(defun ?+ (a b)  (if (or (null a) (null b) (< a b) (zerop a))      nil    (+ a b))) (defun ?- (a b)  (if (or (null a) (null b) (zerop b) (< a b))      nil    (- a b))) (defun ?* (a b)  (if (or (null a) (null b) (< a b) (= b 1) (= a 1) (= b 0) (= a 0))      nil    (* a b))) (defun ?/ (a b)  (if (or (null a) (null b) (zerop b) (= b 1) (not (integerp (/ a b))))      nil    (/ a b)))

我们来测试一下：

CL-USER > (eval ‘(?* (?* (?+ 4 1) 3) 2))30CL-USER > (eval ‘(?* 2 (?* (?+ 4 1) 3)))NIL

http://mip.i3geek.com