- •Конспект лекций по курсу «Информатика» для студентов очной и заочной форм обучения.
- •Базовые положения
- •§.1. Физическое устройство и разумная деятельность мозга
- •§2. Самодостаточная эвм
- •2.1. Память (оперативная память)
- •2.2. Процессор
- •2.3. Программа
- •2.4. Жизненный цикл «Самодостаточной эвм»
- •§3. Язык процессора – базовый язык эвм
- •§4. Реальная эвм. Периферийные устройства
- •§5. Язык программирования. Программа транслятор
- •§6. Язык программирования Pascal
- •6.1. Базовые типы числовых информационных объектов
- •6.2. Явные константы
- •6.3. Оператор описания var
- •Var и1, и2, и3, . . . . ,Иn: Итипа;
- •6.5. Операторы консольного ввода информации
- •6.5.1. Стандартные форматы вывода числовой информации.
- •6.6. Логические переменные
- •6.7. Операторы управления программой
- •6.7.1. Условный оператор if then
- •If Условие then Оператор ;
- •6.7.2. Условный оператор выбора if then else
- •6.8. Метки операторов. Оператор безусловного перехода
- •6.9. Циклические вычисления. Операторы зацикливания
- •Организация циклических вычислений операторами if then goto
- •Программа вычисления корня по формуле Герона.
- •6.9.3. Оператор цикла for to
- •6.9.4. Оператор цикла for downto
- •6.9.5. Оператор цикла while
- •6.9.6. Программа вычисления длины дуги кривой
- •7. Массивы переменных
- •7.1. Программа нахождения экстремальных значений
- •7.2. Программа решения системы линейных алгебраических уравнений
- •8. Сортировка информации
- •8.1. Элементы формальной логики, теории множеств и операций
- •8.2. Упорядоченные структуры информационных объектов
- •8.3. Алгоритм сортировки «поплавок»
- •8.3.1. Программа сортировки массива «на месте»
- •8.3.2. Программа сортировки «индексов» массива
- •8.4. Алгоритм быстрого поиска информации в линейно упорядоченном массиве
- •8.4.1. Программа поиска в отсортированных массивах.
- •9. Символьные переменные
- •9.1.Строковые переменные
- •9.1.1. Программа написания чисел прописью
- •10. Клавиатурное управление эвм
- •§.11. Информационные объекты класса – изображение
- •11.1. Устройство функционированиемонитора
- •11.2. Процедурный язык управления графическим экраном
- •11.3. Оцифровка и масштабирование реальных изображений (чертежей) для последующего их вывода на экран
- •11.4. Пример построения фрагмента графика функции
- •11.5. Ввод и обработка информации в форме изображений
- •§12. Информационные объекты класса – подпрограммы
- •12.1. Подпрограммы типа procedure
- •12.1.1. Пример оформления подпрограммы-процедуры
- •12.2. Подпрограммы класса function
- •12.2.1.Пример оформления подпрограммы-функции
- •12.3. Процедурные языки программирования
- •12.4. Библиотечные модули Unit
- •§13. Динамическое распределение оперативной памяти эвм
- •13.1. Программа использующая динамические переменные
- •§14. Переменные типа record
- •§15. Внешняя память эвм. Работа с файлами
- •15.1. Процедурный язык обработки файлов
- •15.2.Программа “ Жизненный путь файла “
- •15.3. Текстовые файлы
- •§16. Элементы объектно-ориентированного программирования
- •Основная рекомендуемая литература.
8.3.2. Программа сортировки «индексов» массива
«Сортировка индексов» - результатом сортировки является последовательность (массив) целочисленных переменных {ki}, i=1, 2, ...n, где число ki указывает порядковый номер объекта aki , который должен находиться на i-ом месте в отсортированной совокупности.
Пример программы, помещающей результаты сортировки массива действительных чисел в специальный массив индексов K[].
Program N8;
Type T=array[1..4] of real;
Const a:T=(30, 40, -20, 30);
Var K: array[1..4] of integer; {массив для размещения значений индексов}
Var i, j, ii, N: integer;
Begin
N:=4;
for i:=1 to N do K[i]:=i; {первоначально, содержимое массива K[]
совпадает с естественной номерацией неупорядоченного
содержимого (информации) массива a[]}
for ii:=1 to N-1 do {ii – счетчик повторных просмотров
элементов массива}
for i:=1 to N-ii do { i – номер первого из пары просматриваемых
индексов }
if (a[K[i]]<a[K[i+1]])=false then {информация объекта с индексом
K[i+1], т.е. дествительное числоa [K[i+1]], должно находится
левее информации объекта с индексом K[i], т.е. левее
действительного числа a[K[i]] }
begin j:=K[i]; K[i]:=K[i+1]; K[i+1]:=j end;
{ печать содержимого массива a[] в
Упорядоченном (отсортированном) виде}
for i:=1 to N do WRITE(a[K[i]]:5:0);
End.
Трассировка программы:
-
Значения счетчиков циклов
i и ii
Текущее содержимое массива K
k[1]
k[2]
k[3]
k[4]
ii=1 i=1 (нет переписей)
1
2
3
4
i=2 (перепись 2 и 3)
1
3
2
4
i=3 (перепись 2 и 4)
1
3
4
2
ii=2 i=1 (перепись 1 и 3)
3
1
4
2
i=2 (перепись 1 и 4)
3
4
1
2
ii=3 i=1 (нет переписей)
3
4
1
2
Метод «сортировки индексов», сохраняя первоначальную структуру сортируемой информации, требует дополнительно всего 2n байт памяти ЭВМ.
8.4. Алгоритм быстрого поиска информации в линейно упорядоченном массиве
Принцип упорядоченного размещения информации является базовым для организации всех архивов (библиотек, электронных баз данных), поскольку поиск нужной информации в неупорядоченном множестве сводится к банальному последовательному перебору (просмотру) всех данных, что требует огромных временных затрат, даже для современных быстродействующих ЭВМ.
Задача: в упорядоченном, по операции сравнения Р, массиве информационных объектов {ai}, i=1, 2, ...n, для заданного объекта b, найти два соседних элемента aj и aj+1 , для которых P(aj,b)=true и P(b,aj+1)=true, т.е. объект aj предшествует b объекту и b предшествует aj+1.
Частные случаи решения:
1). Объект b может предшествовать всем элементам массива, что имеет место если P(b,a1)=true,
2). Все элементы массива могут предшествовать объекту b, что будет наблюдаться если P(an,b)=true.
Алгоритм решения задачи.
1). Проверяем частные случаи. Если один из них выполняется, то задача решена. В противном случае, объект b находится правее объекта a1 и левее объекта an. Запоминаем номера (индексы) элементов, ограничивающих область локализации объекта b: imin=1 и imax=n.
2). Вычисляем i-номер (индекс) объекта ai расположенного в центре области локализации i=( imin + imax ) div 2 (целочисленное деление !).
3). Если P(ai,b)=true, т.е. объект ai действительно располагается левее объекта b, то изменяем imin=i, в противном случае изменяем imax=i.
Размер области локализации объекта b сокращен в два раза!
4). Повторяем выполнение пунктов (2) и (3) K- раз, где K=[Log2n], т.е. K- наименьшее целое число удовлетворяющее неравенству n≤2K.
Примеры количественной оценки алгоритма:
Для поиска нужной информации в массиве из n=500 элементов требуется проведения всего K=9 проверок, т.к. размеры области локализации решения (imax -imin ) последовательно сокращаются:
-
imax -imin
499
250
125
63
32
16
8
4
2
1
K
0
1
2
3
4
5
6
7
8
9
Для решения этой же задачи с неупорядоченными данными пришлось бы сделать 1000 проверок, т.е. в сто раз больше.
Для поиска адреса человека в миллионном городе, по его Ф.И.О., требуется выполнить всего двадцать проверок в упорядоченном списке соответствующей базы данных.