понятие массивов. Понятие массив и операции над элементом массива в среде Pascal A. Понятие массив и операции над элементом массива в среде Pascal abc. Массив
 Скачать 0.63 Mb.
|
|
Понятие массив и операции над элементом массива в среде Pascal ABC. Массив — это последовательность однотипных элементов, число которых фиксированно и которым присвоено одно имя. В языках программирования массивы используются для реализации таких структур данных, как последовательности и таблицы (см. статьи “Структуры данных”, “Типы данных”). Положение элемента в массиве однозначно определяется его индексом — номером элемента в последовательности (например, a1, a2, a3, ..., an), номером строки и столбца в таблице (a1 1, a2 5, ..., an n) и т.д. Заполнение массива элементами псевдослучайной последовательности Заполнять массив можно либо считывая значение каждого элемента, либо присваивая элементам некоторые значения. Вводить значения элементов с клавиатуры не всегда удобно. Более того, часто при отладке программы нам надо сделать так, чтобы она работала на произвольных массивах. В этом случае очень удобно задавать значения элементов массива случайным образом, с использованием встроенного в язык программирования так называемого датчика псевдослучайных чисел. Числа называются псевдослучайными, так как для их нахождения используется некая итерационная последовательность ri = f(ri-1), например, ri = (ari-1 + b) mod c, здесь mod — операция взятия остатка от деления на c; a, b, c — некоторые константы. Любая подобная последовательность имеет периодические свойства (т.е., начиная с какого-то момента, числа начнут повторяться в том же самом порядке). В языке программирования Pascal псевдослучайная последовательность реализована функцией random. Если использовать ее без параметров, то при очередном обращении она будет выдавать в качестве результата некоторое псевдослучайное вещественное число из диапазона [0; 1), для этого ri делится на c. Процедура randomize предназначена для задания первого значения в последовательности ri. Для этого она использует текущее значение компьютерного таймера; в результате при разных запусках программы последовательности получаются различными. Обращаться к процедуре randomize имеет смысл только один раз — в начале работы программы. Для получения целых случайных чисел из диапазона [0; n–1] используется вызов функции random с параметром n: random(n). Пример 1. Приведем пример заполнения случайным образом целочисленного массива a, состоящего из n элементов, десятичными цифрами (от 0 до 9 включительно): randomize; for i := 1 to N do a[i] := random(10); Суммирование элементов массива Одной из распространенных операций с массивами является операция нахождения суммы значений элементов массива. Например, это нужно для нахождения среднего арифметического значения элементов. Приведем основной фрагмент решения этой задачи: S := 0; {переменная для накопления результата} for i := 1 to N do S := S + a[i]; Циклический сдвиг элементов массива Под циклическим сдвигом элементов массива подразумевается, что все элементы массива сдвигаются на один элемент влево или вправо, а первый (последний) элемент становится последним (первым). Несмотря на кажущуюся простоту, данная задача вызывает затруднения при сдвиге вправо. А такая операция нужна, например, при реализации вставки элемента в массив (часть массива для этого сдвигается вправо). В данном случае операцию сдвига нужно производить с конца массива: с := a[N]; {запоминаем последний элемент во вспомогательной переменной} for i := N downto 2 do a[i] := a[i - 1]; a[1] := c; Поиск в массиве Поиск максимума и минимума Алгоритм поиска максимального и минимального элементов массива по реализации несколько отличается от аналогичного алгоритма для последовательностей. В массиве правильнее искать не значение максимального или минимального элемента, а индексы соответствующих элементов, тогда автоматически мы будем знать и сами значения. Таким образом, делать двойную работу не нужно (в одной переменной хранить значение максимального элемента, а в другой — ее индекс). Приведем основную часть наиболее экономичного решения задачи обмена местами минимального и максимального элементов массива. imax := 1; {индекс максимального элемента} imin := 1; {индекс минимального элемента} for i := 2 to N do if a[i] > a[imax] then imax := i else if a[i] < a[imin] then imin := i; c := a[imin]; a[imin] := a[imax]; a[imax] := c; Заметим, что если в массиве несколько элементов, равных максимальному и/или минимальному значению, то данная программа найдет первые вхождения максимума и минимума. Поиск числа К в массиве Алгоритм поиска в неупорядоченном массиве, индексы которого меняются от 1 до N, значения, равного K, может выглядеть так: i := 0; repeat i := i + 1 until (i = N) or (a[i] = K); if a[i] = K then write(i) else write(0) При отсутствии в массиве элемента с искомым значением K печатается нулевое значение. Оказывается, что и такую программу можно упростить при использовании так называемого “барьерного” метода, который часто применяется в программировании. В данном случае он заключается в том, что мы заносим в дополнительный элемент массива (например, нулевой) искомое значение K и в условии окончания цикла отказываемся от проверки на выход за границу массива: a[0] := K; i := N; while (a[i] <> K) do i := i — 1; write(i) Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку. Если значений K среди элементов массива несколько, то найдено будет первое справа. Поиск числа К в упорядоченном массиве Рассмотрим массив, элементы которого упорядочены по неубыванию. То есть a1  a2 … an. Поиск элемента, равного K, в таком массиве осуществляется с помощью алгоритма “деления пополам”. По-другому его еще называют бинарным поиском, или дихотомией. Алгоритм заключается в том, что мы сравниваем средний элемент массива с числом K и, в зависимости от результата сравнения, переходим к поиску K либо в левой, либо в правой частях массива. Далее наши действия повторяются, пока рассматриваемая часть массива не будет состоять из одного элемента. Если он не равен K, то такого значения в массиве нет. Приведем пример эффективной реализации данного алгоритма, в результате которой будет найден один из элементов, равный K, или будет обнаружено, что такой элемент в массиве отсутствует:L := 1; R := N; while L < R do begin m := (L + R) div 2; if a[m] < K then L := m + 1 else R := m end; if a[R] = K then write(R) else write(0) На каждом шаге данного алгоритма длина части массива, в которой мы осуществляем поиск элемента, уменьшается в два раза. То есть, если N = 2i, то алгоритм будет выполнять i + 1 = log2N + 1 сравнений. Эта величина существенно меньше, чем N. Так, для N = 103 число сравнений будет равно 11, а для N = 106 — всего 21. Алгоритмы сортировки массивов Задача сортировки массива, то есть перестановки элементов массива так, чтобы они были упорядочены по возрастанию, убыванию или другой аналогичной характеристике, является одной из основных технических задач программирования. С этой задачей мы сталкиваемся и при записи фамилий учеников в классном журнале, и при подведении итогов соревнований, и даже при упорядочении игральных карт, например, при игре в преферанс. Очень часто сортировка используется как первый шаг в алгоритме решения более сложной задачи. Рассмотрим наиболее простые алгоритмы сортировки массивов и подсчитаем их вычислительную сложность (см. “Теория алгоритмов”). “Пузырьковая” сортировка Традиционно наиболее простой в реализации считается так называемая “пузырьковая” сортировка. Суть ее в случае упорядочения по неубыванию заключается в следующем. Будем просматривать слева направо все пары соседних элементов: a1 и a2, a2 и a3, …, an-1 и an. Если при этом ai > ai+1, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своем) месте. Об остальных элементах ничего определенного сказать невозможно. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. И так далее. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров при этом равно N–1. Приведем фрагмент программы, реализующий описанный алгоритм: for j := 1 to n — 1 do {цикл по просмотрам} for i := 1 to n — j do {просмотр массива} if a[i] > a[i + 1] then begin x := a[i]; a[i] := a[i + 1]; a[i + 1] := x end; При оценке вычислительной сложности алгоритмов сортировки обычно отдельно подсчитывают количество операций сравнения и количество операций присваивания, т.к. заранее неизвестно, какая из них окажется более трудоемкой, ведь сравниваться между собой могут не только числа, но и строки, и другие достаточно сложные объекты. Иногда обе операции сопоставимы по трудоемкости. Количество сравнений в данном алгоритме равно N – 1 + N – 2 + N – 3 + ... + 1 = N(N – 1)/2. Количество присваиваний в три раза больше, чем число выполненных обменов. В худшем случае обмен будет производиться после каждого сравнения и общее число присваиваний будет равно 3(N – 1 + N – 2 + N – 3 + ... + 1) = 3N(N – 1)/2. Говорят, что данный алгоритм имеет квадратичную сложность как по числу сравнений, так и по числу присваиваний. “Пузырьковым” он называется потому, что в результате каждого просмотра максимальный из оставшихся элементов оказывается на своем месте — “всплывает”. По-другому такая сортировка называется обменной. Сортировка “прямым выбором” Рассмотрим алгоритм сортировки, основанный на принципиально иной идее. Найдем минимальный элемент в массиве и поменяем его с первым элементом массива. В результате он окажется на своем месте. Затем найдем минимальный элемент среди оставшихся и поменяем его со вторым элементом. На N–1-м шаге мы закончим упорядочивание нашего массива. Такой алгоритм называется сортировкой прямым выбором. Приведем фрагмент программы, реализующий описанный алгоритм: for i := 1 to n — 1 do begin mini := i; for j := i + 1 to n do {ищем минимальный элемент} if a[j] < a[mini] then mini := j {меняем минимальный элемент с i-м} x := a[i]; a[i] := a[mini]; a[mini] := x end; Количество выполняемых операций в данном алгоритме всегда одинаково. Для сравнений оно равно N – 1 + N – 2 + N – 3 + ... + 1 = N(N – 1)/2, а для присваиваний — всего 3(N – 1). Сортировка “подсчетом” То есть данный алгоритм квадратичный по числу сравнений и линейный (эффективный) по числу присваиваний. Пусть нам надо отсортировать массив, состоящий из десятичных цифр. Оказывается, что в этом случае существует гораздо более эффективный алгоритм сортировки по сравнению с рассмотренными выше. А именно, подсчитаем во вспомогательном массиве d количество каждой из цифр. Сделать это можно за один проход массива a. Затем заполним массив a заново согласно значениям массива d: const maxn = 10000; var d : array[0..9] of integer; {массив для подсчета} a : array[1..maxn] of 0..9;{массив цифр} n, i, j, k : integer; begin readln(n); {n — количество цифр} for i := 1 to n do a[i] := random(10); for j := 0 to 9 do d[j] := 0; for i := 1 to n do {подсчет каждой цифры} d[a[i]] := d[a[i]] + 1; k := 0; for j := 0 to 9 do {заполняем a заново} for i := 1 to d[j] do begin k := k + 1; a[k] := j end end. Заметим, что эта программа работает верно и в случае, когда какой-либо из цифр во вводимой последовательности нет совсем. Подобный алгоритм называют сортировкой подсчетом. Его вычислительная сложность в общем случае составляет 2N + 2m операций, где m — количество различных значений среди элементов в массиве (в нашем примере их было всего 10). Очевидно, что если m Ј N и мы можем отвести память для подсчета количества каждого из m возможных значений для элементов массива, то алгоритм будет иметь линейную сложность относительно N. Методические рекомендации Данная тема изучается в курсе программирования на языках высокого уровня. В статье приведены основные задачи, включаемые в контрольно-измерительные материалы по информатике, в том числе в задания ЕГЭ по информатике. Освоение данных алгоритмов на уроках информатики оказывается достаточным для самостоятельного решения в дальнейшем и более сложных задач. В профильном курсе информатики особое внимание надо уделить анализу вычислительной сложности каждого из рассматриваемых алгоритмов. Подобные задания также могут встретиться на экзаменах. При изучении “пузырьковой” сортировкистоит обратить внимание на тот факт, что часто массив оказывается отсортированным уже после нескольких первых итераций алгоритма и дальнейшие итерации не нужны. Поэтому, если на каком-то проходе массива ни один обмен произведен не был, то массив уже отсортирован, и работа алгоритма закончена. Соответствующая программа может выглядеть, например, так: b := true; j := 0; while b do begin {пока есть обмены} b := false; j := j + 1; for i := 1 to n — j do {просмотр массива} if a[i] > a[i + 1] then begin x := a[i]; a[i] := a[i + 1]; a[i + 1] := x; b := true; end end; За рамками статьи остались алгоритмы обработки двухмерных массивов — таблиц. Подобная структура данных часто не рассматривается в базовом курсе информатики. При углубленном изучении программирования зачастую достаточно показать, как с помощью вложенных циклов просмотреть все элементы таблицы. Приведем фрагмент программы, печатающий двухмерный массив, состоящий из N строк и M столбцов, в виде соответствующей таблицы: for i := 1 to N do begin for j := 1 to M do write(a[i,j]:6:1); writeln end; Основные этапы компьютерное моделирование. Первый этап - постановка задачи включает в себя стадии: описание задачи, определение цели моделирования, анализ объекта. Ошибки при постановке задачи приводят к наиболее тяжелым последствиям! · Описание задачи Задача формулируется на обычном языке. По характеру постановки все задачи можно разделить на две основные группы. К первой группе можно отнести задачи, в которых требуется исследовать, как изменятся характеристики объекта при некотором воздействии на него, «что будет, если?...». Например, что будет, если магнитный диск положить рядом с магнитом? В задачах, относящихся ко второй группе, требуется определить, какое надо произвести воздействие на объект, чтобы его параметры удовлетворяли некоторому заданному условию, «как сделать, чтобы?..». · Определение цели моделирования На этой стадии необходимо среди многих характеристик (параметров) объекта выделить существенные. Мы уже говорили о том, что для одного и того же объекта при разных целях моделирования существенными будут считаться разные свойства. Например, если вы строите модель яхты для участия в соревнованиях моделей судов, то в первую очередь вас будут интересовать ее судоходные характеристики. Вы будете решать задачу «как сделать, чтобы…?» А того, кто собирается на яхте в круиз, помимо тех же самых параметров, будет интересовать, внутреннее устройство: количество палуб, комфортабельность и т. п. Для конструктора яхты, строящего компьютерную имитационную модель для проверки надежности конструкции в штормовых условиях, моделью яхты будет изменение изображения и расчетных параметров на экране монитора при изменении значений входных параметров. Он будет решать задачу «что будет, если…?» Определение цели моделирования позволяет четко установить, какие данные являются исходными, что требуется получить на выходе и какими свойствами объекта можно пренебречь. Таким образом, строится словесная модель задачи. · Анализ объекта подразумевает четкое выделение моделируемого объекта и его основных свойств. |