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

64. Сортировка
§ 65. Двоичный поиск
§ 66. Символьные строки
§ 67. Матрицы
§

в памяти рядом (в соседних ячейках) и имеющих общее имя.

Надо:

выделять память
записывать данные в нужную ячейку
читать данные из ячейки

array[-5..5] of boolean;
S: array[65..90] of char;
минимальный индекс
максимальный индекс
const N =

размер через константу

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

A['b']

['a'..'z']

массива: 2
ЗНАЧЕНИЕ элемента массива: 10

of integer;
{ обработать A[1] }
{ обработать A[2] }
{ обработать A[3]

}
i:= i + 1;
{ обработать A[i] }
i:= i + 1;
{

i:= i + 1;

Обработка в цикле:

i:= 1;
while i <= N do begin
{ обработать A[i] }
i:= i + 1;
end;

Цикл с переменной:

for i:=1 to N do begin
{ обработать A[i] }
end;

i: integer;
begin
for i:=1 to N do
A[i]:=

экран:
const N = 5;
var A: array[1..N] of integer;

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

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

5
12
34
56
13

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

+ random(81);
write(A[i],' ')
end;
Задача. Заполнить массив (псевдо)случайными целыми числами

сделать что-то с A[i] }
end;
Подсчёт нужных элементов:
Задача. В массиве записаны

count:= 0;
for i:=1 to N do
if (180 < A[i]) and (A[i] < 190) then
count:= count + 1;

if (180 < A[i]) and (A[i] < 190)
then begin

среднее арифметическое

среднее арифметическое его значений.
Пример:
Массив:
1 2 3 4 5
Среднее арифметическое

«B»: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.
Пример:
Массив:
3 2 52 4 60
Ср. арифм. элементов [0,50): 3.000
Ср. арифм. элементов [50,100): 56.000

[1,N] так, чтобы в массив обязательно вошли все числа от

do
i:= i + 1;
write('A[',i,']=',X);
i:= 1;
while

(i <= N)

должно быть первым!

= X then begin
nX:= i;

end;
if

Вариант с досрочным выходом:

break

досрочный выход из цикла

X и найдите все значения, равные X.
Пример:
Массив:
1 2 3

ли в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1

элементы с одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1

> M then
M:= A[i];
write(M);

элементы массива и их номера.
Пример:
Массив:
1 2 3 4 5
Минимальный

«B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5

количество элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3

do
поменять местами A[i] и A[N+1-i]
N div 2
остановиться на

c:= A[i];
A[i]:= A[N+1-i];
A[N+1-i]:= c;
end;

A[i]:= A[i+1]
A[N]:= c;

массива вправо на 1 элемент.
Пример:
Массив:
1 2 3 4 5

«B»: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.
Пример:
Массив:
1 2 3 4 5 6
Результат:
3 2 1 6 5 4

элементы так, чтобы все положительные элементы стояли в начала массива,

условию, в массив B.
for i:= 1 to N do
if

A

B

выбрать чётные элементы

1 to N do
if A[i] mod 2 = 0

B[count]:= A[i];

в другой массив все чётные отрицательные числа.
Пример:
Массив А:
-5 6 7

«B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.
Пример:
Массив А:
12 13 85 96 47
Массив B:
13 47

все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли

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

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

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

1-й проход:

A[j] then begin
{ поменять местами A[j] и A[j+1]

2-й проход:

for j:= N-1 downto do
if A[j+1]< A[j] then begin
{ поменять местами A[j] и A[j+1] }
end;

2

единственное отличие!

downto do
if A[j+1]< A[j] then begin

i

самый «тяжёлый» элемент опускается в конец массива.
«B»: Напишите вариант метода

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

на первое место.
for i:= 1 to N-1 do begin

if i nMin then begin
{ поменять местами

nMin:= i;
for j:=i+1 to N do
if A[j] < A[nMin] then
nMin:= j;

первую половину массива по возрастанию, а вторую – по убыванию.

чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3

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

от друга.

не покидают « свою область»!
Шаг 1: выбрать некоторый элемент массива

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

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

Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

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

{ заполнить массив }
qSort(1, N); { сортировка }
{

Основная программа:

глобальные данные

if nStart >= nEnd then Exit;
L:= nStart; R:= nEnd;

чисел в нем. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2

сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее

«D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

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

1; { начальный диапазон }
while L < R-1 do begin

X. Используя двоичный поиск, определить, есть ли в массиве число,

X. Используя двоичный поиск, определить, сколько чисел, равных X, находится

его. Ввести число X. Используя двоичный поиск, определить, есть ли

{ массив символов }
элементы массива – отдельные объекты
сложно

Хочется:
строка – единый объект
длина строки может меняться во время работы программы

var s: string; { символьная строка }

строка

'a';
Длина строки:
var n: integer;
...
n:= Length(s);
var s: string;

строку');
readln(s);
for i:=1 to Length(s) do

Задача: заменить в строке все буквы 'а' на буквы 'б'.

все буквы «а» на «б» и все буквы «б» на

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

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

s1 + ', ' + s2 + '!';
'Привет, Вася!'
Срез:
s:=

с какого символа

откуда

5

символа
Удаление:
s:= '123456789';
Delete(s, 3, 6); { '129' }
с какого символа
сколько символов

0 then
write('Номер символа ', n)
else
write('Символ не найден.');
что
где

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

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

Алибабаевич Хрюндиков

Хрюндиков

Хрюндиков В.А.

integer;
begin
write('Введите имя, отчество и фамилию: ');
readln(s);

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

знаком '/'. Каждую часть вывести в отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2013/Поход/vasya.jpg
C:
Фото
2013
Поход
vasya.jpg

символов на другую.
Пример:
Введите строку:
(X > 0) and (Y < X)

r); { N = 123 }
s:= '123.456';
Val(s, X, r); {

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

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

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

0 или номер неверного символа

форме символьной строки. Все числа целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60
«B»: Напишите программу,

и двух знаков (допускаются знаки «+», «–», «*» и «/»).

и двух знаков (допускаются знаки «+», «–», «*» и «/»)

строке s все вхождения слова-образца wOld на слово-замену wNew.
пока {

wOld: '12'
wNew: 'A12B'

зацикливание

процедура }
begin
s:= '12.12.12';
replaceAll(s, '12', 'A12B');
writeln(s)
end;

res: string;
p, len: integer;
begin
len:= Length(wOld);
res:= '';

найти слово wOld

не нашли…

добавить то, что перед ним

добавить wNew

взять «хвост»

s:= replaceAll(s, '12', 'A12B');
writeln(s)
end;
function replaceAll(s,

строки.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды

расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя

числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в

«Ш», «Ч» и «О». Нужно вывести на экран все слова,

перебор K-1 символов

задача для слов длины К сведена к задаче для слов длины К-1!

последних K-1 символов }
w[1]:='Ш';
{ перебор последних K-1

TumbaWords(A, w: string; N: integer);
var i: integer;
begin
if N =

уже установлено

когда все символы уже установлены

по всем символам алфавита

алфавит

слово

«Ч» и «О». Нужно вывести на экран все возможные слова,

«B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

«Ч» и «О». Нужно вывести на экран все возможные слова,

S: array[1..N] of string;
begin
for i:= 1 to

for i:= 1 to N-1 do
for j:= N-1 downto i do
if S[j+1] < S[j] then begin
s1:= S[j];
S[j]:= S[j+1];
S[j+1]:= s1;
end;

массив строк

строки с точкой, а затем – слово. Вывести слова в

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

записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой.

одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет

нет знака

нолик

крестик

строка 2, столбец 3

1..M] of integer;
X: array[-3..0, -8..M] of double;

строки

столбцы

строки

столбцы

j:=1 to M do begin
A[i,j]:= random(61) + 20;

Суммирование:

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

интервале [10,99], и находит максимальный и минимальный элементы в матрице

в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
вычислить

числами по спирали и змейкой, как на рисунках:

{ работаем с  A[i,i] }
end;
Побочная диагональ:
for i:= 1 to N

Главная диагональ и под ней:

for i:= 1 to N do
for j:= 1 to i do begin
{ работаем с  A[i,j] }
end;

c:= A[2,j];
A[2,j]:= A[4,j];
A[4,j]:= c
end;

интервале [10,99], а затем записывает нули во все элементы выше

содержащей N строк и M столбцов. Выполните отражение рисунка сверху

«С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

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

на чтение }
Rewrite(Fout); { открыть на запись }
{

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

связать с файлами

хлеб

хлеб

начинка

a, b);
Переход к началу открытого файла:
if Eof(Fin) then { end

Определение конца файла:

1; b:= 2;
Assign(Fout,'output.txt');
Rewrite(Fout);

Close(Fout);
writeln(Fout, a, '+', b, '=', a+b);

begin
{ прочитать число из файла }
{ добавить его

Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.

var x, S: integer;
Fin: Text;
...
Assign(Fin,'input.txt');
Reset(Fin);
S:= 0;
while not Eof(Fin) do begin
readln(Fin, x);
S:= S + x;
end;
Close(Fin);

в файле в столбик, и выводит результат в другой файл.

«B»:

Вывести в другой текстовый файл те же числа, отсортированные в

const MAX = 100;
var A: array[1..MAX] of integer;

Eof(Fin)) and do
begin
N:= N

(N < MAX)

счётчик прочитанных данных

do
writeln(Fout, A[i]);
Close(Fout);

N

по возрастанию последней цифры и записать в другой файл.

«B»: В

строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка

пока { не конец файла }
{ прочитать строку из файла }
{ разобрать строку – выделить возраст }
если возраст < 5 то
{ записать строку в файл Fout }

кличку с первым пробелом }
{ найти в строке пробел }
{

Разбор строки:

var s, sAge: string;
age, p, r: integer;
... { s = 'Мухтар 4 овчарка' }
p:= Pos(' ', s); { 'Мухтар 4 овчарка' }
Delete(s, 1, p); { s = '4 овчарка' }
p:= Pos(' ', s); { '4 овчарка' }
sAge:= Copy(s, 1, p-1); { sAge = '4' }
Val(sAge, age, r); { age = 4 }

readln(Fin, s0);
s:= s0;
{ обработка строки s

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

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

Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО