WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

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

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

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

(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.

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



Похожие работы:

«Федеральное агентство по образованию ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ Кафедра электронных приборов (ЭП) Орликов Л.Н. ТЕХНОЛОГИЯ МАТЕРИАЛОВ И ИЗДЕЛИЙ ЭЛЕКТРОННОЙ ТЕХНИКИ Учебное пособие 2006 Учебное пособие рассмотрено и рекомендовано к изданию методическим советом кафедры электронные приборы ТУСУР _2006 г. Развитие научно-технического прогресса поставило задачу резкого усложнения техники и технологии на базе применения ЭВМ. Большинство явлений,...»

«Н. Н. Непейвода, И. Н. Скопин ОСНОВАНИЯ ПРОГРАММИРОВАНИЯ УДК 519.682 Непейвода Н. Н., Скопин И. Н. Основания программирования Книга представляет собой первое издание в серии, предназначенной для студентов, готовящихся к работе по современным информационным технологиям, и специалистов в данной области. Рекомендуется как для первокурсников, уже имеющих начальное знакомство с программированием, так и для специалистов, имеющих лишь практический опыт и желающих получить более основательные...»

«Негосударственное образовательное учреждение высшего профессионального образования Московский экономико-правовой институт (НОУ ВПО МЭПИ) Кафедра социально-гуманитарных, естественнонаучных и математических дисциплин РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ МАКРОЭКОНОМИКА образовательная программа направления подготовки 080100.62 - экономика Квалификация (степень) выпускника - бакалавр экономики Москва 2013 СОДЕРЖАНИЕ 1. Цели и задачи дисциплины 2. Место дисциплины в структуре ООП ВПО 3. Компетенции...»

«СОДЕРЖАНИЕ. Цели освоения дисциплины..3 1. Место дисциплины в структуре ООП бакалавриата.3 2. Компетенции обучающегося..3 3. Структура и содержание дисциплины.5 4. Образовательные технологии..19 5. Формы и методы контроля..19 6. Учебно-методическое и информационное обеспечение 7. дисциплины..20 Материально-техническое обеспечение.21 8. Приложение 1. Приложение 2. 2 1. Цели освоения дисциплины изучение основных институтов жилищного права, каковыми являются социальный и коммерческий найм,...»

«Номенклатура цифровых образовательных ресурсов локального доступа, используемых в образовательном процессе Сведения, Область количественной № п/п Вид ресурса Сведения об издании относящиеся к характеристики заглавию Русский язык 1с: Репетитор. 1. Электронное учебное издание ЗАО 1С, 1999-2002 1CD-ROM Русский язык Программа-тренажер по 2. Фраза 2001. Гуру Софт 1CD-ROM русскому языку Диктанты 3. Учебное пособие Издательство Учитель 1CD-ROM Изложения Тренировочные упражнения 5-11 класс Начальная...»

«1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Новокузнецкий институт (филиал) Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Кемеровский государственный университет юридический факультет УТВЕРЖДАЮ Директор НФИ КемГУ В.С. Гершгорин _ _ 2012 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС право_ _ Б.3.Б.14. _Финансовое Направление подготовки _030900.62 Юриспруденция Профиль подготовки _Государственно-правовой Гражданско-правовой...»

«Московский государственный технический университет имени Н. Э. Баумана Калужский филиал А. В. Волков ОПРЕДЕЛЕНИЕ ДИНАМИЧЕСКОЙ ХАРАКТЕРИСТИКИ ШПИНДЕЛЬНОГО УЗЛА СТАНКА Методические указания 1 УДК 621.9:531.3 ББК 34.63-5 В67 Рецензент: канд. техн. наук, доцент В. М. Попков Утверждено методической комиссией КФ МГТУ им. Н. Э. Баумана (протокол № 4 от 04.10.11) Волков А. В. В67 Определение динамической характеристики шпиндельного узла станка : методические указания к выполнению домашнего задания по...»

«Федеральное агентство по образованию ГОУ ВПО Алтайский государственный университет УТВЕРЖДАЮ декан исторического факультета Демчик Е.В. _ 2010 г. РАБОЧАЯ ПРОГРАММА по дисциплине Маркетинг экскурсионно-туристической деятельности для специальности 031502.65 Музеология факультет исторический кафедра археологии, этнографии и музеологии курс 5 семестр 9 лекции 20 (час.) Практические (семинарские) занятия 10 (час.) Зачет в 9 семестре Всего часов 30 Самостоятельная работа 30 (час.) Итого часов...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Гуманитарный факультет Кафедра всеобщей истории Г. Г. Пиков ИЗ ИСТОРИИ ЕВРОПЕЙСКОЙ КУЛЬТУРЫ Учебное пособие Новосибирск 2002 Пиков Г. Г. Из истории европейской культуры: Учебное пособие / Новосибирский государственный университет. Новосибирск, 2002. 255 с. Пособие подготовлено на кафедре всеобщей истории гуманитарного факультета Новосибирского государственного университета в соответствии с программами курсов...»

«Санкт-Петербургский государственный технический университет Институт инноватики УПРАВЛЕНИЕ ИННОВАЦИОННЫМИ ПРОЕКТАМИ Часть 2 Инструментальные средства и практикум управления проектами Санкт Петербург Институт инноватики http://ii.spb.ru/ Авторы: Т.В.Александрова С.А.Голубев. О.В.Колосова, Н.Б.Культин, С.П.Некрасов, Ю.Р.Нурулин, И.Л.Туккель, В.С.Черняк. Управление инновационными проектами. Учебное пособие в 2-х частях. Издание второе, переработанное и расширенное. Часть 2. Методология управления...»

«Министерство образования Республики Беларусь Учебно-методическое объединение высших учебных заведений Республики Беларусь по химико-технологическому образованию УТВЕРЖДЕНА Министерством образования Республики Беларусь 08.01.2011 г Регистрационный № ТД-I.604 /тип. ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ И ИННОВАЦИОННОЙ ДЕЯТЕЛЬНОСТИ Типовая учебная программа для высших учебных заведений по специальности 1-48 01 01 Химическая технология неорганических веществ, материалов и изделий Минск УДК 001:001.895(073)...»

«3. Физическая культура. Типовая учебная программа для высших учебных заведений./ В.А. Коледа, Е. К. Кулинкович, И.И. Лосева, В.А., Овсянкин, Т.А. Глазько – Минск:РИВШ, 2008г. – 49с. 4. Физическая культура студента: учебник / под ред. В.И. Ильинича. – М., 1999. – 448 с. 5. Физическая культура: учеб. пособие / В.А. Коледа и др.; под общ. ред. В.А. Коледы. – Минск: БГУ, 2005. – 211 с.: ил. 6. Холодов, Ж.К. Теория и методика физического воспитания и спорта: учебное пособие для студентов высш. учеб....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Восточно-Сибирская государственная академия образования Факультет компьютерных наук Кафедра математической информатики Выпускная квалификационная работа специальности 080801 Прикладная информатика (в образовании) Методические рекомендации Иркутск 2011 ББК 74.262+74.58 УДК 510(07)+378 И 93 Печатается по решению учебно-методической комиссии...»

«Политология Политология : учебник для бакалавров / под ред. В. Н. Лавриненко. – 4-е изд., перераб. и доп. – М. : Юрайт, 2012. – 519 с. – (Бакалавр. Базовый курс). – гриф МО В учебнике в доступной для понимания форме изложен полный курс политологии. Авторами рассмотрены основные понятия (категории) политологии, её общетеоретические и методологические проблемы, выполняемые функции, а также методы политологических исследований. Значительное внимание уделено истории развития политической мысли и...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА И ПРОДОВОЛЬСТВИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ В.В. Липницкая, З.Г. Близнюк МАКРОЭКОНОМИКА Методические указания и задания по выполнению курсовых работ студентами специальностей 1-25 01 07 Экономика и управление на предприятии, 1-26 02 02 Менеджмент Минск 2008 УДК 330.101.541(075.8) ББК 65.012.2я7 Л 61 Рекомендовано научно-методическим советом факультета предпринимательства и управления...»

«Министерство образования и науки Российской Федерации Сыктывкарский лесной институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования Санкт-Петербургский государственный лесотехнический университет имени С. М. Кирова Кафедра менеджмента и маркетинга Посвящается 60-летию высшего профессионального лесного образования в Республике Коми СТРАХОВАНИЕ Учебное пособие Утверждено учебно-методическим советом Сыктывкарского лесного...»

«учителя физической культуры МБОУ Боханской СОШ №2 Асалханова Александра Львовича ФИО учителя: Асалханов Александ Львович Дата рождения: 16 февраля 1976 г. Сведения об образовании: среднее специальное. В 1996 году окончил отделение физической культуры в Боханском педагогическом училище им. Д. Банзарова. Трудовой стаж: 12 лет Педагогический стаж: 10 лет Стаж работы в данной школе: 12 года Квалификационная категория: 9 разряд Адрес места жительства: 669311 Иркутская область, Боханский район, п....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Н. Т. Когабаев ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ Учебное пособие Новосибирск 2009 УДК 510.5(075) ББК В12я73-1 К 570 Когабаев Н. Т. Лекции по теории алгоритмов: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2009. 107 с. ISBN 978-5-94356-799-5 В настоящем учебном пособии изложены математические основы теории алгоритмов. Пособие отражает содержание лекций основного курса Теория алгоритмов...»

«УДК 741.041.02(075.8) ББК 85.15я73 Н56 ПРЕДИСЛОВИЕ Р е ц е н з е н т ы: кафедра художественного и педагогического обра Выполнение рисунка головы человека требует опреде зования Белорусского государственного педагогического университета имени Максима Танка (доцент Г.В. Лойко); кандидат педагогических ленных умений и навыков. Без знаний правил восприя наук профессор Г.Ф. Шауро тия модели, законов изображения, без знаний пластиче ской анатомии невозможно создать изображение, про фессионально...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ЭКОНОМИКИ ПРЕДПРИЯТИЯ И ПРОИЗВОДСТВЕННОГО МЕНЕДЖМЕНТА С.А. БРЫЗГАЛОВА Н.А. СОКОЛОВА РЕКЛАМНЫЙ МЕНЕДЖМЕНТ УЧЕБНОЕ ПОСОБИЕ ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ ББК 65.290- Б...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.