Формула шнурка в ракетке

Question

У меня проблемы с поиском способа рекурсивного вычисления площади.

(check-expect(signed-area(list (make-posn 1 2)(make-posn 3 4)(make-posn 5 6)(make-posn 1 6)))8)

(ожидаемый чек (область подписи (список (make-posn 1 2) (make-posn 11 3) (make-posn 12 9) (make-posn 2 10))) 70)

    (define (signed-area lop)
  (cond
    [(< 3 (length lop)) 0]
    [else
     (abs (/ (+(-(* (posn-x (first  lop)) (posn-y (second lop))) 
                 (* (posn-x(second lop)) (posn-y(first lop))))
               (-(* (posn-x (second  lop)) (posn-y (third lop)))
                 (* (posn-x(third lop)) (posn-y(second lop))))
               (-(* (posn-x (third  lop)) (posn-y (fourth lop))) 
                 (* (posn-x(fourth lop)) (posn-y(third lop))))
               (-(* (posn-x (fourth  lop)) (posn-y (first lop))) 
                 (* (posn-x(first lop)) (posn-y(fourth lop)))))
               2))]))

У меня нет идей о том, как рекурсивно пройти по списку и удалить первый posn после того, как он прошел по списку. Поскольку код, который у меня есть, ограничен 4 баллами, и я должен сделать так, чтобы он был не менее 3 баллов

Answer 1

Решение I - прямая рекурсия

Однако проблема заключается в функции absolute в конце всей формулы. Для того чтобы это было выполнено в самом окончательном варианте для всей суммы, вы должны поместить свою функцию во внешнюю функцию и применить abs к вызову функции:

(define (signed-area plist)
  (define (.signed-area plist)
    (cond ((< (length plist) 3) 0)
          (else (+
                 (/ (- (* (first plist) (fourth plist))
                       (* (second plist) (third plist)))
                    2)
                 (.signed-area (cddr plist))))))
  (abs (.signed-area plist))) ;; final absolute

Вместо деления на для каждого слагаемого вы можете сделать это также в самый конец на всю абсолютную сумму. Итак, очень очень минимально более эффективный - но в практике совершенно незначительное улучшение.

(define (signed-area plist)
  (define (.signed-area plist)
    (cond ((< (length plist) 3) 0)
          (else (+
                 (- (* (first plist) (fourth plist))
                    (* (second plist) (third plist)))
                 (.signed-area (cddr plist))))))
  (* (/ 1 2) (abs (.signed-area plist))))

Решение II - рекурсия хвостового вызова

Это метод, который экономит память и позволяет избежать вложения рекурсивных вызовов для интерпретатора. Так что обычно считается лучшей практикой. Кроме того, вы можете более четко видеть, что происходит между этапами - потому что вам нужно просто сконцентрироваться на acc и на том, что с ним делается на каждом шаге рекурсии, - тогда вы понимаете формулу / процедуру, примененную к результатам каждого отдельного шага. Из-за этих двух причин рекурсивный вызов хвоста является предпочтительным методом для lisp-программистов для формулирования рекурсивных функций.

(define (signed-area plist)
  (define (.signed-area plist acc)         ; introduce accumulator 
    (cond ((< (length plist) 3) (* (/ 1 2) (abs acc)))
          (else (.signed-area (cddr plist) ; in next round remove first pair
                              (+ (- (* (first plist) (fourth plist))
                                    (* (second plist) (third plist)))
                                 acc)))))  ; add shoelace product to accumulator
  (.signed-area plist 0)) ; call inner recursive function with accumulator start value 0
;

Test

Все три определения функций дают правильный результат 2:

(signed-area (list 1 2 3 4 5 6))
;; => 2

Для проверки / тестирования рассчитайте вручную пример:

;; to check, calculate shoelace by hand:
;; visualize:
;; 1 2
;; 3 4
;; 5 6
;
;; and then calculate:
(* (/ 1 2)
   (abs (+ (- (* 1 4)
              (* 2 3))
           (- (* 3 6)
              (* 4 5)))))
;; => 2

Для списка рассылки

(define (signed-area list-of-posn)
  (define (.signed-area list-of-posn acc)         ; introduce accumulator 
    (cond ((< (length list-of-posn) 2) (* (/ 1 2) (abs acc)))
          (else (.signed-area (cdr list-of-posn) ; in next round remove first posn
                              (+ (- (* (posn-x (first list-of-posn)) (posn-y (second list-of-posn)))
                                    (* (posn-x (second list-of-posn)) (posn-y (first list-of-posn))))
                                 acc)))))  ; add shoelace product to accumulator
  (.signed-area list-of-posn 0)) ; call inner recursive function with accumulator start value 0