Программирование на языке Паскаль. Часть 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]

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

на 2 и вывести на экран.
Пример:
Введите пять

из них.
Пример:
Введите пять чисел:
4 15

A первыми N натуральными числами, начиная с 1.
3. Заполните массив

на 1.
2. Умножить все элементы массива A на 2.
3. Возвести

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

первый элемент – максимальный }
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 }

нем минимальный элемент и его номер.
Пример:
Исходный

нем два максимальных элемента и их номера.
Пример:

Найти минимальное значение среди всех элементов массива.
3. Найти минимальное

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

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

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

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

a

b

a

b

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

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

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

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;

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

количество положительных элементов.
«4»: Заполнить массив случайными числами в интервале [20,100]

равны 1.
2. Определите, сколько элементов массива A равны заданному значению

и подсчитать сумму положительных элементов.
Идея: используем переменную 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];

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

[-10,10] и подсчитать сумму всех отрицательных элементов.
«4»: Заполнить массив из

Пример:
Исходный массив:
10 10 11 12 12 12 10 11 11 12
Длина последовательности: 3

Вычислить сумму отрицательных элементов массива A.
3. Вычислить сумму всех

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

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

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

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

do

[10..20] и найти элемент, равный X.
Пример:
Исходный массив:

[0..4]и определить, есть ли в нем одинаковые соседние элементы.

элемента, равного X.
2. Определите номер первого элемента, равного X, в

и 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;

[-10..10] и сделать реверс всех элементов, кроме последнего.
Пример:

[-10..10] и сделать реверс отдельно для 1-ой и 2-ой половин

элемент становится на место последнего.
Алгоритм:
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;

[-10..10] и выполнить циклический сдвиг влево без первого элемента.

[-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента.

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

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] уже поставлены

[-10..10] и отсортировать его по убыванию.
Пример:
Исходный массив:

[0..100] и отсортировать первую половину по возрастанию, а вторую –

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

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;

местами с A[1])
из оставшихся найти минимальный элемент и поставить на

i ;
for j:= i+1 to N do
if

N-1

N

нужно N-1 проходов

поиск минимального от A[i] до A[N]

если нужно, переставляем

i+1

i

[0..99] и отсортировать его по убыванию последней цифры.
Пример:

[0..100] и отсортировать первую половину по возрастанию, а вторую –

дальше друг от друга.
N div 2
2 шаг: переставить элементы

1 шаг: выбрать некоторый элемент массива X

3 шаг: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

и справа от него в отсортированном массиве стоит одинаковое число

Разделение:
выбрать средний элемент массива (X=67)


установить L:=1, R:=N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R, поменять местами A[L] и A[R] и перейти к п. 3

R, c, X: integer;
begin
if first < last then begin

ограничение рекурсии

while L <= R do begin
while A[L] < X do L:= L + 1;
while A[R] > X do R:= R - 1;
if L <= R then begin
c:= A[L]; A[L]:= A[R]; A[R]:= c;
L:= L + 1; R:= R - 1;
end;
end;

разделение

обмен

двигаемся дальше

сортируем две части

of integer;


begin
{ заполнить массив }
{ вывести исходный массив

procedure QSort ( first, last: integer);
...

[-50..50] и отсортировать его с помощью алгоритма быстрой сортировки.
«4»: Заполнить

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

средний элемент A[c] и сравнить с X.
Если X = A[c],

:= N; {границы: ищем от A[1] до A[N] }









if

while R >= L do begin
c := (R + L) div 2;




if X < A[c] then R := c - 1;
if X > A[c] then L := c + 1;
end;

номер среднего элемента

if X = A[c] then begin
nX := c;
R := L - 1; { break; }
end;

нашли

выйти из цикла

сдвигаем границы

в нем элемент, равный X (это число вводится с клавиатуры).

символ – отдельный объект;
массив имеет длину N, которая задана при

Что нужно:
обрабатывать последовательность символов как единое целое
строка должна иметь переменную длину

length ( s );
var n: integer;

«а» на буквы «б».
program qq;
var s: string;
i: integer;
begin

readln(s);

writeln(s);

Length(s)

ввод строки

длина строки

вывод строки

буквы «б», как заглавные, так и строчные.
Пример:
Введите

(палиндром читается одинаково в обоих направлениях).
Пример:

значения:
var s, s1, s2: string;
s := 'Вася';
s1 := 'Привет';
s2 :=

'Привет, Вася!'

Подстрока: выделить часть строки в другую строку.

s := '123456789';

s1 := Copy ( s, 3, 6 );
s2 := Copy ( s1, 2, 3 );

'345678'

'456'

с 3-его символа

6 штук

s, 3, 6 );
с 3-его символа
6 штук
строка
меняется!
'123456789'
'129'
s :=

куда вставляем

что вставляем

начиная с 3-его символа

'12ABC3456789'

'12ABQC3456789'

Pos ( 'е', s );
if n > 0 then

s[3]

3

n = 11

Особенности:
функция возвращает номер символа, с которого начинается образец в строке
если слова нет, возвращается 0
поиск с начала (находится первое слово)

var n: integer;

);
Delete ( s, n, 4 );
Insert ( 'Лена', s, n

'Вася Лена Митя'

s := 'Вася Петя Митя';
n := length ( s );
s1 := Copy ( s, 1, 4 );
s2 := Copy ( s, 11, 4 );
s3 := Copy ( s, 6, 4 );
s := s3 + s1 + s2;
n := length ( s );

'Вася Митя'

14

'Вася'

'Митя'

'Петя'

'ПетяВасяМитя'

12

6

к формату «фамилия-инициалы».
Пример:
Введите имя, фамилию и отчество:

Алгоритм:
найти первый пробел и выделить имя
удалить имя с пробелом из основной строки
найти первый пробел и выделить отчество
удалить отчество с пробелом из основной строки
«сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

writeln('Введите имя, отчество и фамилию');
readln(s);
n :=

их пробелом. Вывести инициалы и фамилию.
Пример:
Введите фамилию,

вложенную папку с новой строки
Пример:

собой сумму двух целых чисел, например:
12+35
Вычислить эту сумму:
12+35=47

Алгоритм:
найти знак «+»
выделить

r ); { N = 123 }
{ r =

Из числа в строку:

N := 123;
Str ( N, s ); { '123' }
X := 123.456;
Str ( X, s ); { '1.234560E+002' }
Str ( X:10:3, s ); { ' 123.456' }

var N, r: integer;
X: real;
s: string;

n2, sum: integer;
begin
writeln('Введите выражение (сумму чисел):');
readln(s);
n:= Pos('+',

слагаемые-строки

слагаемые-числа

сумма

слагаемые-строки

слагаемые-числа

Пример:
25-12
Ответ: 13
«4»: Ввести арифметическое выражение: сумму трёх

использовать сложение и вычитание. Вычислить это выражение.
Пример: Пример:

использовать сложение, вычитание и умножение. Вычислить это выражение.
Пример:

команды «Шайба», а затем – N строк, в каждой из

Алгоритм:

for i:=1 to N do begin
{ пропускаем фамилию и имя }
{ читаем год рождения Year и число голов Gol }
if (1988 <= Year) and (Year <=1990) and
(Gol = 0) then { увеличиваем счетчик }
end;

не встретим пробел }
var c: char;
Пропуск имени:
repeat read(c); until c

Ввод года рождения:

read(Year); { из той же введенной строки }

var Year: integer;

Ввод числа голов и переход к следующей строке:

readln(Gol); { читать все до конца строки }

var Gol: integer;

integer;
begin
writeln('Количество футболистов');
readln(N);
count := 0;
for i:=1 to

repeat read(c); until c = ' ';
repeat read(c); until c = ' ';
read(Year);
readln(Gol);

read(c); { прочитать символ }

Вместо read(Year):

s := ''; { пустая строка }
repeat
read(c); { прочитать символ }
s := s + c; { прицепить к году }
until c = ' ';
Val(s, Year, r); { строку – в число }

var fam: string;

var s: string;

array[1..MAX] of string;
...
fam[i] := ''; { пустая строка }
repeat

массив символьных строк

двух голов.
Пример:
Иванов Василий
Семёнов Кузьма
«4»: Вывести фамилию

Информация о футболистах вводится так же, как и для приведенной задачи (сначала N, потом N строк с данными).

которые забили хотя бы один гол. В списке не более

Ц, Щ и О. Вывести на экран все слова из

1

K

в каждой ячейке может быть любая из 4-х букв

4 варианта

4 варианта

4 варианта

4 варианта

Количество вариантов:

к 4-м задачам для слов из K-1 букв.
1
K
1
K
1
K

перебрать все варианты

перебрать

перебрать все варианты

перебрать все варианты

writeln(s);
count := count+1;
end
else begin
s[p]:='Ы';

1

K

p

s

p+1

рекурсивные вызовы

окончание рекурсии

Глобальные переменные:
var s: string;
count, K: integer;

integer;
begin
if p > k then begin

const letters = 'ЫЦЩО';

for i:=1 to length(letters) do begin
s[p] := letters[i];
Rec(p+1);
end;

все буквы

цикл по всем буквам

локальная переменная

длину слов:');
read ( K );
s := '';
for

procedure Rec(p: integer);
...
end;

процедура

s := '';
for i:=1 to K do s := s + ' ';

строка из K пробелов

глобальные переменные

и О. Число K вводится с клавиатуры.
«3»: Вывести на экран

типа).
Матрица – это массив, в котором каждый элемент имеет два

A

строка 2

столбец 3

ячейка A[3,4]

array[1..N,1..M] of integer;
B: array[-3..0,-8..M] of integer;
Q:

Ввод с клавиатуры:

for i:=1 to N do
for j:=1 to M do begin
write('A[',i,',',j,']=');
read ( A[i,j] );
end;

A[1,1]=

25

A[1,2]=

14

A[1,3]=

14

...

A[3,4]=

54

i

j

for j:=1 to M do
for i:=1 to N do begin

M do
A[i,j] := random(25) - 10;
цикл по строкам
цикл

Вывод на экран

for i:=1 to N do begin


writeln;
end;

перейти на новую строку

for j:=1 to M do
write ( A[i,j]:5 );

вывод строки

в той же строке

4 столбцов случайными числами и вывести ее на экран. Найти

program qq;
const N = 3; M = 4;
var A: array[1..N,1..M] of integer;
i, j, S: integer;
begin
{ заполнение матрицы и вывод на экран}
S := 0;



writeln('Сумма элементов матрицы ', S);
end.

for i:=1 to N do
for j:=1 to M do
S := S + A[i,j];

в интервале [-10,10] и вывести ее на экран.
«3»: Удвоить все

матрицы из N строк и N столбцов.
A[1,N]
A[2,2]
A[3,3]
A[N,N]
for i:=1 to N

Задача 2. Вывести на экран вторую диагональ.

A[N,1]

A[N-1,2]

A[2,N-1]

for i:=1 to N do
write ( A[i, ]:5 );

N+1-i

сумма номеров строки и столбца N+1

A[1,1]

диагонали и ниже ее.
строка 1: A[1,1]
строка 2: A[2,1]+A[2,2]
...
строка N: A[N,1]+A[N,2]+...+A[N,N]
S

цикл по всем строкам

for j:= 1 to i do
S := S + A[i,j];

складываем нужные элементы строки i

из N строк и M столбцов переставить 2-ую и 4-ую

2

4

j

A[2,j]

A[4,j]

for j:=1 to M do begin
c := A[2,j];
A[2,j] := A[4,j];
A[4,j] := c;
end;

Задача 5. К третьему столбцу добавить шестой.

for i:=1 to N do
A[i,3] := A[i,3] + A[i,6];

в интервале [10,90] и вывести ее на экран. Заполнить элементы,

«3»: «4»: «5»:

оформления, не содержат управляющих символов (с кодами < 32)
ACSII (1 байт

*.txt, *.log,
*.htm, *.html

могут содержать любые символы кодовой таблицы

*.doc, *.exe,
*.bmp, *.jpg,
*.wav, *.mp3,
*.avi, *.mpg

Текстовые

Двоичные

Папки (каталоги)

файл (сделать его активным, приготовить к работе)

assign(f, 'qq.txt');
reset(f); {для чтения}
rewrite(f);

II этап: работа с файлом

Переменная типа «текстовый файл»: var f: text;

III этап: закрыть файл

close(f);

read ( f, n ); { ввести значение n }

write ( f, n ); { записать значение n }
writeln ( f, n );{c переходом на нов.строку }

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

той позиции, где стоит курсор
после чтения курсор сдвигается на первый

12 5 45 67 56●

конец файла
(end of file, EOF)

12 5 45 67 56●

assign ( f, 'qq.txt' );
reset ( f );

read ( f, x );

reset ( f ); { начать с начала }
readln

12 5 45¤ 36 67¤ 56●

конец строки
(end of line, EOL)

– неизвестно. Записать в файл output.txt их сумму.
Алгоритм:
Открыть файл input.txt

цикл с условием «пока есть данные»

assign(f, 'input.txt');
reset(f);
s := 0;

while not eof(f) do begin
readln(f, x);
s := s + x;
end;

f: text;

eof(f)

логическая функция, возвращает True, если достигнут конец файла

assign(f, 'output.txt');
rewrite(f);
writeln(f, 'Сумма чисел ', s);
close(f);

запись результата в файл output.txt

Найти сумму чётных чисел и записать её в файл output.txt.
«4»:

их – неизвестно, но не более 100. Переставить их в

text;
function ReadArray: integer;
var i: integer;
begin
assign(f,

Глобальные переменные:

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

while (not eof(f)) and (i < 100) do begin
i := i + 1;
readln(f, A[i]);
end;

ReadArray := i;

цикл заканчивается, если достигнут конец файла или прочитали 100 чисел

N, i: integer;
Begin
N := ReadArray;
{

function ReadArray: integer;
...
end;

assign(f, 'output.txt');
rewrite(f);
for i:=1 to N do
writeln(f, A[i]);
close(f);

вывод отсортированного массива в файл

не более 100.
«3»: Отсортировать массив по убыванию и записать

есть слово-паразит «короче». Очистить текст от мусора и записать в

сочетания ", короче," (Pos, Delete).
Записать строку в другой файл.

пока не кончились данные

repeat
i := Pos(', короче,', s);
if i <> 0 then Delete(s, i, 9);
until i = 0;

искать «, короче,»

удалить 9 символов

i: integer;
fIn, fOut: text;
begin

fIn, fOut: text;

файловые переменные

открыть файл для чтения

открыть файл для записи

readln(fIn, s);
writeln(fOut, s);
end;

пока не достигнут конец файла

обработка строки

запись «очищенной» строки

Заменить все слова «короче» на «в общем» и записать результат

сайта (не более 100). Вывести их в алфавитном порядке в

их в переменной N
отсортировать первые N строк массива по алфавиту
вывести

Объявление массива (с запасом):

const MAX = 100;
var s: array[1..MAX] of string;

eof(f) do begin
N:= N + 1;
readln(f, s[N]);
end;
close(f);
var f:Text;

do begin
nMin:= i;
for j:=i+1 to N do

var i, j, nMin: integer;
c: string;

i:=1 to N do
writeln(f, s[i]);
close(f);
var f:Text;
i,

'в'
'Пароход' > 'Паровоз'

string;
c: string; {вспомогательная строка}
...
for i:=1 to N

2) Иванов Федор
«4»: Выполнить задачу на «3» и сократить имя

имена школьников и баллы, полученные ими на экзамене (0-100). В

'marks.txt');
reset(fIn);
assign(fOut, 'best.txt');
rewrite(fOut);
while not eof(fIn) do begin
{ обработка строк

s);
{ обработка строки s }
{ ball:=

r ); { N = 123 }
{ r =

Из числа в строку:

N := 123;
Str ( N, s ); { '123' }
X := 123.456;
Str ( X, s ); { '1.234560E+002' }
Str ( X:10:3, s ); { ' 123.456' }

var N, r: integer;
X: real;
s: string;

}
fam:= Copy(s,1,n-1); { fam:= 'Пупкин'; }
Delete(s, 1, n);

var n, r: integer;
s, fam, name: string;

s:

n

1

n

1

Анисимов Никита 90
«4»: Выполнить задачу на «3» и сократить имя

163, г. Санкт-Петербург
kpolyakov@mail.ru