Scheme 或 Common Lisp 中的牛顿平方根法

Question

我无法找出该程序中的错误。这是方案版本。我也尝试了 Common Lisp 版本。在这两种情况下，程序都保留运行而没有任何结果。请帮忙。

(define (sqrt1 x)

  (define (square x)
      (* x x))

  (define (isGoodEnough g x)
      (< (abs (- (square g) (square x))) 0.01))

  (define (average x y)
      (/ (+ x y) 2))

  (define (improvedGuess g x)
      (average g (/ x g)))

  (define (sqrt-iter g x)
      (if (isGoodEnough g x)
          g
          (sqrt-iter (improvedGuess g x) x)))

  (sqrt-iter 1.0 x))

Answer 1

isGoodEnough 有一个错误。您正在对当前猜测 g 和数字 x 求平方。但是由于 g 应该是 x 的平方根，所以如果将它们都平方则它们永远不会接近。你应该只平方猜测。

(define (isGoodEnough g x)
  (< (abs (- (square g) x)) 0.01))

Answer 2

你自己应该能找到问题所在。我会告诉你如何去做。我将使用 LispWorks，但它与大多数 Lisp 实现的工作方式相似。

这是您使用 Common Lisp 编写的代码：

(defun square (x)
  (* x x))

(defun isGoodEnough (g x)
  (< (abs (- (square g)
             (square x)))
     0.01))

(defun average (x y)
  (/ (+ x y) 2))

(defun improvedGuess (g x)
  (average g (/ x g)))

(defun sqrt-iter (g x)
  (if (isGoodEnough g x)
      g
    (sqrt-iter (improvedGuess g x) x)))

(defun sqrt1 (x)
  (sqrt-iter 1.0 x))

我现在已经用 LispWorks 评估了代码。

让我们尝试计算 2.0 的平方根：

CL-USER 8 > (sqrt1 2.0)

LispWorks 出现堆栈溢出，但如果它处于无限循环中，我们可以手动中断它：

Stack overflow (stack size 53998).
  1 (continue) Extend stack by 50%.
  2 (abort) Return to level 0.
  3 Return to top loop level 0.

Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.

CL-USER 9 : 1 > 是提示符。在包 CL-USER 中，九种形式在侦听器和中断循环级别一中评估。

:bq 是快速回溯概述的命令：

CL-USER 9 : 1 > :bq

ERROR <- AVERAGE <- IMPROVEDGUESS <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER
...
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER
<- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- SQRT-ITER <- EVAL
<- CAPI::CAPI-TOP-LEVEL-FUNCTION <- CAPI::INTERACTIVE-PANE-TOP-LOOP
<- MP::PROCESS-SG-FUNCTION

:n是转到下一个堆栈帧的命令。

CL-USER 10 : 1 > :n
Interpreted call to AVERAGE

CL-USER 11 : 1 > :n
Interpreted call to IMPROVEDGUESS

CL-USER 12 : 1 > :n
Interpreted call to SQRT-ITER

:v 是查看该堆栈帧的变量值的命令。我们查看这一帧和下一帧，看看该函数是如何被调用的。

CL-USER 13 : 1 > :v
Interpreted call to SQRT-ITER:
  G : 1.4142135                    ; current guess
  X : 2.0

CL-USER 14 : 1 > :n
Interpreted call to SQRT-ITER

CL-USER 15 : 1 > :v
Interpreted call to SQRT-ITER:
  G : 1.4142135                    ; prior guess
  X : 2.0

因此当前猜测和先前猜测相等。

看看你的代码：

(defun sqrt-iter (g x)
  (if (isGoodEnough g x)
      g
    (sqrt-iter (improvedGuess g x) x)))

这个递归调用只有在猜测不够好时才会发生。使用当前值检查它：

CL-USER 16 : 1 > (isgoodenough 1.4142135 2.0)
NIL

不过应该是T吧，其实猜的还不错。有错误！！我们看代码：

(defun isGoodEnough (g x)
  (< (abs (- (square g)
             (square x)))
     0.01))

嗯，你把两者都平方了。 1.4142135 和 2.0。那是错误的。让我们将其更改为不对 `x:

的值求平方

CL-USER 17 : 1 > (defun isGoodEnough (g x)
                   (< (abs (- (square g)
                              x))
                      0.01))
ISGOODENOUGH

验证：

CL-USER 18 : 1 > (isgoodenough 1.4142135 2.0)
T

现在 LispWorks 很酷，让我们使用 :res 命令重新启动当前调用 (sqrt-iter 1.4142135 2.0)：

CL-USER 19 : 1 > :res
1.4142135

CL-USER 20 >

我们得到了足够好的结果，然后 LispWorks 又回到了顶级：1.4142135。

Scheme 或 Common Lisp 中的牛顿平方根法

Newton's square root method in Scheme or Common Lisp

lisp

scheme

common-lisp