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

Question

我无法弄清楚这个程序中的错误.这是Scheme版本.我也尝试过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

你应该能够自己找到问题.我会告诉你如何做到这一点.我将使用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,在监听器和break循环级别1中评估了九种形式.

: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很酷,让我们(sqrt-iter 1.4142135 2.0)使用以下:res命令重启当前调用:

CL-USER 19 : 1 > :res
1.4142135

CL-USER 20 > 

我们得到了足够好的结果,LispWorks又回到了顶层:1.4142135.

Answer 2

isGoodEnough有一个错误.你正在调整当前的猜测g和数字x.但是因为g它应该是平方根x,所以如果你把它们都放在一边,它们就永远不会接近.你应该只猜测猜测.

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