17) получить многочлен, являющийся произведением двух заданных многочленов;

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

Исходный многочлен от переменной X с целыми коэффициентами записывается как алгебраическая сумма одночленов любого из следующих видов (^ - возведение в степень):

aX^k, X^k, aX, X или a

где k и a - целые числа (k≥2, a≥1). При этом по степеням X одночлены могут быть не упорядочены, но одночлены одной и той же степени не повторяются (кроме варианта 18). За последним одночленом следует пробел - признак конца записи многочлена. (Особый случай: нулевой многочлен записывается как 0).

Примеры записи многочленов:

7x^30

x^8+1-139x+5x^46

Если результатом операции является многочлен, то он должен быть распечатан в указанном виде (без нулевых слагаемых, без коэффициентов 1 и без показателей степени 0 и 1), но обязательно по убыванию степеней X.

В памяти ЭВМ многочлен должен быть представлен в виде однонаправленного списка, в котором каждому одночлену соответствует звено, содержащее степень этого одночлена и его коэффициент. Звенья списка должны быть упорядочены по убыванию степеней, звеньев с нулевыми коэффициентами не должно быть.

Варианты 19-22

Дана формула, содержащая переменную X (см. ниже). Требуется ввести эту формулу в память ЭВМ, преобразовав ее в двоичное дерево (см. ниже), выполнить операцию, указанную в варианте задания, и распечатать полученный результат.

Операции над формулами:

19) по заданным формуле и целому числу вычислить значение этой формулы при значении переменной X, равном этому числу;

20) получить производную заданной формулы по переменной X;

21) напечатать заданную формулу в префиксном виде;

22) напечатать заданную формулу в постфиксном виде.

Под "формулой" понимается запись следующего вида:

<формула> ::= <число> | <переменная> | (<формула><знак><формула>)

<знак> ::= + | - | *

<число> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<переменная> ::= X

Примеры формул:

5

((2*X)+(X-(8+X)))

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

Формулу можно представить в виде двоичного дерева согласно следующим правилам:

- числу или переменной соответствует дерево из одной вершины, содержащей это число или переменную,

- формуле со знаком операции соответствует дерево, корневая вершина которого - знак, левое поддерево - соответствующее представление первого операнда, а правое поддерево - второго операнда.

Префиксной записью формулы (a#b), где # - знак некоторой операции, называется конструкция (#ab), а постфиксной записью - конструкция (ab#). Примеры записи формул:

обычная (инфиксная) префиксная постфиксная

7 7 7

(a-(b*c)) (-a(*bc)) (a(bc*)-)

((a-b)*c) (*(-ab)c) ((ab-)c*)

ТРЕБОВАНИЯ К ПРОГРАММЕ

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

2. В вариантах 1-11 в программе должны быть определены процедура выделения очередного слова из исходной последовательности и процедура вставки слова в упорядоченный список (в дерево поиска). Кроме того, в вариантах 9-11 должна быть определена рекурсивная процедура печати слов, входящих в дерево.

3. Аналогичные процедуры (выделение очередного одночлена, вставка нового звена в упорядоченный список) должны быть определены в вариантах 12-18.

4. В вариантах 19-22 должны быть определены процедура ввода исходной формулы и построения соответствующего двоичного дерева, а также процедура вычисления значения формулы при заданной величине X (в варианте 19) или процедура печати формулы в нужном виде (варианты 20-22); все эти процедуры должны быть рекурсивными.

ЛИТЕРАТУРА

1. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.

2. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988.

3. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 - М.: "ДИАЛОГ-МИФИ", 2000.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

1. Вводить последовательность слов, многочлен или формулу следует посимвольно. Конец ввода определяется соответственно по точке, по пробелу или по балансу скобок. Ввод целого числа в вариантах 12 и 19 можно осуществлять с помощью процедуры read(n), где n - целочисленная переменная.

2. В вариантах задания, где в качестве внутреннего представления используются списки, следует упорядочивать списки (по алфавиту или по степеням одночленов) одновременно с вводом слов или одночленов: введенное слово или одночлен следует сразу вставлять на "свое" место в ранее упорядоченный список.

3. Для упрощения операций над списками, рекомендуется использовать списки с заглавными звеньями. В этом случае следует в начале выполнения программы построить список (списки) с одним заглавным звеном.

4. В вариантах 1-11 в звеньях списков (вершинах дерева) следует хранить не только слова, но и дополнительную информацию (порядковый номер слова в исходной последовательности или число его вхождений в эту последовательность). В частности, даже в вариантах 1 и 5 для каждого слова лучше иметь только одно звено, фиксируя в нем число вхождений этого слова в последовательность; при печати же надо продублировать слово данное число раз. В варианте 9 такой прием является единственно возможным, поскольку в дереве поиска не должно быть нескольких вершин с одним и тем же словом.

ЗАДАНИЕ 3. ЯЗЫК ПАСКАЛЬ.

МЕТОДЫ СОРТИРОВКИ.

ПОСТАНОВКА ЗАДАЧИ

Требуется реализовать два метода сортировки, определяемых вариантом задания, и провести их экспериментальное сравнение.

Под "сортировкой" понимается упорядочение элементов последовательности X₁, X₂, ..., X_n (1≤n≤100) по неубыванию, т.е. такая перестановка элементов, после которой будет выполняться условие X_i ≤ X_i+1 для всех i. В качестве элементов X_i использовать даты вида 26.11.94, 9.5.00 и т.п.

Сравнение реализованных методов сортировки нужно проводить на одних и тех же последовательностях. Следует рассмотреть последовательности разной длины (например, n=10, 20, 50, 100), используя при каждом n по крайней мере следующие исходные расстановки элементов:

1) элементы уже упорядочены по неубыванию;

2) элементы упорядочены в обратном порядке (по невозрастанию);

3) элементы с нечетными индексами упорядочены по неубыванию, а с четными индексами - по невозрастанию;

4) одна случайная расстановка элементов;

5) другая случайная расстановка элементов.

Оценку методов производить по следующим двум параметрам:

- число сравнений элементов последовательности, выполненных в процессе упоря-дочения;

- число перемещений (перестановок пар элементов или пересылок элементов на новые места - в зависимости от метода), выполненных в процессе упорядочения.

Результаты экспериментов оформить в виде двух таблиц, например, такого формата (средние значения округлять до целой части):

Название метода сортировки

----------------------------------------------------------

| n | параметр | номер последовательности | среднее |

| | | 1 2 3 4 5 | значение |

----------------------------------------------------------

| 10 | сравнения | 9 45 33 25 30 | 28 |

| | перемещения | ... | ... |

----------------------------------------------------------

| 20 | сравнения | ... | ... |

| | ... | | |

ВАРИАНТЫ ЗАДАНИЯ (методы сортировки)

Методы 1-5 - простые, но медленные (с числом сравнений порядка n²), а методы 6-10 - сложные, но быстрые (порядка n*log₂n). Названия методов даны по книге [1], кроме метода 4. В скобках указаны номера книг по списку литературы и страницы, где приводятся описания данных методов.

1) Сортировка простыми вставками ([1] 101-103; [3] 95-96).

2) Сортировка бинарными вставками ([1] 103-104; [3] 97-98).

3) Метод пузырька ([1] 130-132; [2] 27-28; [3] 101-102).

4) Челночная сортировка ([2] 30-31).

5) Сортировка простым выбором ([1] 169-171; [2] 15-16; [3] 99-100).

6) Метод Шелла ([1] 105-107; [2] 37-40; [3] 105-107).

7) Быстрая сортировка, рекурсивный вариант ([3] 114-117).

8) Быстрая сортировка, нерекурсивный вариант ([1] 140-144; [2] 88-97; [3] 114-121).

9) Сортировка простым слиянием ([1] 198-199; [2] 106-111).

10) Сортировка естественным слиянием ([1] 193- 197; [2] 112-117).

ТРЕБОВАНИЯ К ПРОГРАММЕ

1. Сравнение двух элементов (дат) должно быть реализовано в виде логической функции, а перемещение (пересылка или перестановка) элементов - в виде процедуры. Как побочный эффект, при каждом обращении эти функция и процедура должны увеличивать на 1 значения глобальных счетчиков сравнений и перемещений, соответственно. Перед началом каждой сортировки эти счетчики нужно обнулять.

(Замечание. Под одним "перемещением" в методах 1, 2, 9 и 10 понимается пересылка элемента на новое место, а в остальных методах - перестановка значений двух элементов.)

2. Каждый из предложенных методов сортировки должен быть реализован в виде процедуры от двух параметров: массива (X), в котором вначале находится неупорядоченная последовательность, а в конце работы процедуры должна оказаться упорядоченная последовательность, и длины (n) упорядочиваемой последовательности. Эти процедуры должны правильно работать при любом n≤100.

Прежде чем проводить эксперименты, следует отладить каждую из этих процедур (например, на двух-трех последовательностях длины 10).

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

(Замечание. Для генерации случайных последовательностей можно использо-вать функцию random(k) языка Турбо Паскаль, которая при каждом обращении к ней в качестве своего значения выдает новое случайное целое число из отрезка [0, k-1].)

ЛИТЕРАТУРА

1. Кнут Д. Искусство программирования для ЭВМ. Том 3. - М.: Мир, 1978.

2. Лорин Г. Сортировка и системы сортировки. - М.: Наука, 1983.

3. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.

4. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988.

5. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 - М.: "ДИАЛОГ-МИФИ", 2000.

КРАТКОЕ ОПИСАНИЕ МЕТОДОВ СОРТИРОВКИ

СОРТИРОВКА ВСТАВКАМИ

Идея методов сортировки вставками состоит в том, что в ранее упорядоченную подпоследовательность X₁, X₂, ..., X_k-1 вставляется X_k так, чтобы упорядоченными оказались уже k первых элементов исходной последовательности. В зависимости от способа поиска места для элемента q=X_k различаются следующие методы.

а) ПРОСТЫЕ ВСТАВКИ. Если q<X_k-1, то величина q по очереди сравнивается с X_k-1, X_k-2, ..., пока не будет найдена такая пара элементов X_i-1 и X_i, что X_i-1≤q<X_i. Это означает, что местом для q является i-я позиция. Поэтому элементы X_i, …, X_k-1 сдвигаются на одну позицию вправо и в освободившуюся i-ю позицию вставляется q.

б) БИНАРНЫЕ ВСТАВКИ. Величина q сравнивается со средним элементом подпоследовательности X₁, X₂, ..., X_k-1. Если q меньше этого элемента, то место для q ищется тем же способом в левой половине подпоследовательности, иначе - в правой половине. Когда место для q будет найдено, правые (от этого места) элементы сдвигаются на одну позицию вправо, а в освободившуюся позицию вставляется q.

СОРТИРОВКА ОБМЕНАМИ

В методах сортировки обменами переставляются элементы неупорядоченных пар, т.е. таких пар, в которых левый элемент больше правого. В зависимости от порядка перебора пар различаются следующие методы.

а) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X₁ и X₂, X₂ и X₃, X₃ и X₄ и т.д.) и в неупорядоченных парах (X_i>X_i+1) переставляются элементы; в результате просмотра всей последовательности ее максимальный элемент окажется на своем окончательном месте - в конце. Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотре последовательности не было ни одной перестановки, то последовательность уже упорядочена и потому следует прекратить сортировку.)

б) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравниваются пары X₁ и X₂, X₂ и X₃ и т.д., но только до обнаружения неупорядоченной пары X_k>X_k+1. В этом случае осуществляется "движение назад": сравниваются и переставляются пары X_k+1 и X_k, X_k и X_k-1 и т.д. до тех пор, пока X_k+1 не попадет на свое место, т.е. пока не окажется упорядоченной подпоследовательность из k+1 первых элементов. Далее возобновляется "движение вперед": сравниваются пары X_k+1 и X_k+2, X_k+2 и X_k+3 и т.д.

СОРТИРОВКА ПРОСТЫМ ВЫБОРОМ

В сортировке простым выбором находится минимальный (максимальный) элемент последовательности и он переставляется с первым (последним) элементом. Далее аналогичная процедура применяется ко всем элементам, кроме первого (последнего). И так далее.

МЕТОД ШЕЛЛА

Пусть k - целое от 1 до n/2. Независимо друг от друга упорядочиваются (одним из описанных выше методов, например, простых вставок) подпоследовательности из элементов, отстоящих друг от друга на k позиций: