functional-programming - 你如何在 Scheme 中使用原始表达式找到第 6 个根？

Question

我所说的原始表达式是指 + - */sqrt，除非还有其他我遗漏的表达式。我想知道如何仅使用这些函数编写一个求 6 次方根的 Scheme 表达式。

我知道我可以找到平方根的立方根，但立方根似乎不是原始表达式。

Answer 1

考虑 expt , 传递小数幂作为它的第二个参数。

但是假设我们不知道expt。我们还能计算吗？

一种方法是应用类似 Newton's method 的东西.例如，假设我们想要计算 n^(1/4)。当然，我们已经知道我们可以用 sqrt 两次来做到这一点，但让我们看看牛顿法如何适用于这个问题。

给定n，我们想找出函数的根x:

f(x) = x^4 - n

具体来说，如果我们想寻找 16^(1/4)，那么我们会寻找函数的根:

f(x) = x^4 - 16

我们已经知道，如果我们在其中插入 x=2，我们会发现 2 是该函数的根。但是说我们不知道。我们如何发现使该函数为零的 x 值？

牛顿法说如果我们对 x 有一个猜测，称它为 x_0，我们可以通过执行以下过程来改进这个猜测:

x_1 = x_0 - f(x_0) / f'(x_0)

其中 f'(x) 是 derivative 的符号f(x)。对于上述情况，f(x) 的导数是 4x^3。

我们可以通过重复计算得到更好的猜测 x_2, x_3, ...:

x_2 = x_1 - f(x_1) / f'(x_1)
x_3 = x_2 - f(x_2) / f'(x_2)
...

直到我们累了。

现在让我们用代码编写这一切:

(define (f x)
  (- (* x x x x) 16))

(define (f-prime x)
  (* 4 x x x))

(define (improve guess)
  (- guess (/ (f guess)
              (f-prime guess))))

(define approx-quad-root-of-16
  (improve (improve (improve (improve (improve 1.0))))))

上面的代码只是表达了f(x)、f'(x)，以及将初始猜测改进五次的想法。让我们看看 approx-quad-root-of-16 的值是多少:

> approx-quad-root-of-16
2.0457437305170534

嘿，酷。它实际上在做一些事情，而且接近2。对于 1.0 如此糟糕的第一次猜测，这还不错。

当然，在其中硬编码16 有点傻。让我们概括一下，把它变成一个接受任意 n 的函数，这样我们就可以计算任何东西的四根:

(define (approx-quad-root-of-n n)
  (define (f x)
    (- (* x x x x) n))

  (define (f-prime x)
    (* 4 x x x))

  (define (improve guess)
    (- guess (/ (f guess)
                (f-prime guess))))

  (improve (improve (improve (improve (improve 1.0))))))

这样做有效果吗？让我们看看:

> (approx-quad-root-of-n 10)
1.7800226459895
> (expt (approx-quad-root-of-n 10) 4)
10.039269440807693

很酷:它正在做一些有用的事情。但请注意，它还不是那么精确。为了获得更好的精度，我们应该不断调用 improve，而不仅仅是四五次。思考循环或递归:重复改进直到解决方案“足够接近”。

这是如何解决这类问题的草图。有关更多详细信息，请查看 the section on computing square roots in Structure and Interpretation of Computer Programs .