0

如果你能帮助我解决这个问题的任何部分，我将不胜感激。谢谢。

2^0 = 1
2^N = 2^(N-1) + 2^(N-1)

  1. 将此定义转换为完全等效的树递归函数，称为二次幂。描述它的渐近时间复杂度并解释为什么它有这个时间复杂度。

  2. 现在编写一个名为 tttpo_rec 的函数，它计算完全相同的东西，但它使用线性递归过程，该过程具有 O(n) 时间复杂度，并且还使用 O(n) 空间来进行挂起的操作。

  3. 现在编写一个名为 tttpo_iter 的函数，它计算完全相同的东西，但它使用具有 O(n) 时间复杂度并且还使用常数空间的线性迭代过程。

  4. 现在假设您想概括前面的定义之一，以便它可以处理任意整数幂，以便您可以计算 2^N、3^N 等。编写一个名为 to-the-power-of 的函数，它接受两个参数并将一个提升到另一个的权力。

这是模板：

;; to-the-power-of: integer integer -> integer
;; This function raises m to the power of n, returning the result.
;; m must be > 0 and n >= 0.
(define (to-the-power-of m n)
  ...)

(check-expect (to-the-power-of 1 0) 1) ; base case
(check-expect (to-the-power-of 2 3) 8) ; recursive case
(check-expect (to-the-power-of 3 2) 9) ; recursive case

我们将再添加一个限制：您不能使用 * 运算符；您只能使用以下递归函数进行乘法运算：

;;; multiply: integer integer -> integer
;; This function multiplies two non-negative integers, returning the result.
;; Its time complexity is O(a).
(define (multiply a b)
  ...)

编写函数，并描述其时间复杂度和原因。

4

2 回答 2

1

哈哈哈哈。我不应该为人做作业，但这太有趣了。:-P

  1. 这只是幼稚的实现。我可以回答这个问题，而不会放弃其余的问题。

    (define (tttpo n)
  (if (zero? n) 1
                (+ (tttpo (- n 1)) (tttpo (- n 1)))))

    显然这是一个非常愚蠢的实现，但你被要求给出它的渐近复杂度。

  2. 想想如何避免tttpo每次迭代调用两次。由于您被要求避免使用*，因此您可能需要存储tttpo.

  3. 阅读尾递归。具体来说，您需要知道如何将通用递归算法转换为其等效的迭代（或尾递归，因为这是 Scheme）版本。

  4. 一旦你编写了 3 的代码就很明显了。（或者，告诉我你对 3 的答案，我会进一步帮助你。）

祝你好运！

于 2008-10-23T03:33:31.137 回答
1

第一个算法是O(2^n)，可以写成如下：

(define (2pow x)
  (if (= x 0) 1
      (+ (2pow (- x 1))
         (2pow (- x 1)))))

这可以用 O(n) 重写如下：

(define (2pow x)
  (if (= x 0) 1
    (* 2 (2pow (- x 1)))))

由于 Scheme 使用尾调用优化，我们可以将其写为占用常量堆栈的尾递归函数：

(define (2pow x)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (* accum 2))))
  (internal x 1))

广义：

(define (to-the-power-of a b)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (* accum a))))
  (internal b 1))

编辑：因为我看到你不能使用 *，你可以写你自己的整数乘法：

(define (mult a b)
  (define (internal a accum)
    (if (= a 1) accum
        (internal (- a 1) (+ accum b))))
  (internal a b))

这是尾递归的，因此它在恒定的堆栈空间中运行。只需在上述任何算法中将 * 替换为 mult 即可。

我还应该注意，所有这些功能都是直接在这里编写到编辑器中的，没有经过测试。使用风险自负

于 2008-10-23T03:35:31.910 回答