0

この質問の一部を手伝っていただければ幸いです。ありがとう。

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

  1. この定義を、2 の累乗と呼ばれるまったく同等のツリー再帰関数に変換します。その漸近的な時間計算量を説明し、なぜこの時間計算量を持つのかを説明してください。

  2. ここで、まったく同じことを計算する tttpo_rec という関数を作成しますが、O(n) 時間の複雑さを持ち、保留中の操作に O(n) スペースを使用する線形再帰プロセスを使用します。

  3. ここで、まったく同じことを計算する tttpo_iter という関数を作成しますが、O(n) 時間の複雑さを持ち、一定のスペースを使用する線形反復プロセスを使用します。

  4. ここで、2^N、3^N などを計算できるように、前述の定義の 1 つを一般化して、任意の整数乗を処理できるようにしたいとします。2 つの引数を取る 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

もう 1 つ制限を追加します。* 演算子は使用できません。乗算を行うには、次の再帰関数のみを使用できます。

;;; 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反復ごとに 2 回呼び出さないようにする方法を考えてください。の使用を避けるように求められているため*、 の結果を隠しておく必要がある場合がありますtttpo。

  3. 末尾再帰を読んでください。具体的には、一般的な再帰アルゴリズムを同等の反復 (またはスキームなので末尾再帰) バージョンに変換する方法を知る必要があります。

  4. 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 に答える