Двумерные массивы данных

Двумерные массивы данных       Занятие 9 1. Урок 1.  Определение    двумерного    массива   данных   и   его формирование  в памяти компьютера. 2. Урок 2.  Поиск информации в двумерных массивах данных. 3. Урок 3.  Прием бинарного поиска искомых значений в массивах данных. 4. Контрольные вопросы и упражнения.   Из определения массива  (см. занятие 8) следует, что это упорядоченный набор переменных одного и того же   типа.   Составляющие   массив   данные   определяются  одним   именем  и   называются  элементами     массива. Каждый элемент массива в памяти компьютера помечается своим номером (адресом), который называется индексом. Массивы данных могут быть одномерными и многомерными по количеству индексов определяющих местонахождение элемента массива в массиве данных. Частным случаем многомерного массива данных является двумерный массив (таблица, матрица). Урок 1. Определение  двумерного массива  данных и его формирование  в памяти компьютера 1.1. Определение двумерного массива данных. 1.2. Формирование двумерного массива данных в памяти компьютера. Практические примеры. 1.1. Определение двумерного массива данных Двумерным массивом  или  матрицей  (таблицей) будем называть такой порядок элементов в ней, когда адрес некоторого элемента массива указан двумя координатами ­ строкой и столбцом (колонкой). Таким примерами может служить Таблица Пифагора, значения элементов которой являются произведением строки   и   столбца,   расстановка     фигур   на   шахматной   доске,   где   позиция   каждой   фигуры   определяется   двумя координатами, одна из которых имеет символьное обозначение, другая цифровое  и т.д.   1.2. Формирование двумерного массива данных в памяти компьютера Для формирования двумерного массива данных в памяти компьютера средствами языка программирования Turbo Pascal необходимо описать его в блоке  описания  переменных,   затем  ввести  данные  в  память компьютера с помощью клавиатуры, либо явно записать в тексте программы, либо прочесть их с диска (дискеты) или использовать генератор случайных чисел. 1.2.1. Описание двумерного массива в тексте программы Двумерный массив описывается аналогично одномерному массиву (см. занятие 8), только размерность массива указывается двумя значениями через запятую в квадратных скобках, например: Var mas :array[1 .. 9, 1 .. 5] of real; i, j :integer; Здесь описан двумерный массив (таблица, матрица), имеющий 9 строк и 5 столбцов с соответствующими индексами i,  принимающим  значения  номера строки    и   j,  принимающим  значения  номера столбца.  В этом  случае в памяти компьютера резервируется 45 (9 * 5) ячеек для размещения в них значений элементов массива. Существует и другой способ описания массивов данных с использованием оператора  type  (раздел типов), в котором   описываются   имена   типов   переменных   отличных   от   стандартных,   т.е.   переменные   типа   "перечисление", ограниченные переменные, массивы и т.д. и имеет следующий формат: type <Имя типа> = array [1 .. m, 1 .. n] of  <Тип данных массива>; var <Имя массива> : <Имя типа>; Например, пусть в программе необходимо описать следующий двумерный массив (матрицу)  Matrix:  752  301   13  9  Описание первым способом выглядит следующим образом: Var  Matrix  : array [1 .. 2, 1 .. 4] of integer;            i, j  : integer; 55 Определение двумерного массива  данных и его формирование. Поиск информации в двумерных массивах.  Прием бинарного поиска в этом случае номер первого элемента 0, а четвертого, соответственно, 3. Var  Matrix    : array [0 .. 1, 0 .. 3] of integer;            i, j   : integer или или Для второго способа имеем Type  Mas = array [1 .. 2, 1 .. 4] of integer;         Var    Matrix : Mas; Type  Mas = array [0 .. 1, 0 .. 3] of integer;         Var    Matrix : Mas; аналогично может быть описан массив любой размерности. 1.2.2. Формирование двумерного массива в памяти компьютера явно в тексте программы Такое формирование возможно для небольших массивов, как правило, при решении учебных задач. Используя предыдущий пример, покажем, как это делается в следующей программе: Program V1L10P1; {Формирование двумерного массива явно в тексте программы} Uses Crt; Var Matrix :array[1..2,1..4] of integer;   i,j :integer; begin ClrScr; {Формирование массива данных} Matrix[1,1]:=2;Matrix[1,2]:=5;Matrix[1,3]:=7;Matrix[1,4]:=13; Matrix[2,1]:=1;Matrix[2,2]:=0;Matrix[2,3]:=3;Matrix[2,4]:=9; {Печать массива данных} WriteLn('Исходный массив'); for i:=1 to 2 do begin   {Внешний цикл} for j:=1 to 4 do Write(Matrix[i,j]:3); {Печать элементов столбцов строки}   {Внутренний цикл} WriteLn end; ReadKey end.   {Перевод строки} Результат работы программы Исходный массив   2  5 13   1  0  9 1.2.3. Формирование двумерного массива в памяти компьютера вводом данных с клавиатуры Формирование массива данных в памяти компьютера можно осуществить вводом этих данных с клавиатуры. На практике такой ввод осуществляется пользователем и в случае больших массивов данных весьма трудоемок и чреват многочисленными ошибками, на устранение которых тратится большое время. Поэтому в производстве, где обрабатывается   значительное   количество   информации,   вводимой   с   каких   либо   документов   вручную,   пользуются специальными программами, проверяющими ее на достоверность.  В последующей программе показан ввод двумерного массива данных в память компьютера с клавиатуры. Ввод значений элементов массива осуществляется с помощью оператора Read,  во внутреннем цикле по столбцам в строку, номер которой определяет внешний цикл.   Program V1L10P2; {Формирование двумерного массива вводом цифровых значений с клавиатуры} Uses Crt; Type Mas=array[0..1,0..3] of integer; Var Matrix:Mas; i,j :integer; begin {} ClrScr; WriteLn('Веди исходный массив'); for i:=0 to 1 do begin {Описание двумерного массива как тип Mas} {Описание типа Mas} {Внешний цикл ввода} for j:=0 to 2 do {Внутренний цикл ввода} 56 Read(Matrix[i,j]); {Ввод данных с клавиатуры} WriteLn; end; WriteLn('Ввуденный с клавиатуры массив массив'); for i:=0 to 1 do begin {Внешний цикл вывода} for j:=0 to 2 do Write(Matrix[i,j]:3); WriteLn {Внутренний цикл вывода} {Вывод строки массива на экран} {Перевод строки} end; ReadKey end. Результат работы программы Введи исходный массив 1 2 3 4 5 6 Введенный с клавиатуры массив   1  2  3   4  5  6 1.2.3. Формирование двумерного массива в памяти компьютера генерацией случайных чисел Массивы   случайных   чисел   используются   в   программировании   для   решения   ряда   прикладных   задач,   где необходимо моделирование случайных процессов, например, компьютерные игры, задачи по вероятностным расчетам и т.д. В данном случае массивы случайных чисел используются в учебном процессе при изучении и решении задач преобразования   и   поиска   необходимой   информации   в   подобных   массивах   данных.   Например,   при   изучении   и исследовании методов       простых     сортировок     необходимо     обрабатывать     достаточно       большие     массивы данных, получить которые в памяти компьютера вводом их с клавиатуры  трудно. Например, двумерный массив данных размерностью 100 * 100 элементов потребует, как минимум, 20000 нажатий на соответствующие клавиши клавиатуры, при   этом   возможны   и   ошибки   ввода.   Поэтому   целесообразно   формировать   массивы   данных,   где   не       требуется конкретные     значения     элементов     массива,         их       генерацией     самим   компьютером,     используя   стандартную математическую функцию Random (см. занятие 5). В   последующем   примере   показано   формирование   двумерного   массива   генерацией   случайных   чисел   в определенном диапазоне. Количество элементов массива  устанавливаетс с клавиатуры. Задача.   Сформировать   в   памяти   компьютера   двумерный   массив,   состоящий   из  m  строк   и  n  столбцов случайных чисел, которые должны генерироваться  в диапазоне  [­5, 7]  и  вывести его на экран дисплея. Значения строк и столбцов принимать соответственно  m 10 n 10 1 ,  1 . Program V1L10P3; {Формирование двумерного массива генерацией случайных чисел} Uses Crt; Var a:array[1..10,1..10] of integer; i,j,m,n,c,d :integer; {} begin ClrScr; Randomize; Write('Введи  количество   строк  '); Read(m); Write('Введи количество столбцов  '); Read(n); WriteLn('Массив случайных чисел'); {Инициализация генератора случайных чисел} {Формирование массива случайных чисел} for i:=1 to m do begin for j:=1 to n do begin {Внешний цикл по строкам} {Внутренний цикл по столбцам} c:=Random(7); d:=Random(5); a[i,j]:=c­d {Генерация случ. числа от 0 до 7} {Генерация случ. числа от 0 до 5} {Значение элемента массива} end; end; {Вывод массива на экран дисплея} 57 Определение двумерного массива  данных и его формирование. Поиск информации в двумерных массивах.  Прием бинарного поиска for i:=1 to m do begin for j:=1 to n do Write(a[i,j]:4); WriteLn end; ReadKey end. Возможный вариант работы программы Введи  количество   строк  3 Введи количество столбцов  4 Массив случайных чисел    3   2   2   1    1  ­3   1   0    4   1   1   1 Урок 2.   Поиск информации в  двумерных массивах данных 2.1.   Поиск элементов массива по их значениям. 2.2. Поиск наибольшего (наименьшего) элемента массива по строке, столбцу, всей матрицы, главной диагонали квадратной матриц. Двумерные массивы данных широко используются в производстве вычислительных работ на ЭВМ и, особенно в задачах  экономических   расчетов   и  поиска  информации.   В   данном   занятии  будут   рассмотрены  некоторые  приемы поиска цифровой информации в двумерных массивах данных. 2.1. Поиск элементов массива по их значениям Данная задача предполагает нахождение элементов по их конкретным значениям или по значениям, лежащим в некотором интервале или вне него. Рассмотрим эту задачу на предлагаемом примере. Задача.  Дан некоторый двумерный массив, состоящий из  m  строк и  n  столбцов целых чисел, лежащих в диапазоне (m ­ n, m + n). Определить количество элементов массива со значениями целой части от (m + n) / 2. Постановка задачи. Значения строк и столбцов массива данных вводить с клавиатуры. 1. 2. Массив данных получить генерацией случайных чисел с распечаткой его на экране дисплея. 3. Результат решения задачи выводить на экран дисплея в виде: "Количество элементов со значением … равно …" . Program V1L10P4; {Определение количества значений элементов массива от целой части (m+n)/2} Uses Crt; Var  a: array[1..10, 1..10] of integer; i,j,k,m,n,c,d,s: integer; {} begin ClrScr; Write('Введи  количество   строк  '); ReadLn(m); Write('Введи количество столбцов  '); ReadLn(n); Randomize; WriteLn('Исходный массив'); for i:= 1 to m do begin {Внешний цикл формирования матрицы по строкам} for j:=1 to n do {Внутренний цикл формирования матрицы по столбцам} begin c:=Random(Abs(m­n)); d:=Random(m+n); a[i,j]:=d­c; Write(a[i,j]:4) end; WriteLn end; {} s:=0; for i:= 1 to m do for j:=1 to n do begin 58 {Случайное значение элемента массива} {Начальное значение счетчика} k:=(m+n) div 2; if a[i,j]=k then s:=s+1 {Расчет значения элемента поиска} {Подсчет количества элемента поиска} end; WriteLn('Количество элементов со значением',k:4,'  равно ',s:4); ReadKey end. Возможный вариант работы программы Введи  количество  строк   3 Введи количество столбцов  4 Исходный массив    2   0   4   4    0   5   1   1    0   3   3   1 Количество элементов со значением    3 равно    2 Данная  задача  решалась в "лоб" т.е. простым перебором массива для сравнения его с искомыми данными. Такой подход к решению задачи исходит из здравого смысла и понятен потому, что массивы  малы и не требуют большого   времени   поиска.   Проблема   возникнет   тогда,   когда   массивы   данных   будут   большими   или   даже   очень большими, что, естественно, приведет к увеличению времени поиска информации них.  И это обстоятельство приведет к поискам приемов сокращения времени этого процесса. Урок 3. Приемы поиска информации в массивах данных 3.1. Алгоритм поиска информации в сортированном массиве данных. Бинарный поиск Начнем   объяснение   этих   приемов   (алгоритмов)   с   некоторой   практической   задачи,   которая   предполагает массив данных, сформированных однажды, и пользователь обращается к нему лишь для поиска информации, по каким либо  поисковым   ключам  (значениям)   будь  это   какой  либо  цифровой или  символьный  код  и  т.д.  При  достаточно большом   количестве   данных,   скорость   поиска   вряд   ли   удовлетворит   пользователя   подобной   базы   данных.   Если упорядочить данные по возрастанию (убыванию) значений поисковых элементов, то возможно сократить время поиска необходимой информации. 3.1. Алгоритм поиска информации в сортированном массиве данных. Бинарный поиск Имея отсортированный массив данных, в данном случае по возрастанию, какого либо поискового значения (кода) и, имея поисковый код, принадлежащий этому массиву, задаемся следующим: 1. Выбираем начало проверки значения кода с середины массива данных, т.е., имея n элементов массива, и начинаем   сравнение   с    n  /   2  элемента   или   целой   части   этого   частного.   Если   искомый   код   меньше выбранного нами значения, то продолжаем данный прием в первой половине, если наоборот, то во второй. Таким образом, происходит отсечение половины сортированного массива от поиска информации там, где заведомо ее нет. Такой прием поиска информации носит название бинарного поиска от английского слова binary  ­ двоичный. 2. Следующий шаг предполагает поиск подобным приемом в определенной первым шагом половине массива данных  и  т.д.  Т.е.  сокращаем  поиск   информации   в геометрической   прогрессии.   Выигрыш   во времени поиска   обеспечивает   предварительная   сортировка   массива   данных,   которая   производится   после обновления его новыми данными соответствующей формы, принятой для этого массива. Контрольные вопросы и упражнения 1. Какие показатели используются для оценки прямых методов сортировок? 2. Какой из прямых методов сортировок является оптимальным по времени сортировки? 3. Какая существует зависимость времени сортировки от количества сортируемых элементов? Для заметок, вопросов и ответов ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ 59 Определение двумерного массива  данных и его формирование. Поиск информации в двумерных массивах.  Прием бинарного поиска ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ 60