Алгоритм как процедура

а. Реализуйте этот алгоритм как процедуру reduce-terms , которая принимает в качестве аргументов два списка термов n и d и возвращает список из nn и dd , которые представляют собой n и d , приведенные к наименьшему знаменателю по вышеописанному алгоритму. Напишите, кроме того, процедуру reduce-poly , подобную add-poly , которая проверяет, чтобы два poly имели одну и ту же переменную. Если это так, reduce-poly откусывает эту переменную и передает оставшуюся часть задачи в reduce-terms , а затем прикрепляет переменную обратно к двум спискам термов, которые получены из reduce-terms .

б. Определите процедуру, аналогичную reduce-terms , которая делает то, что делала для целых чисел исходная make-rat :

(define (reduce-integers n d)
  (let ((g (gcd n d)))
    (list (/ n g) (/ d g))))

и определите reduce как обобщенную операцию, которая вызывает apply-generic и диспетчирует либо к reduce-poly (если аргументы — многочлены), либо к reduce-integers (для аргументов типа scheme-number ). Теперь Вы легко можете заставить пакет рациональной арифметики приводить дроби к наименьшему знаменателю, потребовав от make-rat звать reduce прежде, чем сочетать данные числитель и знаменатель в процессе порождения рационального числа. Теперь система обрабатывает рациональные выражения и для целых чисел, и для многочленов. Чтобы проверить программу, попробуйте пример, который приведен в начале этого расширенного упражнения:

(define p1 (make-polynomial 'x '((1 1)(0 1))))
(define p2 (make-polynomial 'x '((3 1)(0 -1))))
(define p3 (make-polynomial 'x '((1 1))))
(define p4 (make-polynomial 'x '((2 1)(0 -1))))

(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))

(add rf1 rf2)

Посмотрите, удалось ли Вам получить правильный ответ, правильно приведенный к наименьшему знаменателю.

Вычисление НОД находится в центре всякой системы, работающей с рациональными числами. Алгоритм, который мы использовали в тексте, хотя математически он естествен, работает очень медленно. Медлительность эта проистекает отчасти из большого количества операций деления, а отчасти из огромного размера промежуточных коэффициентов, которые порождаются в ходе псевдоделения. Одна из активно разрабатываемых областей в теории систем алгебраических манипуляций – построение более быстрых алгоритмов для вычисления НОД многочленов.

---