Реферат: Описание массива

МАССИВЫ


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

Массивом называется упорядоченная последовательность величин, обозначенная одним именем.

Массив можно условно изобразить в виде прямоугольника с n делениями, каждое деление – это элемент массива, он имеет свой номер (индекс). Индекс записывается рядом с именем массива в квадратных скобках


3

12

-2

…

4

10

A[1]

A[2]

A[3]

…

A[n-1]

A[n]



Массив обозначается одним именем (А).

Каждый элемент массива обозначается именем массива с индексом (А[1]). Индекс записывается в квадратных скобках после имени массива и определяет порядковый номер элемента.

Элементы упорядочены по значениям индекса.
^ Описание массива
Рассмотрим описание массива на конкретном примере


3

12

-2

-8

4

10

-5

A[1]

A[2]

A[3]

А[4]

A[5]

A[6]

А[7]

А- имя переменной типа массив. В описании типа мы должны указать, что объявляется тип массив, для этого используется служебное слово array, указать границы изменения индексов. У нас 7 элементов, следовательно, индекс изменяется от 1 до 7. Синтаксически это записывается следующим образом 1..20, называется такая запись - диапазон.

В разделе переменных на языке Паскаль массив описывается следующим образом:
Var
A: array [1..7] of integer;

{все элементы массива являются целыми числами}


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

Замечания:
^ Если несколько массивов имеют одинаковый диапозон индексов и одинаковый базовый тип, то допускается объединять массивы в список: Var A,В,С: array [1..20] of integer;



В качестве индекса может быть:

константа А[5] – 5-ый элемент массива А

переменная А[i] – i-ый элемент массива А

выражение А[i+2]– i+1-й элемент массива А

Элемент массива называют переменной с индексом.


Работа с элементами массива

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

^ B[5]:=A[3]+7; S:=S+A[i]; P:=SQRT(A[7]); S:=A[1]+A[5];


ОСНОВНЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С ОДНОМЕРНЫМИ МАССИВАМИ

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

Заполнение одномерного массива значениями (ввод данных)

Заполнить элементы одномерного массива значениями мы можем:

Вводя значения с клавиатуры;

Случайным образом;

По формуле;

С помощью оператора присваивания :=

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

Будем считать, что объявили массив из 10 элементов.


^ А) заполнение с клавиатуры.

WRITE(‘Введите 10 чисел:’);

FOR i:=1 to 10 DO

READ(A[i]);

WRITELN;

Б) случайным образом. Для этого мы должны подключить датчик случайных чисел.

FOR i:=1 to 10 DO

A[i]:=random(n);

n должно быть заранее задано, например 100

В) заполнение по формуле. Каждый элемент массива должен быть рассчитан по формуле (например а[i]=2* i).

FOR i:=1 to 10 DO

A[i]:=2*i;
^ Г) с помощью оператора :=

A[1]:=3; A[2]:=12;
A[3]:=-2; …
Вывод на экран значений элементов одномерного массива.
А) в строчку FOR i:=1 to 10 DO
WRITE(A[i],’ ‘);
Б) в столбик FOR i:=1 to 10 DO
WRITELN(‘A[‘,i,’]=’,A[i]);


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

Заполнить массив A[1..7] целыми значениями с клавиатуры и вывести на экран в строчку.

Program f;
Var
A: array [1..7] of integer;

i:integer;

Begin

WRITE(‘Введите 7 чисел:’);

FOR i:=1 to 7 DO

READ(A[i]);

WRITELN;
^ FOR i:=1 to 10 DO
WRITE(A[i],’ ‘);

End.

Заполнить массив В[1..5] целыми значениями с клавиатуры и вывести на экран в столбик.

Заполнить массив A[1..7] вещественными значениями с клавиатуры и вывести на экран в строчку.

Заполнить массив A[1..5] по формуле А[i]:=i+2 и вывести на экран в столбик.

Заполнить массив A[1..5] по формуле А[i]:=1/i и вывести на экран в столбик.

Заполнить массив В[1..5] целыми значениями с клавиатуры и вывести на экран сумму пятого и третьего элементов.

Заполнить массив В[1..5] целыми значениями с клавиатуры и вывести на экран произведение первого и четвертого элементов..

Составьте программу, которая формирует массив В из 12 элементов. После заполнения массива вывести на экран: А) квадраты этих чисел; Б) обратные величины этих чисел.

Заполнить массив A[1..7] и вывести на экран только положительные элементы.


ОСНОВНЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С ОДНОМЕРНЫМИ МАССИВАМИ

Вычисление суммы элементов массива.
^ А) суммы всех элементов

S:=0;

FOR i:=1 to 10 DO

S:=S+A[i];


Б) по условию

Например, суммы элементов массива, кратных 3

S:=0;

FOR i:=1 to 10 DO

IF A[i] mod 3=0 then S:=S+A[i];





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

^ А) по простому условию

Например, найти количество элементов, равных 0


К:=0;

FOR i:=1 to 10 DO

IF A[i]=0 then К:=К+1;


Б) по сложному условию

Например, найти количество элементов, нечетных и отрицательных одновременно

К:=0;

FOR i:=1 to 10 DO

IF (A[i]<0)and(A[i] mod 2<>0) then К:=К+1;




Вычисление суммы и количества одновременно, вычисление среднеарфметического значения.

Например, найти среднеарифметическое значение положительных элементов массива.

^ Program srarif;
Var
A: array [1..10] of integer;

S,K,i:integer;

Begin

WRITE(‘Введите 10 чисел:’);

FOR i:=1 to 10 DO

READ(A[i]);

WRITELN;

S:=0; K:=0;

FOR i:=1 to 10 DO

IF A[i]>0 then begin S:=S+A[i]; K:=K+1; end;

SR:=S/K;

WRITE(‘среднеарифм. значение полож. элементов=’,SR)

end.



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

Нахождение индекса i элемента A[i] по его значению х (т.е. нахождение такого i, что A[i]=x) принято называть поиском элемента х в массиве а. Простейший алгоритм поиска такой: будем перебирать все элементы массива от начала до конца. Если очередной элемент равен х, то запомним его индекс в величине N.

N:=0;

FOR i:=1 to 10 DO

IF A[i]=x then N:=i;


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


В массиве А[1..7] найти сумму отрицательных элементов.

В массиве А[1..7] найти сумму нечетных элементов.

В массиве А[1..7] найти сумму элементов, кратных 3 или 5.

В массиве А[1..7] найти сумму четных элементов, кратных 7.

В массиве А[1..6] найти сумму положительных элементов, которые находятся в диапазоне от -1до 5 включительно.

В массиве А[1..6] найти количество положительных элементов.

В массиве А[1..6] найти количество элементов, которые находятся в диапазоне от 2 до 10 включительно.

В массиве А[1..6] найти количество элементов, равных 10.

Определите, сколько элементов массива А[1..8] не превышают заданного числа 10.

Определите среднее арифметическое всех элементов массива А[1..10], удовлетворяющих условию А[i]>5.

Определите среднее арифметическое четных элементов массива А[1..10].

Найти номер элемента массива А[1..5], равного 3.

Найти произведение элементов массиваА[1..5].

Найти произведение элементов массива А[1..5], кратных 3.

Вычислить сумму четных элементов массива до первого встречного нулевого элемента.

Подсчитать количество элементов массива, которые совпадают со своим номером и при этом кратны 3.

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



ОСНОВНЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С ОДНОМЕРНЫМИ МАССИВАМИ


Копирование.




^ Копирование массива А в массив В без изменения

FOR i:=1 to 10 DO

В[i]:=A[i];

Копирование массива А в массив В в обратном порядке

FOR i:=1 to 10 DO

В[i]:=A[10-i+1];

Копирование по условию

Например, скопировать массив А в массив В следующим образом: все элементы < 0 заменить на 0, остальные удвоить.

FOR i:=1 to 10 DO

IF A[i]<0 then B[i]:=0

^ Else В[i]:=A[i]*2;


Корректировка

В массиве А все элементы, большие 100, заменить на 100.


FOR i:=1 to 10 DO

IF A[i]>100 then A[i]:=100;


^ Копирование по условию части массива

Дан массив А. Скопировать в массив В только положительные элементы массива А

K:=0;

FOR i:=1 to 10 DO

IF A[i]>0 then begin

K:=K+1;

B[K]:=A[i];

End;
^ FOR i:=1 to K DO
WRITE(B[i],’ ‘);

Заполнение по условию части массива

Дан массив А. Заполнить массив В индексами элементов массива А, кратных 3

K:=0;

FOR i:=1 to 10 DO

IF A[i] mod 3=0 then begin

K:=K+1;

A[K]:=i;

End;
^ FOR i:=1 to K DO
WRITE(B[i],’ ‘);



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

Скопировать массив А в массив В следующим образом: все элементы < 0 заменить на 5, от остальных отнять 10.

В массиве А все элементы, меньшие 10, заменить на их квадраты.

В массиве А все элементы, кратные 3, заменить на 0.

Дан массив А. Скопировать в массив В только нечетные элементы массива А.

Дан массив А. Скопировать в массив В элементы массива А, лежащие в диапазоне от 0 до 10 включительно.

Скопировать массив А в массив В следующим образом: все положительные элементы без изменения, к остальным добавить 100.

Скопировать массив А в массив В следующим образом: все четные элементы разделить на 2, остальные возвести в квадрат.

В массиве А все элементы, большие 4, заменить на 100, остальные на 0.

Дан массив А. Заполнить массив В индексами отрицательных элементов массива А.

Дан массив А. Заполнить массив В индексами элементов массива А, равных 0.

Дан массив В[1..5]. Заполнить массив C таким образом: С[i] есть разница между B[i] и среднеарифметическим значением массива В.



ОСНОВНЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С ОДНОМЕРНЫМИ МАССИВАМИ


Поиск максимального (минимального) элемента массива и его индекса

Построим алгоритм поиска максимального элемента таким образом: введем две дополнительные переменные с именами max и imax. Присвоим им начальные значения – переменной max значение первого элемента массива, imax номер первого элемента. Затем начиная со второго элемента массива сравниваем каждый элемент с переменной max, если его значение оказывается больше, то присваиваем его переменной max и переменной imax присваиваем индекс этого элемента.

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

^ Program poisk;
Var
A: array [1..10] of integer;

Max,imax,i:integer;

Begin

WRITE(‘Введите 10 чисел:’);

FOR i:=1 to 10 DO

READ(A[i]);

WRITELN;

Max:=A[1];

Imax:=1;

FOR i:=2 to 10 DO

IF A[i]>Max then begin Max:=A[i]; imax:=i; end;

WRITE(‘Максимальный элемент=’,Max,’ его индекс=’,imax)

end.


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

Определить рост самого низкого игрока команды и его порядковый номер. В команде 10 игроков.

В массиве А[1..7] найти сумму максимального и минимального элементов.

Найти минимальный элемент среди положительных элементов массива А[1..10].

Найти максимальный элемент среди отрицательных элементов массива А[1..10].

Найти сумму элементов, стоящих до максимального элемента (включая и его) в массиве А[1..10].

После минимального элемента посчитать количество нулей в массиве А[1..10].

После максимального элемента все элементы массива А[1..7] умножить на 10.

В массиве А[1..10] между минимальным и максимальным элементом найти сумму элементов массива.

В массиве А[1..10] между минимальным и максимальным элементом найти сумму элементов массива.

В массиве А[1..10] между минимальным и максимальным элементом найти количество четных элементов массива.




Обмен (Метод трех стаканов)

Введите два числа. Обменяйте их местами и выведите их на экран.

Для обмена чисел местами необходимо ввести дополнительную переменную.

Program M3;
Var
A,B,C:integer;

Begin

WRITE(‘Введите 2 числa:’);

READ(A,B);

WRITELN;

C:=A; A:=B; B:=C;  С – дополнительная переменная

WRITE(‘A=’,A,’ B=’,B)

end.

первый элемент массива поменять с последним

С:=A[1]; A[1]:=A[10]; A[10]:=C;

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

С:=A[2]; A[2]:=A[imax]; A[imax]:=C;

минимальный элемент массива поменять с максимальным

С:=A[imin]; A[imin]:=A[imax]; A[imax]:=C;

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

В массиве А[1..10] поменять третий элемент с первым. Вывести массив на экран.

В массиве А[1..10] поменять пятый элемент с последним. Вывести массив на экран.

В массиве А[1..10] минимальный элемент массива поменять с первым. Вывести массив на экран.

В массиве А[1..10] максимальный элемент массива поменять с последним. Вывести массив на экран.

В массиве А[1..10] минимальный элемент массива поменять с максимальным. Вывести массив на экран.

ОСНОВНЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С ОДНОМЕРНЫМИ МАССИВАМИ

Сортировка

Сортировка – это такая перестановка элементов, после которой они оказываются упорядоченными требуемым образом.

^ Метод «Пузырька»

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

FOR i:=1 to N-1 DO

FOR J:=1 to N-i DO

^ IF A[J]>A[J+1] then

Begin

С:=A[J]; A[J]:=A[J+1]; A[J+1]:=C;

end;

Проследим процесс упорядочивания массива в динамике:

1. Упорядочить по возрастанию массив: 2, 3, 4, 1.

I

J

Массив

1

1

2, 3, 4, 1




2

2, 3, 4, 1




3

2, 3, 1, 4

2

1

2, 3, 1, 4




2

2, 1, 3, 4

3

1

1, 2, 3, 4

^ 2.Упорядочить по возрастанию массив: 3, 5, 6, 7, 1, 4.

I

J

Массив

1

1

3, 5, 6, 7, 1, 4




2

3, 5, 6, 7, 1, 4




3

3, 5, 6, 7, 1, 4




4

3, 5, 6, 1, 7, 4




5

3, 5, 6, 1, 4, 7

2

1

3, 5, 6, 1, 4, 7




2

3, 5, 6, 1, 4, 7




3

3, 5, 1, 6, 4, 7




4

3, 5, 1, 4, 6, 7

3

1

3, 5, 1, 4, 6, 7




2

3, 1, 5, 4, 6, 7




3

3, 1, 4, 5, 6, 7

4

1

3, 1, 4, 5, 6, 7




2

3, 1, 4, 5, 6, 7

5

1

1, 3, 4, 5, 6, 7

Этод метод сортировки массива называется «Метод всплывания пузырька» и работает довольно долго, но зато не требует много рабочих ячеек.

метод «Выбор»

Для элементов с 1 до N-1 повторяем следующие действия:

Ищем imax (индекс максимального элемента) среди всех от i до N;

Меняем текущий элемент A[i] с A[imin]


FOR i:=1 to N-1 DO

Begin

Imin:=i

FOR J:=1 to N DO

IF A[J]>A[imin] then imin:=J;

С:=A[Imin]; A[Imin]:=A[i]; A[i]:=C;

end;

Проследим процесс упорядочивания массива в динамике:

I
Исходный массив

Imin

Исходный

Imin
Выходной
Выходной массив

1

3, 5, 6, 7, 1, 4

1

5

1, 5, 6, 7, 3, 4

2

1, 5, 6, 7, 3, 4

2

5

1, 3, 6, 7, 5, 4

3

1, 3, 6, 7, 5, 4

3

6

1, 3, 4, 7, 5, 6

4

1, 3, 4, 7, 5, 6

4

5

1, 3, 4, 5, 7, 6

5

1, 3, 4, 5, 7, 6

5

6

1, 3, 4, 5, 6, 7

6

1, 3, 4, 5, 6, 7

4

-

-

Существуют и другие методы сортировки.


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


Упорядочить массив по убыванию «методом пузырька».

Упорядочить массив по возрастанию после максимального элемента.

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

В массиве все элементы, не равные 0, переписать, сохраняя порядок, в начало массива, нулевые элементы – в конец массива. Новый массив не заводить.



Задачи по массивам



Дан массив А. Найти длину самой длинной последовательности подряд идущих элементов, равных 0.

Занести в массив А первые 6 чисел, начиная с 25, делящихся нацело на 7.



0>