Главная arrow Учебники arrow Информатика 9 класс Босова Л.Л. 2013 arrow §2.2 Одномерные массивы целых чисел

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

Одномерные массивы целых чисел, Массив, Описание массива, Заполнение массива, Вывод массива, Обработка массива, Последовательный поиск, Сортировка, Вычисление суммы элементов массива, Последовательный поиск в массиве, Сортировка массива, Информатика 9 класс Босова, Информатика 9 класс

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

2.2.1. Описание массива
Перед использованием в программе массив должен быть описан, т. е. должно быть указано имя массива, количество элементов массива и их тип. Это необходимо для того, чтобы выделить участок памяти нужного размера для хранения массива. Общий вид описания одномерного массива:
var <имя_массива>: array [<мин_знач_индекса> ..
    макс_знач_индекса>] of <тип_элементов>;

Пример
   var a: array [1..10] of integer;
Здесь описан массив а из 10 целочисленных значений. При выполнении этого оператора в памяти компьютера будет выделено место для хранения десяти целочисленных переменных.
Массив, элементы которого имеют заданные начальные значения, может быть описан в разделе описания констант:
   const b: array [1..5] of integer = (1, 2, 3, 5, 7);
В этом случае не просто выделяются последовательные ячейки памяти — в них сразу же заносятся соответствующие значения.

2.2.2. Заполнение массива
Заполнять массив можно либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения в программе. При этом может использоваться цикл с параметром.
Например, для ввода с клавиатуры значений элементов описанного выше массива а используется следующий цикл с параметром:
   for i:=1 to 10 do read (a[i]);
Задавать значения элементов массива можно с помощью оператора присваивания. Например:
   for i:=1 to 10 do a[i] :=i;
В следующем фрагменте программы организовано заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99:
   randomize;
   for i:=1 to 10 do a[i]:=random(100);


2.2.3. Вывод массива
Во многих случаях бывает полезно вывести значения элементов массива на экран. Так, если значения массива генерировались случайным образом, то необходимо знать, каков исходный массив. Также нужно знать, каким стал массив после обработки.
Значения элементов массива можно вывести в строку, разделив их пробелом:
   for i:=1 to 10 do write (a[i], ' ');
Более наглядным является следующий вариант вывода с комментариями:
   for i:=1 to 10 do writeln ('a[', i, '] = ', a[i]);
На основании рассмотренных примеров запишем программу, в которой осуществляется: заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99; вывод массива а на экран.

program n_2;

Заголовок программы

var

   i: integer;

   a: array [1..10] of integer;

Блок описания переменных            

begin

   randomize;

   for i : = 1 to 10 do

      a[i]:= random(100);

   for i := 1 to 10 do

      writeln ('a[', i, ']=', a[i] )

end.

Программный блок

Заполнение массива

Вывод массива


2.2.4. Вычисление суммы элементов массива
Пример. В некотором населённом пункте п домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта количества жителей населённого пункта.
Исходные данные (количество жильцов) здесь представлены с помощью одномерного массива а, содержащего п элементов: а[1] — количество жильцов дома 1, а[2] — количество жильцов дома 2, ..., а\n\ — количество жильцов дома n. В общем случае a[i] — количество жильцов дома i, где i принимает целочисленные значения от 1 до n (i = 1, n). Результат работы алгоритма обозначен через s.
Алгоритм подсчёта количества жителей населённого пункта
Суммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых:
1) определяется ячейка памяти (переменная s), в которой будет последовательно накапливаться результат суммирования;
2) переменной s присваивается начальное значение 0 — число, не влияющее на результат сложения;
3) для каждого элемента массива из переменной s считывается её текущее значение и складывается со значением элемента массива; полученный результат присваивается переменной s.
Описанный процесс наглядно можно изобразить так:

s:= 0

s = 0

s:= s + a[1]

s = 0 + a[1]

s:= s + a[2]

s = 0 + a[1] + a[2]

s:= s + a[3]

s = 0 + a[1] + a[2] + a[3]

...

 

s:= s + a[n]

s = 0 + a[1] + a[2] + a[3] + ... + a[n]

Запишем соответствующую программу на языке Паскаль.

program n_3;

Заголовок программы

const

   n=20;

var

   i, s: integer;

   a: array [1..n] of integer;

Блок описания используемых данных

begin

   randomize;

   for i := 1 to n do

   begin

      a[i]:= random(100)+50;

      writeln ('а [', i, ' ] = ' , a[i])

   end;

   s := 0;

   for i :=1 to n do

      s := s + a [i];

   writeln ('s=', s)

end.

Программный блок

Заполнение и вывод массива

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

Вывод результата

Сравните программы n_2 и n_3. Выделите в них общие блоки. Обратите внимание на различия.

2.2.5. Последовательный поиск в массиве
В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.
Можно выделить следующие типовые задачи поиска:
1) найти наибольший (наименьший) элемент массива;
2) найти элемент массива, значение которого равно заданному значению.
Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.
Рассмотрим подробно решение задач первого типа: нахождение наибольшего (наименьшего) элемента.
Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
1) возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;
2) возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и запишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;
3) повторим действия, описанные в п. 2, для всех оставшихся карточек в стопке.
В итоге на доске будет записано самое большое значение элемента просмотренного массива.
Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве можно искать его индекс. Обозначим искомый индекс imax. Тогда описанный выше алгоритм в сформированном нами массиве а на языке Паскаль можно записать так:

program n_4;

Заголовок программы

var

   i, imax: integer;

   a: array [1..10] of integer;

Блок описания переменных

begin

   randomize;

   for i := 1 to 10 do

   begin

      a[i]:= random(100);

      writeln ('a[', i, '] = ', a[i])

   end;

   imax : = 1;

   for i := 2 to 10 do

      if a[i] > a [imax] then imax := i;

   writeln ('Наибольший элемент массива', a[imax])

end.

Программный блок

Заполнение и вывод массива

Поиск наибольшего элемента массива

Вывод результата

Если в массиве несколько элементов, значения которых равны максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы в ней находился последний из максимальных элементов. Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива?
Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
 - n — индекс элемента массива такой, что а[n] = х, где х — заданное число;
 - сообщение о том, что искомого элемента в массиве не обнаружено. Программа поиска в сформированном нами массиве а значения, равного х, может выглядеть так:

program n_5;

Заголовок программы

var

   i, n, x: integer;

   a: array [1..10] of integer;

Блок описания переменных

begin

   randomize;

   for i := 1 to 10 do

   begin

      a [i]:= random(100);

      writeln ('a [', i, '] = ', a [i])

   end;

   writeln ('x=');

   readln (x);

   n := 0;

   for i : = 1 to 10 do

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

   if n = 0

      then writeln ('Элемента со значением, равным заданному, в массиве нет')

      else writeln ('Индекс элемента,

равного заданному, ', n)

end.

Программный блок

Заполнение и вывод массива

Ввод значения х

Поиск в массиве элемента, равного х

Вывод результата

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

i: =0;
repeat
   i:=i+1;
until (a[i]=x) or (i=10);
if a[i]=x then write(i) else write('Heт')


Здесь выполнение алгоритма будет прервано в одном из двух случаев:
1) в массиве найден первый из элементов, равный заданному;
2) все элементы массива просмотрены.
Запишите полный текст программы и выполните её на компьютере.
Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.
Определите, количество каких элементов подсчитывается в следующем фрагменте программы.

k: =0;
for i:=1 to 10 do
   if a[i]>50 then k:=k+1;
write('k=', k)


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

s: =0 ;
for i:=1 to 10 do
   if (a[i]>50) and (a[i]<60) then s:=s+a[i];
write('s=', s)


Запишите полные тексты двух последних программ и выполните их на компьютере.

2.2.6. Сортировка массива
Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим.
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим.
Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.
Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов1 реализации механизма этой операции — сортировку выбором.
Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:
1) в массиве выбирается максимальный элемент;
2) максимальный и первый элементы меняются местами (первый элемент считается отсортированным);
3) в неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;
4) действия, описанные в n.3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
Рассмотрим процесс сортировки выбором на примере массива а = {0, 1, 9, 2, 4, 3, 6, 5}.

Индекс

1

2

3

4

5

6

7

8

Значение

0

1

9

2

4

3

6

5

Шаги

1

0

1

9

2

4

3

6

5

2

9

1

0

2

4

3

6

5

3

9

6

0

2

4

3

1

5

4

9

6

5

2

4

3

1

0

5

9

6

5

4

2

3

1

0

6

9

6

5

4

3

2

1

0

7

9

6

5

4

3

2

1

0

Итог:

9

6

5

4

3

2

1

0

В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из п элементов такая операция будет проводиться n -1 раз. Объясните почему.
Приведём фрагмент программы, реализующий описанный алгоритм:

for i:=1 to n-1 do
begin
   imax:=i;
   for j:=i+l to n do if a[j]>a[imax] then imax:=j;
   x:=a[i];
   a[i]:=a[imax];
   a[imax]:=x
end;


Здесь мы использовали один цикл внутри другого. Такая конструкция называется вложенным циклом.