Одномерные массивы

Одномерные массивы целых чисел

Разработала: Сергеенкова И.М.,

Учитель информатики,

ГБОУ Школа 1191

Массив  — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве.

В языках программирования массивы используются для реализации таких структур данных, как последовательности и таблицы. 

Мы будем рассматривать одномерные массивы.

Решение разнообразных задач, связанных с обработкой массивов, базируется на решении таких типовых задач, как:

• Описание массива

• Суммирование  элементов  массива;

• Поиск элемента  с  заданными  свойствами;

• Сортировка  массива.

Описание массива

Перед использованием в программе массив должен быть описан, т.е. должно быть указано имя массива, количество элементов массива и их тип.

Это необходимо для того, чтобы выделить в памяти под массив блок ячеек нужного типа. Общий вид описания массива:

Пример

Здесь oписан массив  a   из десяти целочисленных значений.

При выполнении этого оператора в памяти компьютера будет выделено десять ячеек целого типа.

Небольшой массив b с постоянными значениями может быть описан в разделе описания констант:

В этом случае не просто выделяются последовательные 

ячейки памяти — в

них сразу же заносятся соответствующие значения.

Вычисление суммы элементов массива

Описанный процесс наглядно можно изобразить так:

Приведём основной фрагмент решения этой задачи:

Последовательный поиск в массиве

В программировании  поиск   -одна из наиболее часто встречающихся задач невычислительного характера. Можно выделить следующие типовые задачи поиска:

найти наибольший (наименьший) элемент массива;

найти элемент массива, значение которого равно заданному значению.

Компьютер не может сравнить разом весь ряд объектов. На каждом шаге он может сравнивать только два объекта. Поэтому в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.

Рассмотрим подробно решение задач первого типа (нахождение наибольшего (наименьшего) элемента). Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива мажет быть представлена следующим образом:

возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;

возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, инапишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;

повторим действия, описанные в пункте 2, для всех оставшихся карточек в стопке.

В итоге на доске будет записано самое большое значение просмотренного массива.

Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве правильнее искать его индекс.

Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть: 

n — индекс элемента массива такой, что a[n]=x, где x — заданное число;

сообщение о том, что искомого элемента в массиве не обнаружено.

Алгоритм поиска в сформированном нами массиве a значения, равного 50, может выглядеть так:

n:=0;

for i:=1 to 10 do

if a[i]=50 then n:=i;

if n=0 then write ('Нет') else write (i)

В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдет последний из них.

Во многих случаях требуется найти первый из элементов, имею-щих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующую программу:

i:=0;

repeat

i:=i+1;

until(a[i]=50) or (i=10);

if a[i]=50 tehn write (i) else write ('Нет');

Здесь выполнение алгоритма будет прервано в одном из двух случаев:

• в массиве найден первый из элементов, равный заданному;
• все элементы массива просмотрены.

Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.

Сортировка массива

Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.

Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют возрастающим.

Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют убывающим.

Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.

Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов реализации механизма этой операции — сортировку выбором. Сортировка выбором (например, по убыванию) осуществляется следующим образом:

В массиве выбирается максимальный элемент;

Максимальный и первый элементы меняются местами (первый элемент считается отсортированным);

В неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;

Действия, описанные в пункте 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным)

Рассмотрим процесс сортировки выбором на примере массива

  a={0,1,9,2,4,3,6,5}.

В этом массиве из восьми элементов операцию выбора макси-мального элемента мы проводили  7  раз. В массиве из n элементов такая операция

  будет проводиться  n−1  раз.

Задания:

1). Дано описание массива:

constb:array[1..5]ofinteger=(1,12,8,62,111);

Верно ли описан массив?

2). Дано описание массива:

var a:array [1..94] of integer;

Здесь oписан массив  a  из   __?___ целочисленных значений.

  При выполнении этого оператора в памяти компьютера будет выделено ? ячеек целого типа.

Источники:

• Босова Л. Л., Босова А. Ю., Информатика: учебник для 9 класса. М. : БИНОМ. Лаборатория знаний, 217 с.
• http://www.yaklass.ru/p/informatika/9-klass/algoritmizatciia-i-programmirovanie-14692/odnomernye-massivy-tcelykh-chisel-14603