Программирование на языке Паскаль Часть II

расположенных в памяти рядом.
Особенности:
все элементы имеют один тип
весь массив имеет

массива: 10

место в памяти
Массив целых чисел:


Размер через константу:
имя
начальный индекс
конечный

тип
элементов

var A: array[1.. ] of integer;

const N=5;

N

var A : array[ 1 .. 5 ] of integer ;

X, Y: array [1..10] of real;
C: array [1..20]

var Q: array [0..9] of real;
C: array [-5..13] of char;

var A: array ['A'..'Z'] of real;
B: array [False..True] of integer;
...
A['C'] := 3.14259*A['B'];
B[False] := B[False] + 1;

array ['z'..'a'] of integer;
...
A['B'] := 15;
A['b']
['a'..'z']
var a: array [0..9]

of integer;
i: integer;
for i:=1 to N do begin

i

8

8

8

8

8

A[1]:=8

A[2]:=8

A[3]:=8

A[4]:=8

A[5]:=8

A[i]:= Z;
Z:= Z + 1;
end;
i
8
9
10
11
12
A[1]:=8
A[2]:=9
A[3]:=10
A[4]:=11
A[5]:=12
Z
8
9
10
11
12
13
const N = 5;
var

A[i]:= Z;
Z:= Z + 1;
end;
for i:=1 to N do

Z = i + 7

a: array[1..N] of integer;
i: integer;
for i:=1 to N

a[1] =
a[2] =
a[3] =
a[4] =
a[5] =

5
12
34
56
13

for i:=1 to N do a[i]:=a[i]+1;

writeln('Массив A:');
for i:=1 to N do write(a[i]:4);

Массив A:
6 13 35 57 14

элемент массива

первый элемент – максимальный }
for i:=2 to N do

}
iMax := 1;
for i:=2 to N do {

Дополнение: как найти номер максимального элемента?

По номеру элемента iMax всегда можно найти его значение a[iMax]. Поэтому везде меняем max на a[iMax] и убираем переменную max.

a[iMax]

i, iMax: integer;
begin
{ здесь нужно ввести массив с

iMax := 1; {считаем, что первый – максимальный}
for i:=2 to N do { проверяем все остальные}
if a[i] > a[iMax] then { новый максимальный}
iMax := i; { запомнить i }

выбор:
жеребьевка на соревнованиях
выигравшие номера в лотерее
Как получить случайность?

(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в

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

не одного числа
равномерное распределение одно, компьютерные датчики случайных чисел дают

a

b

a

b

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

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

var x: integer;
...
x := random ( 100 );

var x: integer;
...
x := random ( N );

x := a + random ( N );

[0,N-1]

[a,a+N-1]

b = a + N - 1

N = b – a + 1

x := a + random ( b-a+1 );

of integer;
i: integer;
begin
writeln('Исходный массив:');
for i:=1 to

случайные числа в интервале [50,150)

подсчитать количество нулевых элементов.
Идея: используем переменную-счётчик.
Решение:
записать в счётчик ноль
просмотреть все

+ 1


пока ни одного не нашли
начать с 1-ого
перейти к следующему
нашли

integer;
i, count: integer;
begin
{ здесь надо заполнить массив

for i:=1 to N do
if A[i] = 0 then count:= count + 1;

перебираем все элементы массива

и подсчитать сумму положительных элементов.
Идея: используем переменную S для накопления

S:=0

S:= A[1]

S:= A[1]+A[2]

S:= A[1]+A[2]+A[3]

S:= A[1]+A[2]+…+A[N]

S:= S+A[i]

i + 1


пока ни одного не нашли
начать с 1-ого
перейти к

нашли еще 1

of integer;
i, S: integer;
begin
{ здесь надо заполнить

for i:=1 to N do
if A[i] > 0 then S:= S + A[i];

перебираем все элементы массива

или установить, что его нет.
Пример: если в классе ученик

к следующему
‘Не нашли’
‘Есть!’

i, X: integer;
begin
{ здесь надо заполнить массив }

(i<=N) and (A[i]<>X)

do

и A[N], A[2] и A[N-1], …
Псевдокод:
for i:=1 to N do

сумма индексов N+1

N div 2

do

содержимое двух ячеек памяти.
4
6
?
4
6
4
x
y
c
c := x;
x := y;
y := c;
x

3

2

1

i, c: integer;
begin
{ заполнить массив }
{ вывести исходный

for i:=1 to N div 2 do begin
c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c;
end;

элемент становится на место последнего.
Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];
Цикл:
for i:=1 to N-1

почему не N?

i, c: integer;
begin
{ заполнить массив }
{ вывести исходный

c := A[1];
for i:=1 to N-1 do A[i]:=A[i+1];
A[N] := c;

условию (например, отрицательные), и скопировать их в другой массив.
Примитивное

const N = 5;
var i: integer;
A, B: array[1..N]
of integer;
begin
{ здесь заполнить массив A }
for i:=1 to N do
if (A[i] < 0) then
B[i]:= A[i];
...
end.

A

B

ставится на место B[count].
count:=0;
for i:=1 to N do
if (A[i]

A

B

count

write(B[i], ' ');
Правильное решение:
writeln('Выбранные элементы:');
for i:=1 to

count

возрастанию, убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы

сложность O(N2)

дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

…
A[1] и A[2]
A[j] и A[j+1]
2-ой проход
for j:=N-1 downto

2

for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
end;

1

i-ый проход

for j:=N-1 downto i do
...

i

i, j, c: integer;
begin
{ заполнить массив }
{ вывести

for i:=1 to N-1 do begin
for j:=N-1 downto i do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
end;
end;

i

элементы выше A[i] уже поставлены

не было обменов, массив уже отсортирован и остальные проходы не

repeat
flag := False; { сбросить флаг }
for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
flag := True; { поднять флаг }
end;
until not flag; { выход при flag=False }

flag := False;

flag := True;

not flag;

var flag: boolean;

1;
flag := False; { сбросить флаг }
for j:=N-1

i := 0;

i

i := i + 1;