Определение массивов

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

Основные понятия:

Массив обозначается одним именем. Так всю совокупность действительных чисел

1.6, 14.9, -5.0, 8.5, 0.46

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

A(1), A(2), A(3), ..., A(n).

Индекс определяет положение элемента массива данных относительно его начала.

Для рассмотренного выше примера элементами массива А являются:

A(1)=1.6, A(2)=14.9, A(3)=-5.0, A(4)=8.5, A(5)=0.46

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

Формат записи оператора DIM:

DIM имя_массива (максимальный_индекс)

"Имя_массива" обычно выбирается по тем же правилам, что и имена простых переменных.

"Максимальный_индекс" указывает максимально допустимый в программе индекс и должен быть положительным.

Примеры описания массивов:

DIM X(50) " объявление одномерного числового массива X для 50 чисел;

DIM V$(12) "объявление одномерного массива V для 12 символьных элементов.

Объявление массива с переменным размером.

Виды ошибок

Если указать в программе элемент массива с индексом большим, чем значение размерности, объявленное в операторе DIM или принятое по умолчанию, то выдается сообщение об ошибке 9:

Subscript out of range (выход за пределы массива).

Если оператор DIM указан после использования имени массива или массив повторно объявлен, то появляется сообщение 10:

Redimensioned array (повторное задание размерности массива).

Существует два способа присваивания значений элементам массива:

1) cтатический, с использованием операторов DATA, READ и оператора присваивания;

2) динамический, с использованием оператора INPUT и функции RND.

При работе с массивами очень удобно пользоваться оператором цикла FOR...NEXT. В качестве индекса массива используют параметр цикла.

1. Пример статического заполнения массива.

DATA слива,ананас,груша

DATA яблоко,вишня,абрикос

Цикл FOR...NEXT последовательно присваивает значения всем переменным из списка.

2. Пример динамического заполнения массива

INPUT "Введите количество элементов массива ";N

В данном примере используется переменное задание размерности массива.

3. Пример заполнения массива с помощью стандартной функции RND

Одномерный массив – это именованная последовательность, состоящая из пронумерованных элементов одного типа. Элементы могут быть любого имеющегося в Pascal (за исключение файлового) типа данных. Номер, также называемый индексом, имеет каждый элемент массива. Индекс должен быть порядкового типа. Одномерный массив можно объявить как в качестве переменной:

var <имя переменной>: array of <тип элементов>;

так и типа:

type <имя типа> = array of <тип элементов>;

Здесь m – номер первого элемента, а n – последнего. Например, если диапазон задан так: , то это означает, что определен одномерный массив размерностью в 10 элементов, с индексами от 1 до 10.

Для обращения к элементу массива нужно указать его имя и номер: mas[i], тут mas – имя, i – номер. В программе ниже мы объявим массив и произведем простые операции над его элементами.

1 2 3 4 5 6 7 8 9 10 11 12

program array_primer; uses crt; var mas, A: array [ 1 ..10 ] of real ; begin clrscr; mas[ 1 ] := 32 ; mas[ 5 ] := 13 ; mas[ 9 ] := 43 ; A[ 1 ] := (mas[ 9 ] — mas[ 1 ] ) * mas[ 5 ] ; write (A[ 1 ] : 5 : 2 ) ; readkey; end .

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

for i:=1 to n do
begin
mas[i]:=i;
write(mas[i]:3);
end;

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14

program array_random; uses crt; var i: integer ; mas: array [ 1 ..100 ] of integer ; begin clrscr; randomize; for i:= 1 to 100 do begin mas[ i] := random(10 ) ; write (mas[ i] : 2 ) ; end ; readkey; end .

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

Алгоритмы сортировки:

Алгоритмы поиска:

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

program array_max; uses crt; type massiv= array [ 1 ..10 ] of word ; var i, max: integer ; A: massiv; begin clrscr; for i:= 1 to 10 do begin write (‘Элемент №’ , i: 2 , ‘=’ ) ; read (A[ i] ) ; {ввод с клавиатуры} end ; max:= A[ 1 ] ; {пусть первый элемент будет максимальным} for i:= 1 to 10 do if maxwriteln ; write (‘Максимальный элемент = ‘ , max) ; readkey; end .

Для того чтобы сделать программу для поиска минимального элемента нужно всего лишь поменять знак < в 15 строке на >.

Определение количества положительных элементов :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Разделы: Информатика

Тема : Двумерные массивы. Заполнение двумерного массива по заданному правилу.

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

ХОД ЗАНЯТИЯ

1. Актуализация знаний

Массивы, положение элементов в которых описывается двумя индексами, называются двумерными. Структура такого массива может быть представлена прямоугольной матрицей. Каждый элемент матрицы однозначно определяется указанием номера строки и столбца, номер строки – i, номер столбца – j.
Рассмотрим матрицу А размером n*m:

а 11	а 12	а 13	а 14
а 21	а 22	а 23	а 24
а 31	а 32	а 33	а 34

Матрица из 3 строк и 4 столбцов, количество строк n=3, количество столбцов m=4. Каждый элемент имеет свой номер, который состоит из двух чисел – номера строки, в которой находится элемент, и номера столбца. Например, а23 – это элемент, стоящий во второй строке и в третьем столбце.
Двумерный массив на языке Турбо Паскаль можно описать по-разному. Чтобы описать двумерный массив, надо определить какого типа его элементы, и каким образом они пронумерованы (какого типа его индекс). Существует несколько способов описания двумерного массива.

Const maxN=…; {Максимальные значения количества строк}
maxM=…; {Максимальные значения количества столбцов}

1 способ

Type Mas = array of <тип элементов>; {Одномерный массив}
Type TMas = array of Mas; {Одномерный массив, элементами которого являются одномерные массивы}

2 способ

Type TMas = array of array of <тип элементов>;
{Одномерный массив, элементами которого являются одномерные массивы}

3 способ

Type <имя типа>= array of <тип элементов>; {Двумерный массив}

Предпочтение отдается третьему способу описания двумерного массива.

Например:

Const N=3; M=4;
Type TMas= array of integer; {Двумерный массив из целых чисел}

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

1) Формирование двумерного массива при помощи ввода с клавиатуры и алгоритм построчного вывода элементов матрицы.

Const N=10;M=10;
Type Tmas= array of integer;
Var A:Tmas; i,j:integer;
Begin
{Ввод элементов матрицы}
For i:=1 to N do
For j:=1 to M do
Read(A);
{Вывод элементов матрицы}
For i:=1 to N do begin
For j:=1 to M do
Write(A:4); {Печатается первая строка}
Writeln {Переход на новую строку}
end;
End.

2) Фрагмент программы формирования двумерного массива через генератор случайных чисел.

Begin
Randomize; {Инициализация генератора случайных чисел}
{Ввод элементов матрицы}
For i:=1 to N do
For j:=1 to M do
A:=random(45)-22;

2. Изучение нового материала. Заполнение массива по правилу

Рассмотрим несколько фрагментов программ заполнения двумерного массива по некоторому закону. Для этого необходимо вывести правило заполнения.

1. Заполнить массив А размером n*m следующим образом, например

1 2 3 4 5 6 7 8
16 15 14 13 12 11 10 9
17 18 19 20 21 22 23 24
32 31 30 29 28 27 26 25
33 34 35 36 37 38 39 40
48 47 46 45 44 43 42 41

Массив заполняется по принципу «змейки». Правило заполнения: если номер строки – нечетное число, то A=(i-1)*m+j, иначе A=i*m-j+1.

program M1А;

n,m,i,j: integer;
begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do
begin
if i mod 2 = 1 then
A=(i-1)*m+j
else
A=i*m-j+1;
write(A:3);
end;
writeln;
end;
readln;
end.

Приведем пример программы другого способа заполнения по заданному правилу:

program M1В;
var A:array of integer;
n,m,i,j: integer;
c: integer;
begin
readln(n,m);
c:=1;
for i:=1 to n do
begin
for j:=1 to m do
begin
A:=c;
if (i mod 2 = 0) and (j<>m) then
dec(c)
else
inc(c);
write(A:3);
end;
c:=c+m-1;
writeln;
end;
readln;
end.

2. Заполнить массив A по следующему принципу:

1 0 2 0 3 0 4
0 5 0 6 0 7 0
8 0 9 0 10 0 11
0 12 0 13 0 14 0

program M2;
var A:array of integer;
n,m,i,j: integer;
c: integer;
begin
readln(n,m);
c:=0;
for i:=1 to n do
begin
for j:=1 to m do
begin
if (i-1+j) mod 2 = 0 then
A:=0
else
begin
inc(c);
A:=c;
end;
write(A:5);
end;
writeln;
end;
readln;
end.

3. Заполнить массив A по следующему принципу:

1 12 13 24 25 36
2 11 14 23 26 35
3 10 15 22 27 34
4 9 16 21 28 33
5 8 17 20 29 32
6 7 18 19 30 31

var A:array of integer;
n,m,i,j: integer;
c: integer;
begin
readln(n,m);
c:=1;
for j:=1 to m do
begin
for i:=1 to n do
begin
A:=c;
if (j mod 2 = 0) and (i<>n) then
dec(c)
else
inc(c);
end;
c:=c+n-1;
end;
for i:=1 to n do
begin
for j:=1 to m do
write(A:5);
writeln;
end;
readln;
end.

4. Заполнить массив A по следующему принципу:

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

var i,j,m,c,d: integer;

begin
c:=1;
readln(m);
for j:=1 to m do
begin
i:=c;
d:=1;
repeat
A:=d;
inc(i);
if i>m then
i:=1;
inc(d);
until i=c;
dec(c);
if c <= 0 then
c:=m-c;
end;
for i:=1 to m do
begin
for j:=1 to m do
write(A:2);
writeln;
end;
end.

5. Заполнить массив A по следующему принципу:

1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1

var m,i,j: integer;
A:array of integer;
begin
readln(m);
for i:=1 to m do
begin
for j:=1 to m do
begin
if (i=j) or (m-i+1=j) then
A:=1
else
A:=0;
write(A:2);
end;
writeln;
end;
end.

3. Задачи для самостоятельного решения

6 5 4 3 2 1
7 8 9 10 11 12
18 17 16 15 14 13
19 20 21 22 23 24
30 29 28 27 26 25
31 32 33 34 35 36

36 25 24 13 12 1
35 26 23 14 11 2
34 27 22 15 10 3
33 28 21 16 9 4
32 29 20 17 8 5
31 30 19 18 7 6

0 1 1 1 0
1 0 1 0 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0

4) Заполнить массив по следующему принципу:

31 32 33 34 35 36
25 26 27 28 29 30
19 20 21 22 23 24
13 14 15 16 17 18
7 8 9 10 11 12
1 2 3 4 5 6

5) Заполнить массив по следующему принципу:

31 25 19 13 7 1
32 26 20 14 8 2
33 27 21 15 9 3
34 28 22 16 10 4
35 29 23 17 11 5
36 30 24 18 12 6

Домашние задание:

1) Заполнить массив по следующему принципу:

6 7 18 19 30 31
5 8 17 20 29 32
4 9 16 21 28 33
3 10 15 22 27 34
2 11 14 23 26 35
1 12 13 24 25 36

2) Заполнить массив по следующему принципу:

31 32 33 34 35 36
30 29 28 27 26 25
19 20 21 22 23 24
18 17 16 15 14 13
7 8 9 10 11 12
6 5 4 3 2 1

3) Заполнить массив по следующему принципу:

0 1 1 1 0
1 0 1 0 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0

1 Способ (заполнение с клавиатуры. Динамический ввод данных )

M:array of integer;

For I:=1 To 10 Do Begin

Write("Введите ",I," значение ");

2 Способ (с использованием генератора случайных чисел)

M: array of integer;

For I:=1 To 25 Do Begin

M[I]:=Random(50);

3 Способ (статический ввод данных)

M: array of integer = (31,28,31,30,31,30,31,31,30,31,30,31);

For I:=1 To 9 Do

1.4 Примеры решения задач

1. Алгоритмы поиска и присвоения значений элементам массива

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

A:ARRAY OF INTEGER;

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

FOR I:=1 TO N DO Begin

Write("Введите ",I," элемент массива "); ReadLn(A[I]);

{ Обработка элементов массива }

FOR I:=1 TO N DO

IF A[I]>0 THEN WriteLn("Положительный элемент = ",A[I]," его индекс = ",I);

2. Составить программу вычисления и печати значений функции Y=sin(x-1)/2x. Значения аргументов задать в массиве X, состоящего из 6 элементов. Значения функции записать в массив Y.

X,Y:ARRAY OF REAL;

FOR I:=1 TO 6 DO Begin

Write("Введите ",I," значение аргумента "); ReadLn(X[I]);

FOR I:=1 TO 6 DO Begin

Y[I]:=SIN(X[I]-1)/(2*X[I]);

WriteLn(" X= ",X[I]:4:1," Y=",Y[I]:5:2);

3. Дан массив M, состоящий из 30 элементов. Элементы массива - произвольные целые числа. Выдать на экран значение каждого пятого и положительного элемента. Указанные элементы выдать в строку.

M:ARRAY OF INTEGER;

ClrScr; Randomize;

WriteLn(" Значения элементов массива");

FOR I:=1 TO 30 DO Begin

M[I]:=Random(20)-4; Write(M[I]:3);

WriteLn(" Значения каждого пятого и положительного элемента массива");

While I<=30 DO Begin

IF M[I] > 0 THEN Write(M[I]:3);

Примеры для самостоятельного решения:

Дан одномерный массив размерностью 10, заполненный целыми числами, введенными с клавиатуры, и величина N. Отрицательные элементы заменить на N. Измененный массив вывести на экран одной строкой.

Дан одномерный массив размерностью N, заполненный случайными числами в интервале от -15 до 20. Вывести на экран значения элементов массива, абсолютное значение которых >10.

Дан одномерный массив размерностью N, заполненный случайными числами. Каждый третий элемент массива возвести в квадрат, если элемент отрицательный. Измененный массив вывести на экран.

Составить программу вычисления и печати значений функции Y=(sinx+1)cos4x. Значения аргументов задать в массиве X, состоящего из 10 элементов. Значения функции записать в массив Y.

Из элементов массива А, состоящего из 25 элементов, сформировать массив D той же размерности по правилу: первые 10 элементов находятся по формуле Di=Ai+i, остальные - по формуле Di=Ai-i.

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

Уроки 11 - 14
§2.2 Одномерные массивы целых чисел
Описание, заполнение, вывод массива
Вычисление суммы элементов массива
Последовательный поиск в массиве
Сортировка массива

Ключевые слова:

Массив
описание массива
заполнение массива
вывод массива
обработка массива
последовательный поиск
сортировка

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

Массив - это совокупность фиксированного количества однотипных элементов, которым присвоено общее имя. Доступ к отдельному элементу массива осуществляется по его номеру (индексу).

С подобными объектами - числовыми последовательностями - вы уже встречались на уроках математики. Например, члены арифметической прогрессии обозначались так: а 1 , а 2 , а 3 , ..., а n .

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

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

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

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

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

Пример

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

Массив, элементы которого имеют заданные начальные значения, может быть описан в разделе описания констант:

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

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

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

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

Задавать значения элементов массива можно с помощью оператора присваивания. Например:

В следующем фрагменте программы организовано заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99:

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

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

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

Более наглядным является следующий вариант вывода элементов массива с пояснениями в столбик:

На основании рассмотренных примеров запишем программу, в которой осуществляется: заполнение целочисленного массива а , состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99; вывод массива а на экран.

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

Пример . В некотором населённом пункте я домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта количества жителей населённого пункта.

Исходные данные (количество жильцов) здесь представлены с помощью одномерного массива а , содержащего n элементов: a - количество жильцов дома 1, а - количество жильцов дома 2, ..., а[n] - количество жильцов дома n. В общем случае a[i] - количество жильцов дома n, где i принимает целочисленные значения от 1 до n (кратко обозначим это в блок-схеме как ). Результат работы алгоритма обозначен через s.

Суммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых:

1) определяется ячейка памяти (переменная s), в которой будет последовательно накапливаться результат суммирования;
2) переменной s присваивается начальное значение 0 - число, не влияющее на результат сложения;
3) для каждого элемента массива из переменной s считывается её текущее значение и складывается со значением элемента массива; полученный результат присваивается переменной s.

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

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

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

Каким образом в программе n_3 уточнена информация, представленная в примере о домах населённого пункта?

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

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

Можно выделить следующие типовые задачи поиска:

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

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

Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.

Рассмотрим подробно решение задач первого типа: нахождение наибольшего (наименьшего) элемента.

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

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

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

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

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

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

Инвариант цикла - логическое выражение (условие), зависящее от переменных, изменяющихся в теле цикла; оно истинно непосредственно перед началом выполнения цикла и после каждого прохода тела цикла.

Условие «записанное на доске число - самое большое из всех просмотренных до сих пор» является инвариантом цикла для рассмотренного алгоритма.

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

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

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

K - индекс элемента массива такой, что a[k] = х, где х - заданное число;
сообщение о том, что искомого элемента в массиве не обнаружено.

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

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

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

Здесь выполнение алгоритма будет прервано в одном из двух случаев: 1) в массиве найден первый из элементов, равный заданному; 2) все элементы массива просмотрены.

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

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

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

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

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

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

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

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

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

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

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

Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов 1 реализации механизма этой операции - сортировку выбором.

1 С другими способами сортировки вы познакомитесь на уроках информатики в 10-11 классах.

Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:

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

Рассмотрим процесс сортировки выбором на примере массива а = {0, 1, 9, 2, 4, 3, б, 5}.

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

Приведём фрагмент программы, реализующий описанный алгоритм:

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

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

2.2.7. Другие структуры данных

Многие современные приложения (диалоговые, сетевые, инструментальные системы, операционные системы и др.) работают с данными, объём которых заранее не может быть ограничен определённой величиной. Предположим, разрабатывается большой программный комплекс, при работе которого в оперативной памяти будет храниться большое количество различных данных, представленных в форме массивов. Область памяти, отводимая для каждого массива, непрерывна; границы области во время выполнения программы строго фиксированы. Так как объём данных заранее неизвестен, программистам придётся указывать максимально возможные размеры используемых массивов. В результате этого для хранения всех возможных данных может оказаться недостаточно доступной памяти. При этом на практике крайне редко будут встречаться ситуации, когда каждый массив будет полностью заполнен - во многих из них часть зарезервированной памяти будет оставаться свободной. Жёсткие границы не позволяют перераспределять пустое пространство одних массивов в пользу других. Как результат - неэффективное использование оперативной памяти. Выходом в этой ситуации является замена при проектировании программы некоторых массивов на списки, которые занимают именно столько памяти, сколько действительно нужно в данный момент, и не создают никаких запасов.

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

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

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

Рис. 2.3. Линейный список

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

САМОЕ ГЛАВНОЕ

Массив - это совокупность фиксированного количества однотипных элементов, которым присвоено общее имя. Доступ к отдельному элементу массива осуществляется по его номеру (индексу).

Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива:

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

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

Вопросы и задания

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

2. Может ли массив одновременно содержать целые и вещественные значения?

3. Для чего необходимо описание массива?

4. Что вы можете сказать о массиве, сформированном следующим образом?

а) for i:=l to 10 do a[i]:=random(101)-50;
б) for i:=l to 20 do a[i]:=i;
в) for i:=l to 5 do a[i]:=2*i-l;

5. Выполните на компьютере программу решения задачи, рассмотренной в примере пункта 2.2.4. Считайте количество жильцов дома случайным числом из диапазона от 50 до 200 человек, а число домов n = 30.

6. Рядом с вами находятся две корзины. Первая наполнена яблоками разных размеров, вторая - пустая.

Шаг 1 . Вы берёте любое яблоко из первой корзины и кладёте его на стол перед собой.

Шаг 2 . Вы достаёте следующее яблоко из первой корзины и выполняете сравнение:

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

Вы повторяете шаг 2 до тех пор, пока первая корзина не опустеет.

Какое яблоко окажется на столе в самом конце? Попытайтесь сформулировать, что является инвариантом цикла в приведённом алгоритме. Сформулируйте условие задачи с использованием терминологии, рассмотренной в этом параграфе.

7. Напишите программу, которая вычисляет среднюю за неделю температуру воздуха. Исходные данные вводятся с клавиатуры.

8. Дан массив из десяти целых чисел. Напишите программу подсчёта количества элементов этого массива, имеющих максимальное значение.

9. В классе 20 учеников писали диктант по русскому языку. Напишите программу, подсчитывающую количество двоек, троек, четвёрок и пятёрок, полученных за диктант.

10. Объявлен набор в школьную баскетбольную команду. Известен рост каждого из п учеников, желающих попасть в эту команду. Составьте алгоритм подсчёта количества претендентов, имеющих шанс попасть в команду, если рост игрока команды должен быть не менее 170 см. Запишите на языке Паскаль программу. Считайте рост претендента в команду случайным числом из диапазона от 150 до 200 см, а число претендентов n = 50.

11. В целочисленных массивах а и b содержатся длины катетов десяти прямоугольных треугольников (а[i] - длина первого катета, b[i] - длина второго катета i-ro треугольника). Напишите программу, которая по имеющимся данным определит треугольник с наибольшей площадью и выведет его номер, длины катетов и площадь. Предусмотрите случай, когда таких треугольников несколько.

12. Занесите информацию о десяти европейских странах в массивы n (название страны), k (численность населения), s (площадь страны). Напишите программу, выводящую названия стран в порядке возрастания плотности их населения.

13. Найдите информацию о таких частных случаях списка, как стек и очередь. Подготовьте короткое сообщение.