2.5. Системы с обобщенными операциями
209
Выражаясь более точно, если P и Q — многочлены, определим O
1
как порядок P
(то ес ть порядок его старшего терма), а O
2
как порядок Q. Пусть c будет коэффициент
старшего терма Q. В таком случае, можно показать, что если мы домножим P на множи-
тель целости (inte gerizing factor) c
1+O
1
−O
2
, то получившийся многочлен можно будет
поделить на Q алгоритмом div-terms, получив результат, в котором не будет никаких
дробей. Операци я домножения делимого на такую константу, а затем деления, иногда
называется псевдоделением (pseudodivision) P на Q. Остаток такого деления называется
псевдоостатком (pseudoremainder).
Упражнение 2.96.
а. Напишите процедуру pseudoremainder-terms, которая работает в точности как remainder-
terms, но только прежде, чем позвать div-terms, домножает делимое на множитель целости,
описанный выше. Модифициру йте gcd-terms так, чтобы она использовала pseudoremainder-
terms, и убедитесь, что теперь в примере из упражнения 2.95 greatest-common-divisor
выдает ответ с целыми коэффициентами.
б. Теперь у НОД целые коэффициенты, но они больше, чем коэффициенты P
1
. Измените gcd-
terms, чтобы она убирала о бщий множитель из коэффициентов ответа путем деления всех коэф-
фициентов на их (целочисленный) НОД.
Итак, вот как привести рациональную функцию к наименьшему знаменателю:
• Вычислите НОД числителя и знаменателя, используя версию gcd-terms из
упражнения 2.96.
• Когда Вы получаете НОД, домножьте числитель и знаменатель на множитель це-
лости, прежде чем делить на НОД, чтобы при делении не получить дробных коэф-
фициентов. В качестве множителя можно использовать старший коэффициент НОД,
возведенный в с тепень 1 + O
1
− O
2
, где O
2
– порядок НОД, а O
1
— максимум из по-
рядков числителя и знаменателя. Так Вы добьетесь того, чтобы деление числителя и
знаменателя на НОД не привносило дробей.
• В результате этой операции Вы получите числитель и знаменатель с целыми ко-
эффициентами. Обычно из-за всех множителей це лости коэффициенты окажутся очень
большими, стало быть, на последнем шаге следует избавиться от лишних множителей,
вычислив (целый) наибольший общий делитель числителя и знаменателя и поделив на
него все термы.
Упражнение 2.97.
а. Реализуйте этот алгоритм как процедуру 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))))