Московский государственный

университет им. М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Трифонов Н.П., Пильщиков В.Н.

Задания практикума на ЭВМ

(1 курс)

Москва

2001

УДК 681.325.5

ББК 22.18

Т67

Трифонов Н.П., Пильщиков В.Н.

Задания практикума на ЭВМ (1 курс). Учебное пособие, 2-е исправленное издание. — М.: МГУ, 2001. — 32 с.

Издательский отдел факультета ВМК (лицензия ЛР №040777 от 23.07.96), Приводятся описания заданий практикума на ЭВМ для студентов 1 курса факультета вычислительной математики и кибернетики МГУ. Эти задания относятся к языку программирования Паскаль и языку ассемблера для персональных компьютеров.

В разработке заданий принимали участие И.А Волкова, Е.В. Зима, В.В. Игнатов, В.Н. Пильщиков, В.И. Родин, Т.В. Руденко, Н.П. Трифонов.

В новом издании исправлены замеченные ошибки и неточности первого издания ( г.), в качестве используемой версии языка Паскаль взят язык Турбо Паскаль 7.0. При подготовке нового издания большую помощь оказала Е.А. Бордаченкова.

Рецензенты:

доц. Баула В.Г.

доц. Корухова Л.С.

Печатается по решению Редакционно-издательского совет факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова.

ISBN 5-89407-102-Х © Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, Замечания по данной электронной версии присылайте на сmсmsu.infо@gmail.cоm Методическое пособие Задание 1. ЯЗЫК ПАСКАЛЬ. ВЫЧИСЛЕНИЕ КОРНЕЙ

УРАВНЕНИЙ И ОПРЕДЕЛЕННЫХ

ИНТЕГРАЛОВ

1.1. ПОСТАНОВКА ЗАДАЧИ С заданной точностью вычислить площадь плоской фигуры, ограниченной тремя кривыми, уравнения которых y = f1(x), y = f2(x) и y = f3(x) определяются вариантом задания.

При решении задачи необходимо:

с некоторой точностью eps1 вычислить абсциссы точек пересечения кривых, используя предусмотренный вариантом задания метод приближенного решения уравнения F(x)=0; отрезки, где программа будет искать точки пересечения и где применим используемый метод, определить вручную;

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

Величины 1 и 2 подобрать вручную так, чтобы гарантировалось вычисление площади фигуры с точностью.

1.2. ВАРИАНТЫ ЗАДАНИЯ Во всех вариантах = 0.001.

А. Уравнения кривых y = fi(x):

f1 = 2x + 1 f 2 = x 1) f3 = (1 x)/ 2) f1 = 3(0.5/(x + 1) + 1) f2 = 2.5x 9.5 f3 = 5/x (x > 0) 3) f1 = exp(x) + 3 f2 = 2x 2 f3 = 1/x 4) f1 = exp(x) + 2 f2 = 1/x f3 = 2(x + 1)/ 2 x 5) f1 = 0.35x 0.95x + 2.7 f2 = 3 +1 f3 = 1/(x + 2) f2 = (x 2) 6) f1 = 0.6x + 3 f3 = 3/x 7) f1 = ln(x) f2 = 2x + 14 f3 = 1/(2 x)+ 8) f1 = exp(x) + 2 f2 = 2x + 8 f3 = 5/x f1 = 3/((x 1)2 + 1) 9) f2 = sqrt (x + 0.5) f3 = exp(x) f1 = 1 + 4/(x2 + 1) f 2 = x3 f3 = 2x 10) Б. Методы приближенного решения уравнений:

1) метод деления отрезка пополам;

2) метод хорд (секущих);

3) метод касательных (Ньютона);

Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВМ 4) комбинированный метод (хорд и касательных).

В. Квадратурные формулы:

1) формула прямоугольников;

3) формула Симпсона (парабол).

1.3. ТРЕБОВАНИЯ К ПРОГРАММЕ 1. В программе предусмотреть печать как площади заданной фигуры, так и абсцисс точек пересечения кривых.

2. Описать в программе процедуру root (f, g, a, b, eps1, x), вычисляющую с точностью 1 корень x уравнения f (x) = g (x) на отрезке [a, b]. (Если используется метод касательных или комбинированный метод, то у root должны быть еще параметры 3. Описать в программе функцию integral (f, a, b, eps2), вычисляющую с точностью 2 величину определенного интеграла от функции f (x) на отрезке [a, b].

4. Процедуру root и функцию integral следует предварительно протестировать.

1.4. ЛИТЕРАТУРА [1]. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Т.1 — М.:

Наука, 1985.

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

Наука, 1988.

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

1.5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ 1. Для корректного применения предложенных методов приближенного решения уравнения F(x) = 0 (где F(x) = f (x) g (x)) необходимо найти отрезок [a, b], на котором уравнение имеет ровно один корень. Достаточное условие для этого таково:

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

2. В методе деления отрезка пополам определяется средняя точка c отрезка [a, b] и из двух отрезков [a, c] и [c, b] выбирается тот, на концах которого функция F(x) имеет разные знаки. К выбранному отрезку применяется та же процедура. Процесс деления отрезков прекращается, когда длина очередного отрезка станет меньше требуемой точности ; за корень уравнения можно принять любую точку 3. В остальных трех методах следует различать два случая:

случай 1 — первая и вторая производные функции F(x) имеют одинаковый знак случай 2 — эти производные имеют разные знаки.

Методическое пособие В методе хорд концы (a, F(a)) и (b, F(b)) кривой y = F(x) соединяются прямой линией и определяется точка пересечения этой линии с осью абсцисс:

Далее выбирается отрезок [c, b] в случае 1 или отрезок [a, c] в случае 2 и к нему применяется та же процедура. Тем самым происходит постепенное приближение к искомому корню слева (в случае 1) или справа (в случае 2).

В методе касательных проводится касательная к кривой y = F(x) в точке (b, F(b)) в случае 1 или в точке (a, F(a)) в случае 2 и определяется точка c пересечения этой касательной с осью абсцисс:

где d = b в случае 1 и d = a в случае 2. Далее проводится касательная к кривой в точке (c, F(c)) и процедура повторяется. Тем самым происходит приближение к искомому корню справа (в случае 1) или слева (в случае 2).

В методах хорд и касательных можно использовать следующий критерий завершения процесса приближения к корню. Если приближение «идет» слева, то на очередном шаге надо сравнить величины F(c) и F(c + ): если они одного знака, то процесс продолжается, иначе на отрезке [c, c + ] имеется корень и потому процесс завершается. При приближении справа надо проверять знаки F(c ) и В комбинированном методе одновременно применяется метод хорд и метод касательных, в связи с чем приближение к корню происходит с двух сторон. Критерий окончания — длина очередного отрезка меньше.

4. При использовании метода хорд, метода касательных или комбинированного метода процедура root должна самостоятельно распознавать, какой из двух случаев, указанных в п. 2, имеет место при текущем обращении к ней. Это можно сделать проверкой следующих двух условий:

— функция возрастает или убывает;

— график функции расположен выше хорды, соединяющей концы графика, или Поскольку производные F'(x) и F"(x) на отрезке [a, b] не меняют знак, для проверки первого условия достаточно сравнить F(a) с 0 (при F(a) < 0 функция возрастает). Для проверки же второго условия надо сравнить в какой-то внутренней точке отрезка значения функции и хорды; например, если взять среднюю точку (a + b)/ расположен выше хорды. Если функция возрастает и ее график расположен ниже хорды или если функция убывает и ее график расположен выше хорды, то имеет место случай 1, иначе — случай 2.

5. Квадратурные формулы для приближенного вычисления интеграла I от функции F(x) на отрезке [a, b] имеют следующий вид (n — число разбиений отрезка [a, b]):

Формула прямоугольников:

I In = h(F0 + F1+...+Fn-1), где Fi = F(a + (i + 0.5)h), h = (b – a)/n Формула трапеций:

Формула Симпсона (n — чётное):

I In = h/3 (F0 + 4F1 + 2F2 + 4F3 +... + 4Fn-3 + 2Fn-2 + 4Fn-1 + Fn), Для обеспечения требуемой точности при приближенном вычислении интеграла I по квадратурной формуле нужно подобрать соответствующее число n разбиений отрезка интегрирования. Известны формулы, выражающие n через, но в эти формулы входят производные подынтегральной функции, что неудобно на практике. Поэтому для достижения требуемой точности обычно используется следующий метод: берется некоторое начальное число разбиений n0 (например, или 20) и последовательно вычисляются значения In при n, равном 2n0, 4n0, 8n0 и т.д. Известно правило Рунге (для формул прямоугольников и трапеций p = 1/3, для формулы Симпсона p = 1/15). Согласно этому правилу, когда на очередном шаге величина p |In I2n| окажется меньше, в качестве приближенного значения для I можно взять In или, что лучше, I2n.

7. При реализации функции integral следует учитывать, что в формулах трапеций и Симпсона в сумму I2n входят значения Fi, вычисленные ранее для суммы In, поэтому их не следует перевычислять заново.

8. В процедуре root и функции integral используются параметры-функции (f, g и др.).

В языке Турбо Паскаль такие параметры описываются следующим образом.

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

(вместо TP и x можно использовать любые другие имена), в который автоматически включаются все описанные в программе вещественные функции от одного вещественного аргумента, а затем имя данного типа нужно указать в спецификации формального параметра-функции, например:

procedure root (f, g: TF; a, b, eps1: real; var x: real);

При обращении же к процедуре root или функции integral указываются, как обычно, имена фактических функций (не стандартных!), например:

root(f1, f2, -0.1, 3.5, 0.0001, x12);

Что касается самих фактических функций (f1, f2 и др.), то перед их описанием необходимо разместить директиву {$F+} транслятору:

function f1 (x: real): real; begin f1:=ln(x) end;

function f2 (x: real): real; begin f2:=2*x+14 end;

Методическое пособие Задание 2. ЯЗЫК ПАСКАЛЬ.

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.

2.1. ПОСТАНОВКА ЗАДАЧИ Варианты 1- Дана непустая последовательность слов, в каждом из которых содержится от 1 до 6 заглавных латинских букв; соседние слова разделены запятой, за последним словом следует точка.

Требуется ввести эту последовательность слов в память ЭВМ, преобразовав ее во внутреннее представление (см. ниже), а затем распечатать в алфавитном порядке:

1) все слова последовательности;

2) все слова с указанием для каждого из них его порядкового номера в исходной последовательности;

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

4) все различные слова с указанием для каждого из них порядкового номера его первого вхождения в исходную последовательность;

5) сначала все однобуквенные слова, затем все двухбуквенные слова и т.д.;

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

7) сначала все различные однобуквенные слова с указанием для каждого из них числа его вхождений в исходную последовательность, затем аналогичным образом все различные двухбуквенные слова и т.д.;

8) сначала все различные однобуквенные слова с указанием для каждого из них порядкового номера его первого вхождений в исходную последовательность, затем аналогичным образом все различные двухбуквенные слова и т.д.;

9) та же задача, что и в варианте 1;

10) та же задача, что и в варианте 3;

11) та же задача, что и в варианте 4.

В качестве внутреннего представления последовательности слов использовать:

— в вариантах 1-4 — однонаправленный список из слов, упорядоченных по алфавиту;

— в вариантах 5-8 — массив из 6 списков, в k-ом из которых хранятся kбуквенные слова, упорядоченные по алфавиту;

— в вариантах 9-11 — двоичное дерево поиска (в нем слева от каждой вершиныслова располагаются только те слова, что предшествуют ему по алфавиту, а справа — следующие за ним по алфавиту).

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

Операции над многочленами:

12) вычислить значение заданного многочлена при заданном целочисленном 13) проверить, имеет ли заданный многочлен хотя бы один целый корень (такими корнями могут быть только положительные и отрицательные делители свободного члена, а при нулевом свободном члене корнем является 0);

14) проверить на равенство два заданных многочлена;

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

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

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

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

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

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

(Особый случай: нулевой многочлен записывается как 0).

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

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

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

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

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

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

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

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

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

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

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

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

— числу или переменной соответствует дерево из одной вершины, содержащей это число или переменную, — формуле со знаком операции соответствует дерево, корневая вершина которого — знак, левое поддерево — соответствующее представление первого операнда, а правое поддерево — второго операнда.

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

2.2. ТРЕБОВАНИЯ К ПРОГРАММЕ 1. В программе должна быть предусмотрена проверка правильности задания исходной информации.

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

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

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

2.3. ЛИТЕРАТУРА [1]. Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1985.

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

Наука, 1988.

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

2.4. МЕТОДИЧЕСКИЕ УКАЗАНИЯ 1. Вводить последовательность слов, многочлен или формулу следует посимвольно.

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

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

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

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

Методическое пособие Задание 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 параметр номер последовательности среднее 3.2. ВАРИАНТЫ ЗАДАНИЯ (методы сортировки) Методы 1-5 — простые, но медленные (с числом сравнений порядка n2), а методы 6сложные, но быстрые (порядка n log2n). Названия методов даны по книге [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Сортировка простым слиянием ([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.

Методическое пособие [5]. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 — М.: «ДИАЛОГ-МИФИ», 2000.

3.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. Это означает, что местом для q является i-я позиция. Поэтому элементы Xi, …, Xk 1 сдвигаются на одну позицию вправо и в освободившуюся i-ю позицию вставляется q.

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

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

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

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

1) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X1 и X2, X2 и X3, X3 и X4 и т.д.) и в неупорядоченных парах (Xi > Xi+1) переставляются элементы; в результате просмотра всей последовательности ее максимальный элемент окажется на своем окончательном месте - в конце.

Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотре последовательности не было ни одной перестановки, то последовательность уже упорядочена и потому следует прекратить сортировку.) 2) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравниваются пары X1 и X2, X2 и X3 и т.д., но только до обнаружения неупорядоченной пары Xk > Xk+1. В этом случае осуществляется «движение назад»: сравниваются и переставляются пары Xk + 1 и Xk, Xk и Xk 1 и т.д. до тех пор, пока Xk + не попадет на свое место, т.е. пока не окажется упорядоченной подпоследовательность из k + 1 первых элементов. Далее возобновляется «движение вперед»: сравниваются пары Xk + 1 и Xk + 2, Xk + 2 и Xk + 3 и т.д.

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

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

МЕТОД ШЕЛЛА

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

Затем k уменьшается и процесс повторяется заново. Последний шаг обязательно должен быть выполнен при k = 1.

Значение k можно менять разными способами, один из них таков: вначале k равно (целой части от) n/2, а затем k каждый раз уменьшается вдвое.

БЫСТРАЯ СОРТИРОВКА

Выбирается некоторый элемент (например, средний) и все элементы последовательности переставляются так, чтобы выбранный элемент оказался на своем окончательном месте, т.е. чтобы слева от него были только меньшие или равные ему элементы, а справа — только большие или равные. Затем этот же метод применяется к левой и правой частям последовательности, на которые ее разделил выбранный элемент. (Замечание:

если в части оказалось два-три элемента, то упорядочивать ее следует более простым способом.) Требуемая перестановка элементов выполняется так. Выбранный элемент копируется в некоторую переменную q. Последовательность просматривается слева направо, пока не встретится элемент, больший или равный q, а затем просматривается справа налево до элемента, меньшего или равного q. Оба этих элемента меняются местами, после чего просмотры с обоих концов последовательности продолжаются со следующих элементов, и т.д. В итоге выбранный элемент окажется в той позиции, где просмотры сошлись, это и есть его окончательное место.

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

СОРТИРОВКА СЛИЯНИЕМ

Основная идея такой сортировки — разделить последовательность на уже упорядоченные подпоследовательности (назовем их «отрезками») и затем объединять эти отрезки во все более длинные упорядоченные отрезки, пока не получится единая упорядоченная последовательность. Отметим, что при этом необходима дополнительная память (массив Y [1..n]).

Различаются следующие варианты сортировки слиянием.

1) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X1 и X2, из X и X4,...), которые переносятся в массив Y. На втором этапе соседние двухэлементные отрезки (Y1, Y2 и Y3, Y4; Y5, Y6 и Y7, Y8;...) объединяются в отрезки из 4 элементов, которые записываются в массив X. На третьем этапе строятся отрезки из 8 элементов, и они заносятся в массив Y, и т.д.

2) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию) отрезок в начале массива X и наиболее длинный (также по неубыванию, но при просмотре справа налево) отрезок в конце массива, и они сливаются в Методическое пособие один отрезок, который записывается в начало массива Y. Затем сливаются следующие максимально длинные отрезки с обоих концов, и полученный отрезок записывается (справа налево) в конец массива Y. Третьи по порядку отрезки после слияния записываются снова в начало Y (вслед за первым объединенным отрезком), четвертые — в конец Y (перед вторым объединенным отрезком) и т.д. Первый этап сортировки оканчивается, когда все элементы из X будут перенесены в массив Y. На втором этапе применяется та же процедура, только массивы X и Y меняются ролями. И так далее.

Замечание: в обоих вариантах следует учитывать, что в конце концов упорядоченные элементы должны оказаться в массиве X.

Задание 4. ЯЗЫК ПАСКАЛЬ. ИНТЕРФЕЙС

ПРОГРАММЫ СОРТИРОВКИ.

4.1. ПОСТАНОВКА ЗАДАЧИ Требуется дополнить программу сортировки, реализованную в задании 3, подсистемой диалогового взаимодействия с пользователем (интерфейсом), которая с помощью экранных окон, меню и других средств упрощает общение пользователя с этой программой. Работу с экраном подсистема должна осуществлять в текстовом режиме.

Объединенная система должна предусматривать следующие возможности.

— Пользователь должен иметь возможность выбрать из нескольких предъявленных ему методов сортировки тот метод, которым затем будут упорядочиваться последовательности.

— Пользователь должен иметь возможность задавать свою длину последовательностей, которые будут упорядочиваться выбранным методом.

— В системе должна быть предусмотрена возможность работы в двух режимах — отладки и счета. В режиме отладки пользователь сам вводит элементы (даты) последовательности, которая должна быть упорядочена, а в ответ система демонстрирует пошаговую работу процедуры сортировки для этой последовательности (это нужно для показа правильности работы процедуры). В режиме счета система должна работать так же, как и в задании 3: должна сформировать несколько последовательностей заданной длины, отсортировать их и вывести на экран таблицу результатов.

— Система должна позволять пользователю менять сделанный им ранее выбор (метода, длины или режима) и должна повторять свою работу при новом выборе.

— При вводе длины и элементов последовательности пользователь должен иметь возможность редактировать вводимую информацию.

4.2. ВОЗМОЖНЫЕ СЦЕНАРИИ РАБОТЫ С СИСТЕМОЙ

Ниже описаны два возможных сценария работы пользователя с системой. Любой из них можно взять за основу и со своими изменениями реализовать в задании.

Сценарий 1.

Этап 1. Выбор метода.

Работа системы начинается с очистки экрана и показа на нем списка названий различных (не менее 4-5) методов сортировки. Пользователь выбирает один из них либо прекращает работу с системой.

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

Методическое пособие Одновременно с меню методов на экране (в его нижней строке) должен высвечиваться текст, подсказывающий пользователю, что он должен сейчас делать, какие клавиши может нажимать и что они означают. Подсказка может быть, например, такой:

ВЫБЕРИТЕ МЕТОД:,–сдвиг Enter-выбор Esc-выход Нажатие пользователем клавиши Enter означает, что он выбрал тот метод, название которого сейчас выделено. (Замечание: поскольку в системе реализовано лишь два метода сортировки, то при выборе нереализованного метода система должна как-то сообщить об этом, например звуковым сигналом или выдачей сообщения «Метод не реализован»

и позволить пользователю выбрать иной метод. Желательно реализованные методы как-то пометить, например звездочкой.) Нажатие клавиши Esc означает конец работы с системой.

На этом этапе система не должна реагировать на другие клавиши, а курсор должен быть невидимым.

Этап 2. Выбор режима.

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

Запрос режима может быть реализован следующим образом. В свободной части экрана появляется окно с текстом «РЕЖИМ: ОТЛАДКА» (см. рис. 1). Если пользователь нажимает клавишу пробела, тогда слово «ОТЛАДКА» заменяется на слово «СЧЕТ»; при новом нажатии этой клавиши снова появляется слово «ОТЛАДКА» и т.д. Нажатие клавиши Enter означает выбор того режима, название которого указано сейчас в окне.

Допустимо также нажатие клавиши Esc, что означает отказ от выбора режима и возврат на предыдущий этап (с удалением окна режима и восстановлением подсказки, соответствующей предыдущему этапу). На иные клавиши система в это время не должна реагировать. Курсор должен быть невидимым.

Этап 3. Выбор длины.

При любом выбранном режиме система далее спрашивает у пользователя, последовательности какой длины он желает упорядочивать. В режиме счета длина может меняться от 1 до 100, а в режиме отладки — от 1 до 15.

Запрос длины можно реализовать так. На экране появляется окно с текстом «ДЛИНА