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

А что не так? В смысле, что ожидается, что получается?

Например, у него если (а, b) поделить на (c, d), то получится (a/c + b/d), т.е. деление вышло почленное.

(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, ящитаю. Рекурсия тут явно не хвостовая.

Да, я смог сделать деление почленно, но это не верный алгоритм, не знаю как правильно сделать.

Судя по скобочкам в стиле Си, лисп учишь не сам?

Параллельно с C#

Но шарп уже давно учу, а за лисп недавно сел

Можно было и без zip, просто map выдавала бы ошибку на разных размерах.

(map / '(2 4 6) '(1 2 3 4))

Есть перспективы или для общего?

Спасибо большое, пойду по Вашему способу прогоню и посмотрю как работает и разберусь.

Пока для общего, но интересно поделать и глянуть что можно реализовывать.

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

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

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

А должно что получиться? Ответ ведь полиномом не будет.

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

Прошу прощения, видимо я не точно расписал постановку с результатом. Допустим, есть 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)), а ответом должны быть листы результат полинома и остаток, ну или все в один список. Я реализовал программу деления почленно, но это не верно, так как оно делается по другому и я не могу придумать алгоритм правильного деления с рекурсией.

Да, я понял, что не правильно указал постановку с ответом, я уточнил, если что :)

https://www.math10.com/ru/vysshaya-matematika/delenie-polinomov.html

Там алгоритм нарисован, его явно подольше пилить.

Вроде так:

(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)))]))

Только предполагается, что степень полинома равна длине списка. То есть запускать не как (pa/pb(list 2 3 0 -1 1)(list 8 -3 4 1 0)), а как (pa/pb(list 2 3 0 -1 1)(list 8 -3 4 1))

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

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

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

Оптимизированный вариант без лишних проходов по списку и позволяющий вызывать и как (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)])))