scheme - Scheme で再帰的な手続きを書く。(2 分の 1 の合計 ab)

Question

a から b までの整数を合計する 1 つの方法は、間隔を半分に分割し、2 つの半分を再帰的に合計してから、2 つの合計を合計することです。区間の整数の数が奇数の場合は、できるだけ半分に分割します。この関数を使用して、floor実際の値よりも小さい最大の整数を返すことができます。

(define sum-by-halves (lambda (a b) your_code_here))

これを解決するアイデアはありますか？

Answer 1

問題を再帰的に解く場合は、i) 停止条件を特定し、ii) 大きな問題を同一で小さな問題に分解する方法を理解する必要があります。あなたはすでに「ii」を持っています（詳細を除く）。「私」はどうなる？

停止条件は、「a」と「b」の 2 つの数字が一致したときです。したがって、出発点は次のとおりです。

(define (sum-by-halves a b)
  (if (= a b)
      a
      ...))

'...' の場合、'a' と 'b' の中間にある 'c' が必要です。

(define (sum-by-halves a b)
  (if (= a b)
      a
      (let ((c (div (+ a b) 2)))
        (+ (sum-by-halves a c)
           (sum-by-halves (+ c 1) b)))))

divI を選択することにより、cは常に整数であり、半分または半分未満のいずれかになります。したがって、(+ c 1)は を超えませんb。注: コードは(<= a b).