редей, можно воспользоваться представлением на базе связного списка либо представлением на базе массива. Программа 4.25 - это реализация, в которой используется представление на базе массива; реализация на базе связного списка остается на самостоятельную проработку (см. упр. 4.78).

Для сложения (add) двух полиномов складываются их коэффициенты. Если полиномы представлены в виде массивов, функция add, как показано в программе 4.25, равнозначна одиночному циклу по этим массивам. Для умножения (multiply) двух полиномов применяется элементарный алгоритм, основанный на законе распределения. Один полином умножается на каждый член другого, результаты располагаются так, чтобы степени х соответствовали друг другу, и затем складываются для получения окончательного результата. В следующей таблице кратко показывается этот вычислительный процесс для (1 - X + X V 2 - X V 6 )(1 + х + х + х ):

х х

1-Х + -

о X X

+Х-Х +----

2 6

о э X X

+ х-х+---

-.5 6 -j 4 X X

х-х---

2 3 л 4 5 6 , X X 2х X X

1+-+---+---

2 3 3 3 6

Время, необходимое для умножения таким способом двух полиномов, по-видимому, пропорционально Л Отыскать более быстрый алгоритм рещения этой задачи весьма непросто. Эта тема рассматривается более подробно в части 8, где будет показано, что время, необходимое для рещения такой задачи с помощью алгоритма разделяй-и-властвуй , пропорционально N, а время, необходимое для ее рещения с помощью быстрого преобразования Фурье, пропорционально N IgTV.

Программа 4.24 Интерфейс АТД Полином

Для того чтобы можно было задавать коэффициенты различных типов, в этом интерфейсе АТД Полином используется шаблон. Здесь также перегружаются бинарные операции + и *, поэтому в арифметических выражениях такие операции можно задавать и для полиномов. Конструктор, вызванный с аргументами с и N, создает полином, соответствующий выражению сх

template <class НшпЬег> class POLY {

private:

программный код, зависящий оф реализахии public:

POLY<Number>(Number, int);

float eval(float) const;

friend POLY operator+(POLY &, POLY &) ;

friend POLY operator* (POLY &, POLY &) ;

В реализации функции evaluate (вычислить) из программы 4.25 используется эффективный классический алгоритм, известный как алгоритм Горнера (Homers algorithm). Самая простая реализация этой функции заключается в непосредственном вычислении выражения с использованием функции, вычисляющей х. При таком подходе требуется время с квадратичной зависимостью от 7V. В более сложной реализации значения х запоминаются в таблице и затем используются при непосредственных вычислениях. В данной ситуации требуется дополнительный объем памяти, линейно зависящий от N. Алгоритм Горнера - это прямой оптимальный линейный алгоритм, основанный на следующем использовании круглых скобок:

ах + ах + ах +ах + Oq ~ (((4 з) 2) i)

Алгоритм Горнера часто представляют как ловкий прием, экономящий время, но в действительности - это первый вьщающийся пример элегантного и эффективного алгоритма, который сокращает время, необходимое для выполнения этой важной вычислительной задачи, делая его не квадратично, но линейно зависимым от N. Преобразование строк с ASCII-символами в целые числа, выполняемое в программе 4.5, является разновидностью алгоритма Горнера. Мы снова встретимся с алгоритмом Горнера в главе 14 и части 5, где он выступает в качестве основы для важного вида вычислений, относящихся к некоторым реализациям таблиц символов и поиску строк.

Программа 4.25 Реализация АТД Полином на базе массива

В этой реализации АТД для полиномов представление данных состоит из степени и указателя на массив коэффициентов. Это не АТД первого класса: клиентские программы должны знать, что возможна утечка памяти, а семантика копирования заключается в копировании указателей (см. упр. 4.79).

template <class Number> class POLY {

private:

int n; Number *a; public:

POLY<Number>(Number c, int N)

{ a = new Number [N+1]; n = N+1; a[N] = c; for (int i = 0; i < N; i++) a[i] = 0;

float eval (float x) const { double t = 0.0;

for (int i = n-1; i >= 0; i -)

t = t*x + a[i] ; return t;

friend POLY operator+(POLY 4p, POLY &q) { POLY t(0, p.n>q.n ? p.n-1 : q.n-1); for (int i = 0; i < p.n; i++)

t.a[i] += p.a[i]; for (int j = 0; j < q.n; j++)

t.a[j] += q.a[j]; return t;

friend POLY operator* (POLY 4p, POLY 4q) { POLY t(0, (p.n-l) + (q.n-l)) ; for (int i = 0; i < p.n; i++) for (int j = 0; j < q.n; j++) t.a[i+j] += p.a[i]*q.a[j] ; return t;

В ходе выполнения перегруженных операций + и * создаются новые полиномы, поэтому данная реализация связана с утечкой памяти. Утечку памяти можно легко ликвидировать, добавляя в реализацию конструктор копирования, перегруженную операцию присваивания и деструктор. Так бы стоило и поступить в случае полиномов очень больших размеров, обработки огромного количества небольших полиномов, а также создания АТД для использования в каком-нибудь приложении (см. упр. 4.79).

Использование в реализации АТД Полином представления на базе массива - это, как обычно, лишь одна из возможностей. Если показатели степени очень большие, а членов в полиномах немного, то представление на базе связного списка может оказаться более подходящим. Например, не стоило бы применять программу 4.25 для выполнения такого умножения:

+ Х )(1 + Х *) = 1+ у* дДОООООО jOOOOOO

поскольку в ней будет использоваться массив с вьщеленным пространством под миллионы неиспользуемых коэффициентов. В упражнении 4.78 вариант со связным списком рассматривается более подробно.

Упражнения

о 4.78 Напишите реализацию для приведенного в тексте АТД Полином (программа 4.24), в которой в качестве базовой структуры данных используются связные списки. Списки не должны содержать узлов, соответствующих членам с нулевыми коэффициентами.

о 4.79 Устраните утечку памяти в программе 4.25, добавив в нее конструктор копирования, перегруженную операцию присваивания и деструктор.

[> 4.80 Добавьте перегруженные операции += и *= в АТД Полином из программы 4.25.

о 4.81 Расширьте рассмотренный в главе АТД Полином , включив в него операции интегрирования и дифференцирования полиномов.

4.82 Модифицируйте полученный АТД Полином из упражнения 4.81 так, чтобы в нем игнорировались все члены с экспонентами, большими или равными целому числу М, которое поступает в клиентскую программу во время инициализации.

4.83 Расширьте АТД Полином из упражнения 4.81 так, чтобы он включал деление и сложение полиномов.

4.84 Разработайте АТД, который позволяет клиентским программам выполнять сложение и умножение целых чисел произвольной точности.