Данные, их типы, структуры и обработка

8. Лекция: Данные, их типы, структуры и обработка Рассматриваются основные понятия о данных к алгоритмам, их базовые типы и структуры, вопросы их использования в алгоритмизации задач. Любая актуализация информации опирается на какие-то данные, любые данные могут быть каким-то образом актуализированы. Данные – это некоторые сообщения, слова в некотором заданном алфавите. Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел. Текущее (то есть рассматриваемое в данный момент времени) состояние данных называют текущим значением данных или просто значением . До разработки алгоритма (программы) необходимо выбрать оптимальную для реализации задачи структуру данных. Неудачный выбор данных и их описания может не только усложнить решаемую задачу и сделать ее плохо понимаемой, но и привести к неверным результатам. На структуру данных влияет и выбранный метод решения. Пример. При решении системы линейных алгебраических уравнений можно воспользоваться методом Крамера (с помощью определителей) или методом Гаусса (с помощью последовательных исключений неизвестных). Метод Крамера потребует при реализации примерно в 3 раза больше операций, чем метод Гаусса, и поэтому им никогда не пользуются при расчетах на ЭВМ. Тип данных характеризует область определения значений данных. Задаются типы данных простым перечислением значений типа, например как в простых типах данных , либо объединением (структурированием) ранее определенных каких-то типов – структурированные типы данных . Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением: специальность = (филолог, историк, математик, медик); студент = (Петров, Николаев, Семенов, Иванова, Петрова); вуз = (МГУ, РГУ, КБГУ). Значением типа "студент" может быть Петров. Пример. Опишем структурированный тип данных "специальность_студента": специальность_студента=(специальность, студент). Значением типа "специальность_студента" может быть пара (историк, Семенов). Для обозначения текущих значений данных используются константы – числовые, текстовые, логические. Часто (в зависимости от задачи) рассматривают данные, которые имеют не только "линейную" (как приведенные выше), но и иерархическую структуру. Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники". В алгоритмических языках есть стандартные типы, например, целые, вещественные, символьные, текстовые и логические типы. Они в этих языках не уточняются (не определяются, описываются явно) и имеют соответствующие описания с помощью служебных слов. Пример. В школьном алгоритмическом языке (ШАЯ), например, целые, вещественные, символьные, текстовые (литерные, стринговые) и логические типы данных описываются ключевыми словами цел, вещ, сим, лит, лог. В языке Паскаль – аналогичными ключевыми словами integer, real, char, string, boolean. Каждый тип данных допускает использование определенных операций со значениями типа ("с типом"). Пример. Для целого типа данных назовем операции ":=", "+", "–", "*", "=" (сравнение на равенство), "", "<", ">", "", "".. Для вещественного типа данных еще и операция "/" (деление). Для символьного типа данных – только ":=", "=", "", "<", ">", "", "". Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся, например, в таблице ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными). Для текстового (литерного) типа данных можно использовать еще и операцию конкатенации (присоединения справа) текстов "+". Например, "аб"+"ба" даст новый текст "абба". Для данных логического типа определены логические операции и отношения сравнения. Например, на Паскале для логических переменных a, b, c можно записать корректное выражение: a and b or (c not a). Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: на ШАЯ – сим, лит, на Паскале – char, string. Текстовые (символьные) константы обычно заключают в апострофы. Пример. Составим алгоритм подсчета числа несовпадающих символов (на одинаковых позициях текстов) в двух заданных текстах a и b. Метод решения: "вырезаем" и сравниваем символы на одинаковых позициях в текстах на совпадение. Program EquSimb; Uses Crt; Var i, k, j: integer; a, b: string; Begin ClrScr; WriteLn('Введите строку a = '); { приглашение к вводу входного параметра } ReadLn(a); { ввод первого входного параметра } WriteLn('Введите строку b='); { приглашение к вводу второго параметра } ReadLn(b); { ввод второго входного параметра } k:=abs(length(a)–length(b)); { вычисление разницы длин текстов } if (length(a)b[i]) { если символы тестов на одинаковых позициях не равны, } then k:=k+1; { то увеличиваем счетчик количества таких символов } WriteLn('k = ',k); { вывод результата } End. Наиболее часто используемая структура данных – массив. Одномерный массив (вектор, ряд, линейная таблица) – это совокупность значений некоторого простого типа (целого, вещественного, символьного, текстового или логического типа), перенумерованных в каком-то порядке и имеющих общее имя. Для выделения конкретного элемента массива необходимо указать его порядковый номер в этом ряду. Пример. Последовательность чисел 89, –65, 9, 0, –1.7 может образовывать одномерный вещественный массив размерности 5, например, с именем x вида: x[1] = 89, x[2] = –65, x[3] = 9, x[4] = 0, x[5] = –1.7. Значение порядкового номера элемента массива называется индексом элемента. Пример. Можно ссылаться на элемент х[4], элемент х[i], элемент x[4+j] массива х. При текущих значениях переменных i = 2 и j = 1 эти индексы определяют, соответственно, 4-й, 2-й и 5-й элементы массива. Для обозначения (нового типа объектов) массивов в алгоритмических языках обычно вводится специальное служебное слово. Пример. В ШАЯ – это слово "таб", после которого приводится имя массива и в квадратных скобках его размерность, например, для одномерного массива – в виде [m:n], где m – номер первого элемента массива (часто 1), n – номер последнего элемента (шаг перебора элементов равен 1). На Паскале имеется соответствующее слово array. Вышеуказанная последовательность из пяти чисел описывается на ШАЯ в виде: вещ таб x[1:7], а на Паскале (в рамках рассматриваемого нами его ядра) необходимо указывать предельную величину размерности: x: array [1..100] of real;. Двумерный массив (матрица, прямоугольная таблица) – совокупность одномерных векторов, рассматриваемых либо "горизонтально" (векторов-строк), либо "вертикально" (векторов-столбцов) и имеющих одинаковую размерность, одинаковый тип и общее имя. Матрицы, как и векторы, должны быть в алгоритме описаны служебным словом (например, таб или array), но в отличие от вектора, матрица имеет описание двух индексов, разделяемых запятыми: первый определяет начальное и конечное значение номеров строк, а второй – столбцов. Пример. Если матрица x описана в виде x: array [1..5, 1..3] of real; , то определяется таблица из 5 строк (от 1-й до 5-й строки) и 3 столбцов (от 1-го до 3-го столбца) вида: (столбец 1) (столбец 2) (столбец 3) x11 x12 х13 (строка 1) x21 x22 х23 (строка 2) х31 х32 х33 (строка 3) х41 x42 х43 (строка 4) х51 x52 х53 (строка 5) Для актуализации элемента двумерного массива нужны два его индекса – номер строки и номер столбца, на пересечении которых стоит этот элемент. Пример. Элемент х[3,2] – элемент на пересечении 3-й строки и 2-го столбца массива х. Рассмотрим ряд задач, решаемых с помощью массивов. Пример. Составим алгоритм (программу) нахождения суммы и произведения всех элементов одномерного массива. Метод решения: начиная с нулевого значения суммы, добавляем поочередно новый элемент ряда и находим значение искомой суммы; начиная с начального, единичного произведения, находим искомое произведение, умножая текущее значение произведения на очередной элемент ряда. Алгоритм (программа) имеет вид Program SPM1; Uses Crt; Var x: array [1..100] of real; n, i: integer; s, р: real; Begin ClrScr; WriteLn('Введите размерность массива :'); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } WriteLn('Введите элементы массива:'); { приглашение к вводу массива } for i:=1 to n do { цикл ввода элементов массива } begin write('x[',i,']='); { приглашение к вводу текущего элемента массива} readln(x[i]) { ввод текущего элемента массива } end; s:=0; { начальное значение суммы – нуль } p:=1; { начальное значение произведение – единица [u1]} for i:=1 to n do { цикл вычисления суммы и произведения } begin s:=s+x[i]; { добавление к сумме очередного слагаемого } p:=p*x[i] { домножение произведения на очередной множитель } end; WriteLn('Полученная сумма равна ', s: 3:3); { вывод полученной суммы } WriteLn('Полученное произведение равно ', p: 3:3); { вывод полученного произведения } End. Пример. Составим алгоритм вычисления суммы бесконечного ряда чисел а[1], а[2], а[3], ... с точностью е, при условии, что точность всегда достигается для номера члена ряда не более 1000000 (это "неестественное" ограничение нужно для того, чтобы в Паскале было проще объявить размерность массива а). Метод решения: сравниваем две суммы – одна сумма была получена на предыдущем шаге суммирования, а вторая – добавлением к ней очередного слагаемого (то есть их разность и равна очередному добавленному элементу ряда); процесс суммирования продолжается до тех пор, пока разность по модулю не станет меньше точности суммирования. Алгоритм (программа) имеет вид Program SumND; Uses Crt; Var a: array [1..1000000] of real; i: integer; e, p, s: real; begin ClrScr; WriteLn('Введите точность :'); { приглашение к вводу входного параметра } ReadLn(e); { ввод входного параметра } i:=1; { начальный номер члена ряда } WriteLn(‘введите первые два элемента :’); { приглашение к вводу входных параметров } ReadLn(a[1], a[2]); { ввод входных параметров } р:=а[1]; { запоминаем начальную сумму – сумму одного элемента } s:=р+a[2]; { запоминаем начальную следующую сумму – сумму двух элементов } while (abs(s–p)>e) do { цикл суммирования, пока слагаемые влияют на сумму } begin i:=i+1; { переход к следующему элементу } p:=s; { "старую" сумму заменяем "новой", полученной добавлением еще одного } s:=s+а[i]; { вычисляем "новую" сумму } WriteLn(‘введите a[‘, i, ‘]=’); { приглашение к вводу очередного элемента ряда } ReadLn(a[i]); { ввод очередного элемента ряда } end; WriteLn('Полученная сумма равна ', s: 3:3); { вывод результата } End. Пример. Составим алгоритм вычисления значения полинома Pn(x) = а0хn + а1хn–1 + ... + аn для заданного значения x. Метод решения – метод (схема) Горнера. Опишем его. Заметим, что: 1) при n = 0, P0(x) = a0 ; 2) при n = 1, P1(x) = a0x + a1 = P0(x) x + a1 ; 3) при n = 2, P2(х) = a0x2 + a1x + a2 = (a0x + a1)x + a2 = P1(x)x + a2 ; . . . n) Pn(x) = a0xn + a1xn–1 + ... + an–1x + an = (a0xn–1 + a1xn–2 + ... + an–1)x + an = Pn–1(x)x + an . Таким образом, всегда верно рекуррентное соотношение Горнера: Текущее Р := Предыдущее Р*x + Текущий коэффициент полинома. Эту схему реализуем в алгоритме (программе) вида: Program Gorner; Uses Crt; Var a: array [0..100] of real; n, i: integer; p, x: real; Begin ClrScr; WriteLn('Введите порядок полинома :'); { приглашение к вводу входного параметра } ReadLn(n); { ввод первого входного параметра } WriteLn('Введите число x :'); { приглашение к вводу второго входного параметра } ReadLn(x); { ввод второго входного параметра } for i:=0 to n do { цикл схемы Горнера } begin WriteLn('a[',i,']='); { приглашение к вводу очередного коэффициента полинома} ReadLn(a[i]); { ввод очередного коэффициента полинома } end; p:=a[0]; { начальное (для n=0) значение полинома – см. схему Горнера} for i:=1 to n do { цикл накапливания значения полинома по схеме Горнера } p:=p*x+a[i]; { находим полином текущей степени i используя предыдущий } WriteLn('Полученнoe значение p = ', p:3:3); { вывод результата } End. Пример. Составим алгоритм вычисления суммы и произведения всех элементов a[i,j], i = 1, 2, ..., n; j = 1, 2, ..., m заданной матрицы. Метод решения: построчно проходя все элементы массива, добавляем к предыдущему значению суммы новый элемент матрицы и умножаем предыдущее значение произведения на этот же элемент. Алгоритм (программа) имеет вид Program SPM2; Uses Crt; Var a: array [1..100,1..100] of real; n, m, i, j: integer; s, p: real; Begin ClrScr; WriteLn('Введите количество строк:'); { приглашение к вводу входного параметра } ReadLn(n); { ввод первого входного параметра } WriteLn('Введите количество столбцов:'); { приглашение к вводу второго параметра } ReadLn(m); { ввод второго входного параметра } for i:=1 to n do { цикл ввода – перебора строк } for j:=1 to m do { цикл перебора элементов текущей строки } begin WriteLn('a[',i,',',j,']='); { приглашение к вводу очередного элемента массива } ReadLn(a[i,j]); { ввод очередного элемента массива } end; s:=0; { начальное значение суммы – нуль } p:=1; { начальное значение произведения – единица } for i:=1 to n do { цикл перебора строк для суммирования } for j:=1 to m do { цикл перебора элементов строки (столбцов) для суммирования } begin s:=s+a[i,j]; { добавление очередного элемента к текущему значению суммы} p:=p*a[i,j]; { умножение текущего значения произведения на новый элемент } end; WriteLn('Сумма равно : ', s:3:3); { вывод первого результата } WriteLn('Произведение равно : ', p:3:3); { вывод второго результата } End.