Вопросы (1110763), страница 2
Текст из файла (страница 2)
Практикум на ЭВМВарианты 12-18Дана символьная запись (см. ниже) многочлена (многочленов) от одной переменной X сцелыми коэффициентами. Требуется ввести этот многочлен в память ЭВМ, преобразовав во внутреннее представление (см. ниже), выполнить операцию, определяемую вариантом задания, и распечатать полученный результат.Операции над многочленами:12) вычислить значение заданного многочлена при заданном целочисленномзначении переменной X;13) проверить, имеет ли заданный многочлен хотя бы один целый корень (такими корнями могут быть только положительные и отрицательные делителисвободного члена, а при нулевом свободном члене корнем является 0);14) проверить на равенство два заданных многочлена;15) получить многочлен, являющийся производной заданного многочлена по переменной X;16) получить многочлен, являющийся суммой двух заданных многочленов;17) получить многочлен, являющийся произведением двух заданных многочленов;18) привести подобные члены в заданном многочлене, в котором могут повторяться одночлены с одними и теми же степенями X.Исходный многочлен от переменной X с целыми коэффициентами записывается какалгебраическая сумма одночленов любого из следующих видов (^ — возведение в степень):aX^k,X^k,aX,Xaгде k и a — целые числа (k ≥ 2, a ≥ 1).
При этом по степеням 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 значения глобальных счетчиков сравнений и перемещений, соответственно. Перед началом каждой сортировки эти счетчики нужно обнулять.(Замечание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
