- •Лекция 1.
- •Контрольные вопросы.
- •Лекция 2.
- •Контрольные вопросы.
- •Лекция 3.
- •Контрольные вопросы.
- •Лекция 4.
- •Контрольные вопросы.
- •Лекция 5.
- •Контрольные вопросы.
- •Лекция 6.
- •Контрольные вопросы.
- •Лекция 7.
- •Моделирование как метод познания.
- •Статистические и динамические информационные модели.
- •Формы представления информационных моделей.
- •Классификация информационных моделей.
- •Пример иерархической статистической информационной модели.
- •IV. Объектно-ориентированное моделирование.
- •Контрольные вопросы.
- •Лекция 8.
- •Лекция 9.
- •Контрольные вопросы.
- •Лекция 10.
- •Контрольные вопросы.
- •Лекция 11.
- •Контрольные вопросы.
- •Лекция 12.
- •Обобщенная схема циклического алгоритма
- •Составление алгоритмов циклической и сложной структуры.
- •Контрольные вопросы.
- •Лекция 13.
- •Контрольные вопросы.
- •Лекция 14.
- •1. Краткая характеристика языка Паскаль.
- •2. Интегрированная среда программирования Turbo Pascal.
- •2.1. Клавиши оперативного вмешательства.
- •2.2. Основное меню.
- •2.3. Локальное меню.
- •2.4. Экранный редактор.
- •Контрольные вопросы.
- •Лекция 15.
- •1. Символы языка.
- •2. Комментарии.
- •3. Простейшие конструкции языка.
- •Выражения
- •Контрольные вопросы.
- •Лекция 16.
- •Структура программы Turbo Pascal.»
- •Структура программы на языке Турбо Паскаль
- •Контрольные вопросы.
- •Лекция 17.
- •2.Простейшие операторы.
- •3.Операторы ввода - вывода.
- •Контрольные вопросы.
- •Лекция 18.
- •Контрольные вопросы.
- •Лекция 19.
- •Контрольные вопросы.
- •Лекция 20.
- •1.Понятие подпрограммы.
- •2.Процедуры.
- •3.Функции.
- •Контрольные вопросы.
- •Лекция 21.
- •1.Понятие массив данных.
- •2.Операция над массивами.
- •3. Одномерные массивы.
- •3.2.Способы задания одномерных массивов.
- •3.3.Описание типа одномерных массивов.
- •4.Двумерные массивы.
- •4.1Способы объявления двумерного массива.
- •Контрольные вопросы.
- •Лекция 22.
- •1. Сортировка массива.
- •1.1.Линейная сортировка (сортировка отбором)
- •1.2.Сортировка методом пузырька.
- •1.3.Метод быстрой сортировки с разделением
- •2. Бинарный поиск в упорядоченных массивах.
- •Контрольные вопросы.
- •Лекция 23.
- •1.Графический экран.
- •2.Текстовый экран.
- •3.Управление звуком.
- •Контрольные вопросы.
- •Лекция 24.
- •Основы взаимодействия пользователя с системой
- •Навигация по дискам и каталогам с помощью пиктограммы «Мой компьютер»
- •Контрольные вопросы.
- •Лекция 25.
- •Контрольные вопросы.
- •Лекция 26.
- •Контрольные вопросы.
- •Лекция 27.
- •1 Способ:
- •2 Способ:
- •Контрольные вопросы.
- •Лекция 28.
- •1. Основные понятия электронных таблиц.
- •2. Ввод, редактирование и форматирование данных.
- •3. Вычисления в электронных таблицах.
- •Контрольные вопросы.
- •Лекция 29.
- •Контрольные вопросы.
1.2.Сортировка методом пузырька.
Один из самых популярных методов сортировки – ″пузырьковый″ метод основан на том, что в процессе исполнения алгоритма более ″легкие″ элементы массива постепенно ″всплывают″. Особенности данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.
Текст программы сортировки массива по невозрастанию можно записать в таком варианте:
program Sort_Puz; (Сортировка массива ″пузырьковым″ методом по невозрастанию}
const
Count=20;
M: array [1.. Count] of
byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5);
var I, J, N, L: Byte;
A:integer;
begin
Writeln(′Исходный массив:′);
for I:=1 to Count do Write (M [I]′,’);
Writeln;
A:=0;
for I:=2 to Count do(Сортировка ″пузырьковым″ методом по невозрастанию}
begin
for J:= Count downto Ido
begin
A:=A+1;
if M[J-1]<M[J] then {Если элемент справа больше элемента слева, то ″вытеснить″ его влево - пузырек ″всплывает″}
begin
K: = M [J-1]; {Обмен значениями этих элементов}
M [J-1]: = M [J];
M [J]: = K;
{Печатать текущее состояние массива после каждой перестановки}
for L:=1 to Count do Write (Writein (′Число итераций=′,А);
end;
end;
end;{Завершение сортировки}
end.
1.3.Метод быстрой сортировки с разделением
Оба выше рассмотренных метода достаточно просты и наглядны, но не очень эффективны. Значительно быстрее работает алгоритм сортировки К. Хора, который называют сортировкой с разделением или ″быстрой сортировкой″. В основу алгоритма положен метод последовательного дробления массива на части. Рассмотрим пример программы, реализующей этот метод.
Program Quck_sort; {Быстрая сортировка по невозрастанию дроблением массива на части}
uses Crt;
const
Count=20;
M: array [1.. Count] of byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var
I, A: integers;
procedure QuickS(First, Last: integer);
var I,J,X,W,L: integer;
begin
I: = First; {Левая граница массива - первый элемент}
J: = Last; (Правая граница массива - первый элемент}
X: =M [(First+ Last) div 2]; (Определить середину массива}
repeat
while M[I]>X do
I: =1+1;
While X>M [J] do
J: = J-1;
A: =A+1 ;( Увеличить число итераций обмена элементов}
if K=J then
begin (Обменять местами элементы}
W: =M[i];
M [I]:=M [J];
M [J]:=W;
I: =I+1;
J: =J-1 ;( Печатать текущее состояние массива после каждой перестановки}
for L:=1 to Count do Write (‘’, M [L]);
Writeln (′Число итераций =′, А);
end;
until I>J;
if First<J then QuickS (First, J)
if K Last then Quacks(I, Last); {Рекурсивный вызов процедуры QuickS }
end;{Конец сортировки}
begin {Начало основной программы}
CIrScr;
Writeln (′Исходный массив :′);
Writeln;
for I:=1 to Count do Write(M[I]:3,′‘); Writeln;
A: =0;
QuickS (1, Count) ;{ Вызов процедуры сортировки QuickS}
Writeln {′Отсортированный массив :′); Writeln;
for I:=1 to Count do Write(M[I]:3,′‘); Writeln;
end.
После первого вызова процедуры QuickS в исходном массиве: 9 11 12 3 1 9 1 5 1710 183 1 9 17 9 12 20 20 19 2 5 будет определена его середина (10-й элемент) и переменной X присвоено значение M[10], т.е. 18. После этого массив делится на две части: 9 1 12 3 1 9 1 5 17 10 18 и 3 19 17 9 12 20 20 9 2 5
Далее выполняется обмен элементами по следующему правилу:
При просмотре левой части массива слева направо выполняется поиск такого элемента массива, что M[I]>X, затем при просмотре правой части справа налево отыскивается такой элемент, M[I]<X. Выполняется обмен местами данных элементов, пока все элементы слева от середины, удовлетворяющие условию M[I]>X, не будут обменены с элементами, расположенными справа от середины и удовлетворяющими условию M[I]<X. В результате этого получим массив из двух частей следующего вида:
9 11 12 19 1 5 17 10 18 3 19 17 9 12 20 20 19 2 5 Число итераций=1
19 20 12 3 19 1 5 17 10 18 3 19 17 9 12 20 11 9 2 5 Число итераций=2
19 20 20 3 19 1 5 17 10 18 3 19 17 9 12 12 11 9 2 5 Число итераций=3
19 20 20 19 19 1 5 17 10 18 3 3 17 9 12 12 11 9 2 5 Число итераций=4
19 20 20 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=5
Далее рекурсивно левая часть в свою очередь дробится на две части, и вызывается процедура для сортировки левой части (с 1-го по 6-и элемет)
20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=7
20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=8
После того как левая часть массива отсортирована, опять рекурсивно вызывается процедура, в которой определяется середина данной части массива, и выполняется обмен элементов. Массив становится таким:
20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=9
20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=10
Далее опять рекурсивно вызывается процедура для сортировки, пока в каждой из частей останется пока в каждой из частей останется по одному элементу.
Затем рекурсивно вызывается процедура для аналогичной сортировки правой части (с 7-го по 19-й элемент). Результат последовательных этапов сортировки массива отображается так:
20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=11
20 20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций=12
20 20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций=13
20 20 19 19 19 18 17 17 10 9 3 3 5 9 12 12 11 1 2 5 Число итераций=14
20 20 19 19 19 18 17 17 10 9 1 1 3 5 9 12 12 3 1 2 5 Число итераций=15
20 20 19 19 19 18 17 17 10 9 1 1 12 5 9 12 3 3 1 2 5 Число итераций=16
20 20 19 19 19 18 17 17 10 9 1 1 12 12 9 5 3 3 1 2 5 Число итераций=17
20 20 19 19 19 18 17 17 10 9 1 1 12 12 9 5 3 3 1 2 5 Число итераций=18
20 20 19 19 19 18 17 17 12 9 1 1 12 10 9 5 3 3 1 2 5 Число итераций=19
20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=20
20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=21
20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=22
20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=23
20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=24
20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=25
20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=26
20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 5 3 3 2 1 Число итераций=27
По последнему значению А определяем что для данного массива сортировка по невозрастанию выполняется за 27 итераций.
Как видно из приведенных примеров, алгоритм ″быстро″ сортировки дает лучшие результаты, чем пузырьковый метод, однако следует учесть, что в некоторых случаях это преимущество снижается. Например, если применить эту программу для сортировки массива M, элементы которого имеют значение 29, 27, 24, 3, 23, 19, 19, 18, 1, 17, 15, 13, 1, 0, 9, 9, 8, 6, 6, 5, то сортировка будет выполнена за 28 итераций, т.е. время процесса и число итераций даже увеличатся, несмотря на то, что исходный массив в большей степени упорядочен, в то время как сортировка линейным методом-190 итераций для обоих массивов, пузырьковым-166(для первого массива-170).