Алгоритмы и их свойства (стр. 12 )

§8.1. Одномерный массив

Представим оценки участника соревнования в виде одномерного массива B, состоящего из 12 элементов:

Обозначение элемента	B[1]	B[2]	B[3]	B[4]	B[5]	B[6]	B[7]	B[8]	B[9]	B[10]	B[11]	B[12]
Значение элемента	3.4	4.2	5.0	4.7	3.9	5.0	3.4	4.5	4.9	4.6	3.3	4.0
Номер элемента	1	2	3	4	5	6	7	8	9	10	11	12

Отсюда мы видим, что массив – упорядоченная по порядковым номерам совокупность однотипных данных. Для обращения к элементу массива указывается имя массива и в квадратных скобках номер элемента, например: B[10]=4.6, B[3]=5.0

Для резервирования в памяти необходимого количеств ячеек массив необходимо описать. В программе массив можно описать несколькими способами:

1. В разделе описания переменных (VAR):

<имя массива>: array [<ном_перв_элем> . . <ном_посл_элем >] of <тип элементов>;

2. В разделе описания констант (CONST):

<имя массива>: array [<ном_перв>. .<ном_посл>] of <тип элементов>=(значения элементов)

3. В разделе описания типов (TYPE).

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

1. var A: array[1..30] of real;

(элементы массива А имеют тип real, тип индекса ограниченный от 1 до 30).

2. var MAS: array[1..n] of integer;

(целочисленный массив MAS из n элементов, n должно быть задано в разделе const).

3. const mes: array [1..12] of integer=(31,28,31,30,31,30,31,31,30,31,30,31)

(элементы массива mes – целочисленные константы, их значения заданы в скобках).

4. var M1: array[‘A’..’Z’] of integer;

(элементы массива M1 имеют тип integer, тип индекса ограниченный – буквы латинского алфавита).

5. type massiv = array [1..12] of integer;

var m, n,k, l: massiv;

(в разделе type задается новый тип данных с именем massiv – целочисленный массив из 12 элементов, в разделе var описываются 4 массива типа massiv)

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

Ввод элементов массива

Ввод элементов массива можно осуществить 4 способами:

1 способ. С помощью оператора ввода данных с клавиатуры.

Program lin_massiv1;

const n=12;

var i: integer;

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

Begin

for i:=1 to n do

begin

write(‘введите’,i,’элемент’);

readln(a[i]);

end;

End.

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

2 способ. С помощью оператора присваивания.

Program lin_massiv21; uses crt; const n=12; var i: integer; a:array[1..n] of real; Begin clrscr; a[1]:=1; a[2]:=0; a[3]:=-14; a[4]:=8; a[5]:=-4; a[6]:=-41; a[7]:=21; a[8]:=30; a[9]:=5; a[10]:=-10; a[11]:=-11; a[12]:=-12; End.

Элементы с нечетными индексами равны 0, с четными 1. Program lin_massiv22; uses crt; const n=12; var i: integer; a:array[1..n] of real; Begin clrscr; for i:=1 to n do if i mod 2=0 then a[i]:=1 else a[i]:=0; End.

3 способ. C помощью датчика случайных чисел.

Этот способ используется, когда элементы массива не заданы в условии задачи. Элементами массива становятся случайным образом полученные числа из отрезка [a, b]

Program lin_massiv3;

uses crt;

const n=12;

var i, a,b: integer;

x:array[1..n] of real;

Begin

clrscr;

randomize;

write(‘Введите отрезок генерации’); readln(a, b);

for i:=1 to n do

x[i]:=a+random(b–a+1); {формула генерации из отрезка [a, b]}

End.

Значениями функции RANDOM являются целые числа.

Задание: запишите форм знаками после запятой.

4 способ. Ввод данных из файла.

Этот способ будет рассмотрен в §14.

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

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

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

в строчку writeln(‘Дан (получен) массив:’); for i:=1 to n do write(a[i], ‘ ’); writeln;

в столбик writeln(‘Дан (получен) массив:’); for i:=1 to n do writeln(‘a[‘,i,’]= ’,a[i]);

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

1. Суммирование элементов (нахождение произведения)

s:=0; for i:=1 to n do s:=s+a[i];

p:=1; for i:=1 to n do p:=p*a[i];

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

Минимум {min–мин. элемент, k–его индекс} min:=a[1]; k:=1; for i:=2 to n do if a[i]<min then begin min:=a[i]; k:=i; end;

Максимум {max–макс. элемент, k–его индекс} max:=a[1]; k:=1; for i:=2 to n do if a[i]>max then begin max:=a[i]; k:=i; end;

3. Поиск по ключу

Нахождение количества, суммы и произведения элементов, удовлетворяющих некоторому условию, например «элементы массива больше 4».

k:=0; s:=0; p:=1;

for i:=1 to n do

if a[i]>=4 then

begin

k:=k+1;

s:=s+a[i];

p:=p*a[i];

end;

Преобразование массива

Изменение элементов массива, в зависимости от условия. Например, положительные элементы массива возвести в квадрат, все остальные – удвоить.

for i:=1 to n do

if a[i]>0 then a[i]:=sqr(a[i])

else a[i]:=2*a[i];

Упорядочение массива – сортировка по возрастанию или убыванию

1 способ – линейная сортировка

for i:=1 to n do

for j:=1 to n-1 do

if a[j]>a[j+1] then

begin

c:=a[j]; a[j]:=a[j+1];

a[j+1]:=c;

end;

2 способ – метод "пузырька"

Сравниваем по величине первый и второй элементы массива и, если между ними неправильный порядок, меняем их местами. Для этого используем циклический обмен с помощью третьей переменной. Далее поступаем точно также со вторым и третьим элементами и т. д. до конца. В результате продвижения по всему массиву в его конце окажется самый маленький (или большой) элемент массива - "пузырек". Если имела место хотя бы одна перестановка, то повторяем процесс сначала. На предпоследнее место встанет элемент, непосредственно предшествующий самому маленькому (большому). Так поступаем до тех пор, пока не потребуется ни одной перестановки. Запоминание факта перестановки будет обеспечивать переменная W – флажок (0 – не было перестановок, 1 – была хотя бы одна перестановка).

w:=1;

while w=1 do

begin

w:=0;

for i:=1 to n–1 do

if a[i]>a[i+1] then

begin

c:=a[i]; a[i]:=a[i+1];

a[i+1]:=c; w:=1

end;

end;

writeln(‘вывод упорядоченного массива по возрастанию’);

for i:=1 to n do writeln(a[i],’; ‘);

3 способ – метод последовательного выделения максимального элемента.

Находим max – наибольший элемент массива среди элементов, начиная с 1-го, фиксируем его индекс, меняем местами МAX с первым элементом Находим max – наибольший элемент массива среди элементов, начиная с 2-го, фиксируем его индекс, меняем местами со вторым элементом исходного массива. … Находим max – наибольший элемент массива среди элементов, начиная с N–1-го, фиксируем его индекс, меняем местами с (N–1)-м элементом исходного массива.

i – индекс элемента массива, j – с какого элемента начинаем поиск max,

к – индекс максимального элемента

for i:= 1 to n-1 do

begin

max:=a[i]; k:=i;

for j:=i+1 to n do

if max<a[j] then

begin

max:=a[j]; k:=j;

end;

c:=a[i]; a[i]:=a[k]; a[k]:=c;

end;

writeln(‘Вывод упорядоченного массива по убыванию);

for i:=1 to n do writeln(a[i],’; ‘);

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

Program figurist;

uses crt;

label met;

const n=12;

var i, w,k: integer; s, max, min, c: real;

b:array[1..n] of real;

Begin

clrscr;

for i:=1 to n do

begin

write(‘Введите оценку’,i,’судьи’);

readln(b[i]);

end;

writeln(‘Лист оценок участника’);

for i:=1 to n do writeln(i,’судья:’,b[i]:3:1);

s:=0;

for i:=1 to n do s:=s+b[i];

writeln(‘Средний балл участника:’,s/n:5:2);

min:=b[1]; max:=b[1];

for i:=1 to n do

begin

if b[i]<min then min:=b[i];

if b[i]>max then max:=b[i];

end;

writeln(‘Максимальный балл участника: ‘,max:3:1);

writeln(‘Минимальный балл участника: ‘,min:3:1);

k:=0;

for i:=1 to n do if b[i]>4 then k:=k+1;

writeln(‘Количество судей, поставивших выше 4 баллов:‘,k);

w:=1;

while w=1 do

begin

w:=0;

for i:=1 to n-1 do

if b[i]>b[i+1] then

begin

c:=b[i]; b[i]:=b[i+1]; b[i+1]:=c; w:=1;

end;

end;

writeln(‘Оценки участника, упорядоченные по возрастанию’);