Н.П. Трифонов, В.Н. Пильщиков - Задания практикума на ЭВМ, страница 2

При этом по степеням X одночлены могут быть неупорядочены, но одночлены одной и той же степени не повторяются (кроме варианта18). За последним одночленом следует пробел — признак конца записи многочлена.(Особый случай: нулевой многочлен записывается как 0).Примеры записи многочленов:7x^30x^8+1−139x+5x^46Если результатом операции является многочлен, то он должен быть распечатан в указанном виде (без нулевых слагаемых, без коэффициентов 1 и без показателей степени 0и 1), но обязательно по убыванию степеней X.В памяти ЭВМ многочлен должен быть представлен в виде однонаправленного списка,в котором каждому одночлену соответствует звено, содержащее степень этого одночлена и его коэффициент. Звенья списка должны быть упорядочены по убыванию степеней, звеньев с нулевыми коэффициентами не должно быть.6Методическое пособиеВарианты 19-22Дана формула, содержащая переменную X (см.

ниже). Требуется ввести эту формулу впамять ЭВМ, преобразовав ее в двоичное дерево (см. ниже), выполнить операцию, указанную в варианте задания, и распечатать полученный результат.Операции над формулами:w19) по заданным формуле и целому числу вычислить значение этой формулыпри значении переменной 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#).

Примеры записиформул:обычная (инфиксная) префикснаяпостфиксная777(a−(b*c))(−a(*bc))(a(bc*)−)((a−b)*c)(*(−ab)c)((ab-)c*)2.2. ТРЕБОВАНИЯ К ПРОГРАММЕ1.В программе должна быть предусмотрена проверка правильности задания исходной информации.2.В вариантах 1-11 в программе должны быть определены процедура выделенияочередного слова из исходной последовательности и процедура вставки слова вупорядоченный список (в дерево поиска).

Кроме того, в вариантах 9-11 должнабыть определена рекурсивная процедура печати слов, входящих в дерево.7Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВМ3.Аналогичные процедуры (выделение очередного одночлена, вставка нового звенав упорядоченный список) должны быть определены в вариантах 12-18.4.В вариантах 19-22 должны быть определены процедура ввода исходной формулыи построения соответствующего двоичного дерева, а также процедура вычислениязначения формулы при заданной величине X (в варианте 19) или процедура печати формулы в нужном виде (варианты 20-22); все эти процедуры должны быть рекурсивными.2.3.

ЛИТЕРАТУРА[1]. Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1985.[2]. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. — М.:Наука, 1988.[3]. Епанешников А.М., Епанешников В.А. Программирование в среде TurboPascal 7.0 — М.: «ДИАЛОГ-МИФИ», 2000.2.4. МЕТОДИЧЕСКИЕ УКАЗАНИЯ1.Вводить последовательность слов, многочлен или формулу следует посимвольно.Конец ввода определяется соответственно по точке, по пробелу или по балансускобок. Ввод целого числа в вариантах 12 и 19 можно осуществлять с помощьюпроцедуры read(n), где n — целочисленная переменная.2.В вариантах задания, где в качестве внутреннего представления используютсясписки, следует упорядочивать списки (по алфавиту или по степеням одночленов)одновременно с вводом слов или одночленов: введенное слово или одночлен следует сразу вставлять на «свое» место в ранее упорядоченный список.3.Для упрощения операций над списками, рекомендуется использовать списки с заглавными звеньями.

В этом случае следует в начале выполнения программы построить список (списки) с одним заглавным звеном.4.В вариантах 1-11 в звеньях списков (вершинах дерева) следует хранить не толькослова, но и дополнительную информацию (порядковый номер слова в исходнойпоследовательности или число его вхождений в эту последовательность). В частности, даже в вариантах 1 и 5 для каждого слова лучше иметь только одно звено,фиксируя в нем число вхождений этого слова в последовательность; при печатиже надо продублировать слово данное число раз. В варианте 9 такой прием является единственно возможным, поскольку в дереве поиска не должно быть нескольких вершин с одним и тем же словом.8Методическое пособиеЗадание 3. ЯЗЫК ПАСКАЛЬ.МЕТОДЫ СОРТИРОВКИ.3.1. ПОСТАНОВКА ЗАДАЧИТребуется реализовать два метода сортировки, определяемых вариантом задания, ипровести их экспериментальное сравнение.Под «сортировкой» понимается упорядочение элементов последовательности X1, X2, ...,Xn (1 ≤ n ≤ 100) по неубыванию, т.е.

такая перестановка элементов, после которой будетвыполняться условие Xi ≤ Xi+1 для всех i. В качестве элементов Xi использовать датывида 26.11.94, 9.5.00 и т.п.Сравнение реализованных методов сортировки нужно проводить на одних и тех же последовательностях. Следует рассмотреть последовательности разной длины (например,n = 10, 20, 50, 100), используя при каждом n по крайней мере следующие исходные расстановки элементов:1) элементы уже упорядочены по неубыванию;2) элементы упорядочены в обратном порядке (по невозрастанию);3) элементы с нечетными индексами упорядочены по неубыванию, а с четнымииндексами — по невозрастанию;4) одна случайная расстановка элементов;5) другая случайная расстановка элементов.Оценку методов производить по следующим двум параметрам:— число сравнений элементов последовательности, выполненных в процессе упорядочения;— число перемещений (перестановок пар элементов или пересылок элементов нановые места — в зависимости от метода), выполненных в процессе упорядочения.Результаты экспериментов оформить в виде двух таблиц, например, такого формата(средние значения округлять до целой части):Название метода сортировки┌────────────────────────────────────────────────────────┐│ n │ параметр │ номер последовательности │ среднее ││|│ 12345 │ значение ││────│─────────────│──────────────────────────│──────────││ 10 │ сравнения │ 9 45 33 25 30 │28│││ перемещения │...│ ...││────│─────────────│──────────────────────────│──────────││ 20 │ сравнения │...│ ...│││ ...│││...└────────────────────────────────────────────────────────┘3.2.

ВАРИАНТЫ ЗАДАНИЯ (методы сортировки)Методы 1-5 — простые, но медленные (с числом сравнений порядка n2), а методы 610 — сложные, но быстрые (порядка n log2n). Названия методов даны по книге [1],9Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВМкроме метода 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] 114121).9) Сортировка простым слиянием ([1] 198-199; [2] 106-111).10) Сортировка естественным слиянием ([1] 193- 197; [2] 112-117).3.3.

ТРЕБОВАНИЯ К ПРОГРАММЕ1.Сравнение двух элементов (дат) должно быть реализовано в виде логическойфункции, а перемещение (пересылка или перестановка) элементов — в виде процедуры. Как побочный эффект, при каждом обращении эти функция и процедурадолжны увеличивать на 1 значения глобальных счетчиков сравнений и перемещений, соответственно. Перед началом каждой сортировки эти счетчики нужно обнулять.(Замечание. Под одним «перемещением» в методах 1, 2, 9 и 10 понимается пересылка элемента на новое место, а в остальных методах — перестановка значенийдвух элементов.)2.Каждый из предложенных методов сортировки должен быть реализован в видепроцедуры от двух параметров: массива (X), в котором вначале находится неупорядоченная последовательность, а в конце работы процедуры должна оказатьсяупорядоченная последовательность, и длины (n) упорядочиваемой последовательности. Эти процедуры должны правильно работать при любом n ≤ 100.Прежде чем проводить эксперименты, следует отладить каждую из этих процедур(например, на двух-трех последовательностях длины 10).Основная программа должна генерировать все необходимые последовательности,обращаться к процедурам сортировки и печатать таблицы результатов.(Замечание.

Для генерации случайных последовательностей можно использоватьфункцию random(k) языка Турбо Паскаль, которая при каждом обращении к ней вкачестве своего значения выдает новое случайное целое число из отрезка [0, k-1].)3.4. ЛИТЕРАТУРА[1]. Кнут Д. Искусство программирования для ЭВМ. Т.3. — М.: Мир, 1978.[2]. Лорин Г. Сортировка и системы сортировки. — М.: Наука, 1983.[3]. Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989.[4]. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль.

— М.:Наука, 1988.10Методическое пособие[5]. Епанешников А.М., Епанешников В.А. ПрограммированиеPascal 7.0 — М.: «ДИАЛОГ-МИФИ», 2000.всредеTurbo3.5. КРАТКОЕ ОПИСАНИЕ МЕТОДОВ СОРТИРОВКИСОРТИРОВКА ВСТАВКАМИИдея методов сортировки вставками состоит в том, что в ранее упорядоченную подпоследовательность X1, X2, ..., Xk − 1 вставляется Xk так, чтобы упорядоченными оказались уже k первых элементов исходной последовательности. В зависимости от способапоиска места для элемента q = Xk различаются следующие методы.1) ПРОСТЫЕ ВСТАВКИ. Если q < Xk − 1, то величина q по очереди сравниваетсяс Xk − 1, Xk − 2, ..., пока не будет найдена такая пара элементов Xi − 1 и Xi, что Xi− 1 ≤ q < Xi.