LINUX.ORG.RU

Racket Scheme. Рекурсивное деление полиномов с остатков (через списки)

 ,


0

2

Привет. Решил поработать с полиномами и списками в Racket и столкнулся с задачей деления. Попробовал реализовать и пока получается не очень. Допустим, есть 2 полинома: 2 + 3х -х^3 + x^4 и 8 - 3х + 4х^2 + x^3, 1ый полином делим на 2ой. В качестве параметра функции я указываю 2 листа (это мои коэффициенты), то есть (pa/pb(list 2 3 0 -1 1)(list 8 -3 4 1 0)), а ответом должны быть листы результат полинома и остаток, ну или все в один список. Я реализовал программу деления почленно, но это не верно, так как оно делается по другому и я не могу придумать алгоритм правильного деления с рекурсией.

(define pa/pb
  (lambda (pol1 pol2)
    (if (null? pol1)
        pol2
        (if (null? pol2)
            pol1
     (cons (/ (car pol1) (car pol2))
           (pa/pb (cdr pol1) (cdr pol2))
     )
    )
   )
  )
)

(define (pa/pb pa pb)
  (cond
   ((and (null? pa) (null? pb))
    '())
   ((null? pa) pb)
   ((null? pb) pa)
   (else (cons (/ (car pa) (car pb))
	       (pa/pb (cdr pa) (cdr pb))))))

Ты вот это хотел?

Лучше это написать через zip и map, ящитаю. Рекурсия тут явно не хвостовая.

anonymous ()
Ответ на: комментарий от Wonka

У меня вот получилось немного с Guile и C покодить по мелочи, батареек маловато, но чутка жить можно. У одного местного был мост для Common Lisp в C#, он с ним живёт.

SICP дочитать не получилось.

Если хочешь, можешь оставить email или tox, можно будет поговорить.

anonymous ()
Ответ на: комментарий от monk

В постановке задачи не говорится, что ответ должен быть полиномом. Говоря о делении полиномов обычно подразумевают деление наподобие (x^2 - 1) / (x^2 - 2x + 1) = (x + 1) / (x - 1) = x / (x - 1) + 1 / (x - 1).

Siborgium ★★★ ()
Ответ на: комментарий от Siborgium

Прошу прощения, видимо я не точно расписал постановку с результатом. Допустим, есть 2 полинома: 2 + 3х -х^3 + x^4 и 8 - 3х + 4х^2 + x^3, 1ый полином делим на 2ой. В качестве параметра функции я указываю 2 листа (это мои коэффициенты), то есть (pa/pb(list 2 3 0 -1 1)(list 8 -3 4 1 0)), а ответом должны быть листы результат полинома и остаток, ну или все в один список. Я реализовал программу деления почленно, но это не верно, так как оно делается по другому и я не могу придумать алгоритм правильного деления с рекурсией.

Wonka ()
Ответ на: комментарий от Wonka

Вроде так:

(define (pa/pb pol1 pol2)
  (define n (- (length pol1) (length pol2)))
  (cond
    [(< n 0)
     (values null pol1)]
    [else
     (define k (/ (last pol1) (last pol2)))
     (define-values (result rest) (pa/pb (pa-pb pol1 (pa* pol2 k n)) pol2))
     (values (append result (list k)) rest)]))

(define (pa* pol k n)
  (append (build-list n (lambda _ 0))
          (map (lambda (x) (* x k)) pol)))

(define (pa-pb pol1 pol2)
  (cond
    [(null? pol2) pol1]
    [(null? pol1) (pa* pol2 -1)]
    [(and (= 1 (length pol2) (length pol1))
          (= (car pol1) (car pol2)))
     null]
    [else
     (cons (- (car pol1) (car pol2)) (pa-pb (cdr pol1) (cdr pol2)))]))
monk ★★★★★ ()
Ответ на: комментарий от monk

Последнюю функцию можно сократить до

(define (pa-pb pol1 pol2)
  (if (null? (cdr pol1))
      null
      (cons (- (car pol1) (car pol2)) (pa-pb (cdr pol1) (cdr pol2)))))

По использованию в неё гарантированно приходят непустые списки одинаковой длины. И старший член гарантированно в разности будет нулевой.

monk ★★★★★ ()
Ответ на: комментарий от monk

Оптимизированный вариант без лишних проходов по списку и позволяющий вызывать и как (pa/pb(list 2 3 0 -1 1)(list 8 -3 4 1 0))

(define (pa/pb pol1 pol2)
  (define (drop-zeroes pol n)
    (if (= (car pol) 0) (drop-zeroes (cdr pol) (sub1 n)) (values pol n)))
  (define (rev-n pol [acc null] [n 0])
    (if (null? pol) (drop-zeroes acc n) (rev-n (cdr pol) (cons (car pol) acc) (add1 n))))
  (define-values (r1 n1) (rev-n pol1))
  (define-values (r2 n2) (rev-n pol2))
  (match-define (cons a an) r2)
  (define zeroes (in-cycle (in-value 0)))
  (let loop ([r1 r1] [n (- n1 n2)])
    (cond
      [(< n 0)
       (values null (reverse r1))]
      [else
       (define k (/ (car r1) a))
       (define-values (result rest) (loop (for/list ([x (cdr r1)]
                                                     [y (in-sequences (map (curry * k) an) zeroes)])
                                            (- x y))
                                          (sub1 n)))
       (values (cons k result) rest)])))
monk ★★★★★ ()