- •Оглавление
- •Предисловие
- •Целочисленная арифметика
- •Операции с целыми числами
- •Задача «Рубли и копейки»
- •Задача «Часы»
- •Задача «Сумма цифр»
- •Задача «Количество цифр»
- •Задача «Високосный год»
- •Задача «Дом»
- •Наибольший общий делитель (алгоритм Евклида)
- •Задача «Банки»
- •Вещественные числа
- •Вычисление площадей сложных фигур
- •Текстовые файлы
- •Одномерные массивы
- •Описание в программе
- •Ввод и вывод массивов
- •Популярные алгоритмы работы с массивами
- •Сумма элементов массива
- •Количество положительных элементов в массиве
- •Поиск максимального (минимального) элемента массива
- •Сортировка простым обменом (метод “пузырька”)
- •Быстрая сортировка
- •Поиск данных
- •Линейный поиск
- •Бинарный поиск
- •Символьные строки
- •Общие сведения
- •Стандартные функции для работы со строками:
- •Сравнение строк
- •Строка палиндром
- •Выделение слов из строки
- •Множества
- •Множество символов в строке
- •Вывод элементов множества на экран
- •Ввод множества символов
- •Количество различных символов в строке
- •Двухмерные массивы (матрицы)
- •Описание матрицы.
- •Ввод элементов матрицы.
- •Динамическое программирование
- •Цифровая геометрия
- •Основные отношения
- •Взамное расположение точки и прямой
- •Площадь многоугольника
- •Выпуклая оболочка
- •Алгоритмы на графах
- •Алгоритм Флойда
- •Задачи олимпиад
- •Задачи с сайта contest.Samara.Ru
- •Тортики – 1
- •Высокие горы
- •Задача «На болоте» (алгоритм Дейкстры)
- •Задача «На болоте» (алгоритм Флойда)
- •Задачи с сайта acm.Timus.Ru
- •Задача «Ниточка» (номер на сайте 1020)
- •Демократия в опасности (номер на сайте 1025)
- •Один в поле воин (номер на сайте 1197)
- •Задача «Выборы» (номер на сайте 1263)
- •Белый тезис (номер на сайте 1335)
- •Проблема Бен Бецалеля (номер на сайте 1336)
- •Ферма (номер на сайте 1349)
- •Развод семи гномов (номер на сайте 1243)
- •Освещение в Хогвартсе (номер на сайте 1448)
- •Гиперпереход ( номер на сайте 1296)
- •Драгоценные камни (Stone pile 1005).
- •Процедуры и функции.
- •Как написать хорошую программу.
- •Рекурсивные процедуры
- •Перевод десятичного числа в двоичную систему
- •Алгоритм Евклида (наибольший общий делитель)
- •Список рекомендуемой литературы
-
Множества
Предлагаем изучить множества самостоятельно по [1, 2]. При изучении обратите внимание на типы данных в множествах и организации ввода и вывода множеств. Дадим лишь краткие пояснения и рекомендации. Практика программирования показывает, что наиболее полезным видом множеств является множество символов.
Появляется новая для вас операция In (проверка принадлежности элемента множеству), операции объединения множеств (+), пересечения множеств (*) и вычитания (-).
Все остальные пояснения в примерах.
-
Множество символов в строке
Множество символов, принадлежащих строке легко получить по следующей программе:
Var M:set of char;
S:string;
i: integer;
Begin
S:='мама мыла раму';
For i:=1 to Length(S) do M:=M+[s[i]];
{просто символ нельзя добавит к множеству М}
{нужно построить из него множество []}
{и объединить его с множеством М}
End.
-
Вывод элементов множества на экран
Используем символьную переменную ch (Var ch: char;), перебираем все значения символов, начиная с пробела (код #32) и, если символ есть в множестве, выдаем его на экран.
For ch:=#32 to #255 do
If ch in M then write(ch);
-
Ввод множества символов
Множество можно задать в разделе констант.
Например, так
Const M: set of char = ['A'..'Z'];
R: set of char = ['0'..'9'];
Можно получить в результате присваивания, описав в разделе переменных (Var M:set of char;) и присвоив в программе
M:= ['0'..'9', '+', '-'];
При вводе с клавиатуры или из текстового файла, заданное множество лучше вводить в виде строки, из символов которой потом легко получить множество или каждый символ сразу добавлять к множеству.
-
Количество различных символов в строке
Все пояснения в тексте программы.
Var M:set of char;
S : string;
k, i: integer;
ch : char;
Begin
S:='мама мыла раму';
M:=[]; {пустое множество - обязательно}
к:=0; {обязательно обнуляем счетчик}
For i:=1 to Length(S) do
If Not (S[i] In M) then {символа еще нет мн-ве}
Begin
k:=k+1;
{добавляем символ к множеству,}
{чтобы не посчитать его повторно}
M:=M+[s[i]];
End;
Write(k);
Readln;
End.
-
Двухмерные массивы (матрицы)
-
Описание матрицы.
-
Const n=4; m=5;
Type matrix=array[1..n, 1..n] of Real;
{или другой тип}
Var A:matrix;
На рис.2. показан вид описанной матрицы. Обратите внимание, что первый индекс – номер строки, второй - -номер столбца.
-
A11
A12
A13
A14
A15
A21
A22
A23
A24
A25
A31
A32
A33
A34
A35
A41
A42
A43
A44
A45
Рис. 2. Вид матрицы.
-
Ввод элементов матрицы.
Элементы вводятся последовательно по строкам, i – номер строки, j – номер столбца.
For i:=1 to n do
For j:=1 to m do Read(A[i, j]);
Если конкретный размер матрицы может меняться, то следует описать матрицу с запасом (максимальный размер по условию задачи), и вводить размеры матрицы, а затем ее элементы.
Const max=100;
Type matrix=array[1..max, 1..max] of Real;
{ или другой тип}
Var A: matrix;
Begin
Write ('Введите число строк'); Radln (n);
Write ('Введите число столбцов'); Radln (m);
Write ('Введите', m*n, 'элементов матрицы');
For i:=1 to n do
For j:=1 to m do Read (A[i, j]);
-
Вывод элементов матрицы.
Вывод матрицы на экран или в текстовый файл нужно производить в «матричной форме» (по строкам и столбцам), разделяя числа пробелами.
For i:=1 to n do Begin
For j:=1 to m do Write (A[i, j], ' ');{ выдаем строку}
Writeln {переводим курсор на следующую строку}
End;
-
Основные алгоритмы работы с матрицами.
-
Сумма элементов матрицы.
-
Простой алгоритм не требует дополнительных пояснений. Еще раз обращаем внимание на то, что переменная S должна быть обнулена.
S:=0;
For i := 1 to n do
For j := 1 to m do S:= S+ a[i, j];
-
Сумма главной диагонали квадратной матрицы.
Обращаем внимание на то, что элементы главной диагонали имеют равные номера строк (первый индекс) и номера столбцов (второй индекс).
S:=0;
For i:= 1 To n Do S:=S+a[i, i];
-
Сумма побочной диагонали квадратной матрицы.
Посмотрите на индексы побочной диагонали матрицы, первый изменяется по возрастанию, второй по убыванию.
S:=0;
For i:= 1 To n Do S:=S+a[i, n+1-i];
-
Транспонирование матриц.
Строки исходной матрицы становятся столбцами транспонированной. Исходная матрица (а) имеет n строк и m столбцов. Транспонированная матрица (в) имеет m строк и n столбцов.
For i := 1 to n Do
For j := 1 to m Do b[j, i] := a [i, j];
-
Транспонирование матрицы в том же массиве (транспонирование квадратной матрицы).
Здесь без рабочей ячейки не обойтись.
For i := 1 To n-1 Do
For j := i To n Do
Begin
r := a[i, j]; a[i, j] := a[j, i]; a[j, i] := r;
End;
-
Умножение матриц.
Дана матрица A размерами n*m и матрица B – m*k. После умножения получим матрицу C размерами n*k.
Умножение ведем по формуле Cij= ait*btj
For i := 1 To n Do
For j := 1 To k Do begin
S:=0;
For t := 1 To m Do S:= S+A[i, t]*B[t, j];
C[i, j] := S;
end;
-
Работа с фрагментами матриц
Рассмотрим квадратную матрицу. Решим четыре похожие задачи по одной простой схеме.
-
A11
A12
A13
A14
A21
A22
A23
A24
A31
A32
A33
A34
A41
A42
A43
A44
Рис.3. Квадратная матрица
Задачи:
-
сумма элементов на главной диагонали и выше нее.
-
сумма элементов на главной диагонали и ниже нее.
-
сумма элементов на побочной диагонали и выше нее.
-
сумма элементов на побочной диагонали и ниже нее.
Для первой задачи суммирование элементов первой строки нужно начинать с первого элемента до конца строки, второй строки со второго элемента и так до последней строки, где в суммировании участвует только последний элемент
Для второй задачи из первой строки нужно взять только первый элемент, из второй строки два элемента и так до последней строки.
Для третьей задачи суммирование элементов из первой строки нужно взять все элементы, из второй строки на один меньше и так до последней строки.
Для четвертой задачи в первой строке нужно взять только последний элемент, во второй строке два последних и так до последней строки.