- •Конспект лекций по курсу «Информатика» для студентов очной и заочной форм обучения.
- •Базовые положения
- •§.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. Элементы объектно-ориентированного программирования
- •Основная рекомендуемая литература.
7.1. Программа нахождения экстремальных значений
Задача: найти сумму наибольшего и наименьшего из заданных N- действительных чисел.
Алгоритм и блок-схема программы:
резервируем в оперативной памяти место для размещения массива из 20 вещественных чисел, т.е. создаем переменную типа ARRAY из двадцати элементов типа REAL,
запрашиваем у пользователя N - конкретное количество чисел, которые предстоит обрабатывать,
проверяем соответствие введенного числа N объему зарезервированной памяти, если N>20 завершаем выполнение программы,
консольно вводим N чисел,
в качестве начальных значений Xmax и Xmin (наибольшего и наименьшего из заданных чисел) берем значение первого элемента массива,
в цикле, просматриваем все оставшиеся элементы массива Xi и сравниваем их с Xmax и Xmin:
если очередное число Xi больше Xmax, то меняем Xmax на Xi,
если очередное число Xi меньше Xmin, то меняем Xmin на Xi,
печатаем результат сложения найденных Xmax и Xmin.
Program N3;
Var X: array[1..20] of real;
i, N: integer; Xmin, Xmax: real;
Begin
Write(‘Введите количество чисел N=’); ReadLN(N);
if N>20 then
begin WriteLN(‘Число N должно быть не более 20-ти !’); Exit end;
for i:=1 to N do
begin
Write(‘Введите ’, i,’-ое число =’);
ReadLN(x[i]);
end;
Xmin:=x[1]; Xmax:=x[1];
for i:=2 to N do
begin
if Xmin>x[i] then Xmin:=x[i];
if Xmax<x[i] then Xmax:=x[i];
end;
WriteLN(‘Ответ Xmin+Xmax =’, Xmin+Xmax)
End.
Типичные ошибки при использовании переменных типа массив:
значение используемого индекса не находится в требуемых (описанных) границах, например:
Type Tvec= array[1..4] of real;
Var V, W: Tvec; k: integer; RR: real;
. . . . . .
k:=3; V[3]:=V[k+2]; { вычисляемый индекс равен 5>4 !}
значение вычисляемого индекса не является целочисленной переменной, например:
V[2]:=7 + V[sqrt(k)];
или RR:=4; V[k]:=RR – V[RR –2];
выполнение арифметических операций над массивом как единым целым, например:
W:=Pi*V ;
или V:=Sin(V);
7.2. Программа решения системы линейных алгебраических уравнений
Эффективность использования ЭВМ проявляется только при реализации алгоритмов, которые основаны на многократном повторении одних и тех же операций на большом количестве однотипных информационных объектов.
Повторение однотипных действий описывается на языке программирования операторами цикла. Перебор множества однотипных объектов легко осуществим, если эти объекты наделены общим именем и строго упорядочены, т.е. прономерованы.
Опр. Упорядоченная совокупность однотипных объектов различимых одним индексом { } , i=1,2,…n образуют математический объект – вектор и его аналог в программировании – одномерный массив:
Var b: array [1…N] of real;
где отдельный -ый элемент совокупности именуется b[i].
Опр. Упорядоченная совокупность однотипных объектов, различимых по двум индексам { aij }, i=1,2…k, j=1,2,…m, образует математический объект – матрицу, а в программировании – двумерный массив
Var a: array [1..k, 1..m] of real;
а отдельный aij-элемент именуется а[i, j].
Примечание: Упорядоченность информационных объектов по k-индексам формализуем k-мерным массивом.
Для освоения техники использования индексированных переменных напишем программу решения системы линейных алгебраических уравнений: найти числа {xi}, i=1,2,…n, удовлетворяющие уравнениям:
i j = 1 2 3 … . . j . . . . . n
1 a11x1+a12x2+a13x3+...+a1jxj ...+a1nxn =b1
2 a21x1+a22x2+a23x3+...+a2jxj...+a2nxn =b2 (1)
3 a31x1+a32x2+a33x3+...+a3jxn...+a3nxn =b3
. . . . . . . . .
n an1x1+an2x2+an3x3+...+anjnj...+annxn =bn
Матричная формула записи задачи (1): А = (2)
где А = {aij} = {xi} = {bi} i=1,2…n, j=1,2,…n
Запись системы (1) посредством символа суммирования:
, для i=1, 2…n (3)
Систему уравнений (1) решаем методом последовательного исключения Гаусса.
Целью первого этапа этого метода является преобразование матрицы к треугольному виду, т.е. обнуление всех коэффициентов матрицы, расположенных ниже главной диагонали, что формализуется записью:
aij=0 для всех i > j (4)
Алгоритм первого этапа:
1) Полагая ≠ 0, делим первое уравнение системы (1) на , т.е. приводим его к виду
1∙ (5)
где j = 1,2,3….n (6)
(7)
Эти действия на языке Pascal описываются операторами:
R:=A[1,1]; {сохранили значение коэффициента
в рабочей переменной с именем R}
for j:=1 to N do a[1, j]:=a[1, j]/R; {вычислили значение и разместили их в
тех же местах памяти, где ранее были значения }
b[1]:=b[1]/R;
Вопрос для самопроверки: почему нельзя описывать вычисления операторами:
for j: =1 to N do a [1,j] : = a [1,j]/a [1,1]; b [1] : = b [1]/a[1,1];
2) С помощью преобразованного первого уравнения (5) легко исключить (обнулить) первые слагаемые из всех остальных уравнений системы, т.е. обнулить все для i=2,3,…n, т.е. обнулить первый столбец матрицы. Для этого необходимо из каждого i-го уравнения (i=2,3,…n) вычесть первое уравнение, т.е. (5) предварительно умножив его на .
Математически это записывается так: для всех i=2,3,…n и j=1, 2, ...n вычислить новые (пересчитать) коэффициенты
и (8)
На языке Pascal, эти инструкции записываются оператором двойного (вложенного) цикла:
For i:=2 to N do { перебор уравнений системы от i=2 до i=n}
begin
R:=a[i,1]; {копирование в рабочую ячейку памяти}
for j:=1 to N do a[i,j]:=a[i,j]-a[1,j]*R;
{пересчет всех элементов матрицы в i-ой строке}
b[i]:=b[i]-b[1]*R {пересчет значения bi}
end;
3) Преобразования, описанные в п.п.(1) и (2) следует последовательно повторить для всех остальных строк системы уравнений (1), т.е. с помощью второго уравнения исключить (обнулить) все под диагональные элементы матрицы из второго столбца, а с помощью третьего уравнения исключить все под диагональные элементы из третьего столбца и т.д.
Строгая упорядоченность выполняемых действий позволяет описать их на языке Pascal посредством вложенных циклов:
For i:=1 to N do {i- номер уравнения, которое используется для обнуления
всех коэффициентов матрицы А, расположенных в i-ом столбце
ниже главной диагонали}
begin
{выполняем пункт (1) для i-го уравнения системы}
R:=a[i,i]; {скопировали в рабочую ячейку коэффициент
матрицы на главной диагонали}
For j:=i to N do a [i,j]: = a [i,j] / R; {j-номера элементов матрицы
в i-ой строке, расположенных левее главной диагонали
Пояснение: цикл по j следует начинать именно с i, а не с 1
, т.к. все элементы матрицы в i-ой строке расположенные
левее i-ого уже обнуленными !}
b [i] : = b [i] / R; {Выполняем пункт (2) для всех уравнений систем,
расположенных ниже i-ой уравнения}
For k:=i+1 to N do {переменная k содержит номер очередного
обрабатываемого уравнения системы, из которого
исключается (обнуляется) коэффициент aki}
begin
R:=a[k,i];
For j:= i to N do a[k,j]:=a[k,j]-a[i,j]*R
{Напоминание: для j=1,2,….i-1 вычислять не надо,
т.к. там уже помещены нули}
b[k]:=b[k]-b[i]*R;
end;
end; {конец цикла по i}
Второй (завершающий) этап решения системы (1) реализуется последовательным просмотром и разрешением всех уравнений системы в обратном порядке, т.е. от N-го до первого.
Последнее уравнение системы, после проведенных преобразований имеет вид
0 ∙ +0∙ +…0∙ +1∙ = , откуда легко находим = ,
Предпоследнее уравнение:
0∙ +0∙ +…0 +1∙ ∙ =
позволяет легко найти , т.к. уже известно = ∙
Аналогично вычисляются и все остальные искомые значения . Математически эта часть алгоритма записывается как
= , для i = n, n-1, n-2…, 2,1
На языке Pascal:
For i:=N downto 1 do {i- номер вычисляемой неизвестной xi , который
последовательно уменьшается на 1 от величины N до 1,
i- номер окончательно разрешаемого уравнения системы}
begin
x[i]:=b[i];
for j:=i+1 to N do x[i]:= x[i]-a[i,j]*x[j]; {j – номера ранее вычисленных
значений xj}
end;