Запись в языке C++ намного короче и яснее, мы в дальнейшем будем использовать
только ее.
Примеры программ:
Лекция 5.
Вычисление функций на последовательностях.
Индуктивные функции
Вычисление функций на последовательностях. Примеры: вычисление
суммы, произведения и максимума числовой последовательности.
Общая схема вычисления значения функции, инициализация значения
для пустой последовательности: сумма элементов пустой последовательности
равна 0, произведение равно 1, максимум — значению -∞; общее во всех случаях
— соответствующий элемент является левой единицей (левым нейтральным элементом)
для бинарных операций +, *, max.
Понятие индуктивной функции на последовательностях:
определение, наиболее важные примеры
(сумма, максимум, значение многочлена в точке, коэффициенты которого заданы
по убыванию степеней). Схема вычисления индуктивной функции (в случае многочлена это
схема Горнера).
Примеры неиндуктивных функций.
Понятие индуктивного расширения и вычисление
значения неиндуктивной функции с помощью построения ее индуктивного расширения.
Примеры: вычисление среднего африфметического (геометрического, гармонического)
элементов числовой последовательности, вычисление значения многочлена в точке,
когда коэффициенты многочлена заданы по возрастанию степеней; вычисление значения производной
многочлена (или k-й производной), коэффициенты которого заданы по убыванию степеней —
во всех этих случаях для вычисления требуемых значений строятся индуктивные расширения
перечисленных неиндуктивных функций.
Автоматическое тестирование программ, вычисляющих
функции на последовательностях
Для автоматического тестирования программа должна быть оформлена
следующим образом.
-
Исходные данные читаются из файла "input.txt" (он содержит
элементы последовательности, а также, возможно, некоторые
дополнительные значения; например, в задаче вычисления значения
многочлена p(x) в точке x=t файл содержит сначала значение
t, а затем последовательность коэффициентов многочлена).
-
Результат записывается в файл "output.txt".
-
Результат должен вычисляться в функции, которая получает на вход
указатель на открытый файл. Эта функция должна прочитать до конца
последовательность (перед последовательностью могут быть также дополнительные
аргументы) и в результате вычислить требуемое значение
(или несколько значений). При этом последовательность
должна просматриваться за один проход. Также запрещено использовать
массивы, длина которых зависит от длины последовательности (короткие
массивы фиксированной длины использовать можно).
-
Основная фукции main всего лишь открывает входной файл и вызывает
вспомогательную функцию, решающую требуемую задачу. После завершения
вспомогательной функции функция main закрывает входной файл,
затем открывает выходной файл и записывает результат, возвращенный
вспомогательной функцией, в выходной файл. После этого выходной файл
закрывается.
-
В случае успешного завершения функция main возвращает
значение 0. При неуспехе (не удалось открыть входной
файл на чтение, некорректное содержимое входного файла,
не удалось открыть выходной файл на запись и т.п.) программа
должна вернуть операционной системе значение -1 (с помощью либо
оператора
return (-1);
в функции main, либо вызова
exit(-1);
в любой точке программы).
Для примера рассмотрим задачу вычисления среднего арифметического
значения последовательности вещественных чисел. Начало программы выглядит
следующим образом: сначала подключаются стандартные заголовочные файлы
stdio.h и stdlib.h (в последнем описан прототип функции exit); потом
описывется прототип функции meanAriphm, которая получает на входе открытый
файл и возвращает среднее арифметическое значение записанной в нем
последовательности; и затем реализуется функция main.
#include <stdio.h>
#include <stdlib.h>
double meanAriphm(FILE* f);
int main() {
FILE* in = fopen("input.txt", "r");
if (in == NULL) {
perror("Could not open input file");
return (-1);
}
double m = meanAriphm(in);
fclose(in);
FILE* out = fopen("output.txt", "w");
if (in == NULL) {
perror("Could not open output file");
return (-1);
}
fprintf(out, "%lf\n", m);
fclose(out);
return 0;
}
Прототип функции, подсчитывающей среднее арифметическое
последовательности, задается следующим образом:
double meanAriphm(FILE* f);
Это означает, что функция читает последовательность из уже открытого файла,
доступ к которому осуществляется через переменную f типа указатель на FILE.
Файл заранее
открывается в основной функции main:
FILE* in = fopen("input.txt", "r");
Если файл открыть не удается, то fopen возвращает нулевое значение.
Для печати причины ошибки удобно использовать функцию perror:
if (in == NULL) {
perror("Could not open input file");
return (-1);
}
Функция perror печатает сообщение пользователя (в данном случае
"Could not open input file" — не могу открыть входной файл)
плюс системнове сообщение о причине ошибке (например,
"No such file or directory" — нет такого файла или директории);
т.е. когда файл не существует, будет напечатано
Could not open input file: No such file or directory
Затем программа завершается с кодом -1 путем исполнения в функции main оператора
return (-1);
Функция main почти одинакова во всех задачах на последовательности.
Специфика каждой задачи сосредоточена в функции, читающей
последовательность из файла и вычисляющей требуемое
значение. Для примера рассмотрим реализацию этой функции
в задаче вычисления среднего арифметического.
double meanAriphm(FILE* f) {
int n = 0;
double sum = 0.;
double a;
while (fscanf(f, "%lf", &a) == 1) {
sum += a;
++n;
}
if (n == 0) {
fprintf(stderr, "Incorrect file format.\n");
exit(-1);
}
return sum / (double) n;
}
Идея реализации состоит в том, что по мере чтения последовательности
мы подсчитываем длину прочитанного куска
в переменной n, а также сумму прочитанных элементов в переменной
sum. По окончании чтения мы вычислим среднее арифметическое,
разделив sum на n.
Переменные n и sum при описании инициализируются
нулевыми значениями:
int n = 0;
double sum = 0.;
Мы описываем также переменную a, в которую будем считывать
текущий элемент последовательности:
double a;
Затем в цикле один за другим читаются элементы последовательности.
Цикл завершается, когда очередная попытка чтения заканчивается неудачей.
Чтение элемента осуществляется функцией fscanf, вызываемой прямо
в заголовке цикла while. Она возвращает количество
удачно прочитанных элементов. В нашем случае, поскольку мы пытаемся
прочесть лишь один элемент, оно должно быть равно 1 в случае успеха.
Если возвращенное значение меньше 1 (оно может быть 0 или -1 при ошибке),
то это означает, что прочесть очередное значение не удалось,
и цикл завершается:
while (fscanf(f, "%lf", &a) == 1) {
sum += a;
++n;
}
В теле цикла мы увеличиваем значение переменной sum на прочитанный
элемент a, а также увеличиваем счетчик числа элементов n.
По завершении цикла мы проверяем вычисленную длину n
последовательности. Если она равна нулю (последовательность пуста),
то среднее арифметическое определить невозможно, т.е. исходный файл
содержит некорректные данные. В этом случае программа завершается
с кодом -1 путем вызова функции exit(-1).
Перед завершением программы выводится сообщение об ошибке
"Incorrect file format.\n"
(неправильный формат файла)
с помощью
функции fprintf. Мы не используем функцию printf, потому что
сообщения об ошибках положено выводить в поток stderr, а не в
выходной поток stdout.
if (n == 0) {
fprintf(stderr, "Incorrect file format.\n");
exit(-1);
}
Если значение n отлично от нуля, то функция meanAriphm
возвращает среднее арифметическое, вычисленное как частное значений
sum и n (целочисленное значение n предварительно
приводится к типу double):
return sum / (double) n;
Примеры программ
на вычисление функций на числовых последовательностях,
предназначенных для автоматического тестирования (исходная последовательность
читается из файла "input.txt", результат записывается в файл "output.txt"):
-
task1.cpp
вычисление среднего арифметического
(условие);
-
task2.cpp
вычисление среднего геометрического
(условие);
-
task3.cpp
вычисление среднего гармонического
(условие);
-
task4.cpp
вычисление количества чисел, больших предыдущего
(условие);
-
task5.cpp
поиск числа в последовательности
(условие);
-
task8.cpp
проверка монотонности последовательности
(условие);
-
task9.cpp
определить, удовлетворяет ли последовательность
данному трехчленному рекуррентному соотношению
(условие);
-
task28.cpp
определить максимальную сумму подряд идущих элементов в последовательности
(условие);
-
task29.cpp
найти значение многочлена и его производной в заданной
точке, коэффициенты многочлена заданы по возрастанию степеней
(условие).
-
task30.cpp
найти значение многочлена и его производной в заданной
точке, коэффициенты многочлена заданы по убыванию степеней
(условие).
Список задач по теме "Последовательности"
(старый список)
Лекция 6.
Задачи на работу с массивами. Автоматический тестер
Рассматриваются различные задачи на работу с массивами:
список задач.
Во всех них решение должно быть оформлено в виде функции,
на вход которой подается указатель на начало массива
и его длина, а также дополнительные данные, зависящие от задачи.
Например, прототип функции циклического сдвига целочисленного массива
вправо на k позиций выглядит так:
void shiftk(int *a, int n, int k);
Здесь a — указатель на начало массива,
n — число его элементов, k —
величина сдвига.
При реализации функции запрещено захватывать и использовать
дополнительные массивы (нельзя пользоваться оператором new
или функцией malloc).
Функция main должна прочитать исходные данные
из файла "input.txt", захватить
в динамической памяти массив требуемого размера и вызвать
функцию, решающую нужную задачу. Функции передается
указатель на начало массива, его длина и, если необходимо
по условию задачи, дополнительные параметры.
После вызова функции, решающей задачу, и окончания ее работы
функция main должна записать результат в файл "output.txt".
Если исходные данные некорректны, файл отсутствует или не
открывается на чтение, то функция main должна вернуть системе
значение -1, используя оператор return
return -1;
или функцию exit
exit(-1);
(Значение -1 является признаком ошибочного завершения задания.)
При успешном завершении main должна вернуть 0.
Чтение исходного массива из файла
Исходный массив в файле "input.txt" может быть задан двумя способами.
-
Файл содержит сначала длину массива (целое число),
затем последовательность его элементов (их число должно быть
не меньшим, чем указанная длина).
В этом варианте программа
сначала читает длину массива, затем создает его в динамической памяти
и в цикле for считывает все его элементы:
FILE* in = fopen("input.txt", "r"); // Открыть файл на чтение
if (in == NULL) { // Если ошибка
perror("Cannot open input file"); // то напечатать сообщение
return -1; // завершить работу
}
int n; // Длина массива
if (fscanf(in, "%d", &n) < 1) { // Прочесть длину массива
perror("Illegal format of input file"); // Ошибка => сообщение,
fclose(in); // закрыть файл,
return -1; // завершить работу
}
if (n <= 0) { // Если n некорректно
fprintf(stderr, "Illegal length of array"); // сообщение
fclose(in); // закрыть файл
return -1; // завершить работу
}
int *a = new int[n]; // Создать в динамической памяти массив размера n
for (int i = 0; i < n; ++i) {
if (fscanf(in, "%d", &(a[i])) < 1) { // Прочесть эл-т массива
fprintf(stderr, "Illegal format of file"); // Ошибка=>сообщ.
fclose(in); // закрыть файл
return -1; // завершить работу
}
}
fclose(in); // Закрыть входной файл
// Данные успешно введены
-
Файл содержит только последовательность элементов массива
(не содержит в начале его длину).
Поскольку в этом случае длина массива заранее неизвестна,
данные приходится читать данные в 2 прохода. На первом проходе мы
подсчитываем число элементов массива. Затем мы создаем массив
подсчитанной длины в динамической памяти и перематываем файл на
начало с помощью функции rewind. На втором проходе мы
считываем элементы массива:
FILE* in = fopen("input.txt", "r"); // Открыть файл на чтение
if (in == NULL) { // Если ошибка
perror("Cannot open input file"); // то напечатать сообщение
return -1; // завершить работу
}
int n = 0; // Длина массива
int x; // Переменная для считывания очередного элемента
// Первый проход: подсчет длины массива
while (fscanf(in, "%d", &x) == 1) { // Прочесть очередной эл-т массива
// Ошибка или конец файла => завершение цикла
++n; // Увеличить число прочитанных элементов
}
if (n <= 0) { // Если n некорректно
fprintf(stderr, "Illegal length of array"); // напечатать сообщение
fclose(in); // закрыть файл
return -1; // завершить работу
}
int *a = new int[n]; // Создать в динам. памяти массив размера n
rewind(in); // Перемотать файл на начало
// Второй проход: считывание элементов массива
for (int i = 0; i < n; ++i) {
if (fscanf(in, "%d", &(a[i])) < 1) { // Прочесть эл-т массива
fprintf(stderr, "Illegal format of file"); // Ошибка=>сообщ.
fclose(in); // закрыть файл
return -1; // завершить работу
}
}
fclose(in); // Закрыть входной файл
// Данные успешно введены
Затем функция main вызывает целевую функцию, решающую
нашу задачу. Например, в задаче циклического сдвига массива на
k позиций вправо (прототип этой функции уже был нами описан)
выполняется строка
shiftk(a, n, k); // Вызвать функцию, решающую требуемую задачу
(Заметим, что в данном конкретном случае размер сдвига k
также задается в исходном файле, в первом варианте это второе
значение в файле, во втором — первое;
с учетом этого фрагмент ввода данных,
указанный выше, должен быть модифицирован —
добавлено чтение k.)
В зависимости от конкретной задачи результатом функции может быть
одно число, несколько чисел или, чаще всего, модифицированный массив
(возможен также вариант, когда длина массива может уменьшиться —
тогда результатом является измененная длина массива и последовательность
его элементов).
В любом случае результат надо записать в выходной файл "output.txt".
Рассмотрим последний вариант, когда работа функции состоит в
изменении содержимого массива без изменения его длины.
Запись результатов в выходной файл
Мы открываем выходной файл "output.txt" и записываем в него последовательность
элементов массива, помещая в каждую строку выходного файла не больше 5-ти
элементов. Внутри строк числа разделяются пробелами:
FILE* out = fopen("output.txt", "w"); // Открыть файл на запись
if (out == NULL) { // Если ошибка
perror("Cannot open output file"); // то напечатать сообщение
return -1; // завершить работу
}
for (int i = 0; i < n; ++i) {
// Запишем сначала разделитель
if (i > 0) {
char delimiter = ' '; // Разделитель - пробел
if (i % 5 == 0) // Если в строке ровно 5 эл-тов,
delimiter = '\n'; // то разделитель - перевод строки
fprintf(out, "%c", delimiter); // Запись разделителя
}
// Запишем очередной элемент массива
if (fprintf(out, "%d", a[i]) < 1) { // Записать эл-т массива
perror("Write error"); // Ошибка => сообщение,
fclose(out); // закрыть файл
return -1; // завершить работу
}
}
fprintf(out, "\n"); // Завершим запись переводом строки
fclose(out); // Закрыть выходной файл
// Результаты успешно записаны в файл
Реализация целевой функции
Требуется реализовать функцию, решающую требуемую задачу.
Функции передается указатель на начальный элемент массива
и его длина, а также, возможно, дополнительные данные,
зависящие от условия конкретной задачи. Результатом работы функции
является либо изменение массива, либо какое-либо значение,
вычисленное в результате обработки массива (например, среднее
арифметическое его элементов, индекс искомого элемента и т.п.).
Напомним, что массив создается и его элементы вводятся из файла "input.txt"
в функции main, она же записывает данные в выходной файл после
вызова целевой функции. Рассмотрим несколько конкретных примеров.
-
Циклически сдвинуть элементы целочисленного массива
вправо на одну позицию
Прототип функции:
void shift(int* a, int n);
Реализация (файл "shift.cpp"):
void shift(int *a, int n) {
int j = n-1;
double x = a[j];
while (j > 0) {
a[j] = a[j-1];
--j;
}
a[0] = x;
}
(Начинаем с последнего элемента массива с индексом j = n-1,
запоминаем его значение в переменной x,
затем последовательно копируем предыдущий к j-му элемент в
j-й элемент массива и j уменьшаем на 1. В конце начальному
элементу массива присваиваем сохраненное в x значение
последнего элемента.)
-
Циклически сдвинуть элементы целочисленного массива
вправо на k позиций
Отметим, что в этой задаче k может быть и отрицательным,
в этом случае выполняется сдвиг влево.
Прототип функции:
void shiftk(int* a, int n, int k);
Задача намного интереснее предыдущей (предыдущая
является ее частным случаем при k = 1). Для нее возможны
2 решения, оба заслуживают внимания. Рассмотрим сначала более
простой вариант, основанный на инвертировании массива
(т.е. изменении порядка его элементов на обратный).
Реализация циклического cдвига на k позиций
с помощью инвертирования отрезков массива
Мы используем вспомогательную функцию
void invert(int* a, int n);
которая меняет порядок элементов массива на противоположный
(последний элемент меняется местами с первым, предпоследний со вторым
и т.д). Ее реализация:
void invert(int* a, int n) {
int i = 0;
int j = n-1;
while (i < j) {
int tmp = a[i];
a[i] = a[j]; a[j] = tmp;
++i; --j;
}
}
Для циклического сдвига элементов массива на k позиций
вправо достаточно сначала инвертировать начальный отрезок
массива длины n-k, затем конечный отрезок длины k и
после этого инвертировать весь массив. Ниже приведен
пример для массива длины n=10, содержащего числа от 1 до 10,
и величины сдвига k=3.
-
Исходный массив:
-
1, 2, 3, 4, 5, 6, 7,
8, 9, 10.
-
Сначала инвертируем начало длины 7:
-
7, 6, 5, 4, 3, 2, 1,
8, 9, 10.
-
Затем инвертируем конец длины 3:
-
7, 6, 5, 4, 3, 2, 1,
10, 9, 8.
-
На третьем шаге инвертируем весь массив:
-
8, 9, 10,
1, 2, 3, 4, 5, 6, 7.
Мы получили циклический сдвиг элементов на 3 позиции вправо.
Итак, запишем на C реализацию функции циклического сдвига
элементов массива на k позиций вправо
с помощью вспомогательной функции инвертирования массива:
void shiftk(int *a, int n, int k) {
if (n <= 1) // Вырожденный случай
return;
// Пользуясь периодичностью, приведем k
// к интервалу 0 <= k < n
k %= n;
if (k < 0) // Сдвиг влево на k эквивалентен
k += n; // сдвигу вправо на n-k
invert(a, n-k); // Инвертируем начало массива длины n-k
invert(a+n-k, k); // Инвертируем конец массива длины k
invert(a, n); // Инвертируем весь массив
}
Полный текст программы содержится в файле "shiftk_inv.cpp".
Реализация циклического cдвига на k позиций
с помощью разбиения на орбиты
Рассмотренный выше вариант реализации циклического сдвига
для массива длины n требует около 3*n операций копирования
элементов. (В функции инвертирования для обмена двух элементов требуется
3 копирования, всего копирование производится n/2 раз; массив
в целом инвертируется дважды, в первый раз инвертирование производится для
двух кусков суммарной длины n, получаем
3*n/2 + 3*n/2 = 3n.)
Существует, однако, способ примерно в 3 раза убыстрить алгоритм, выполнив немногим
более n копирований. Он основан на разбиении перестановки на независимые
циклы. Каждый цикл содержит орбиту любого его элемента. В случае циклического сдвига
на k позиций все эти орбиты содержат одинаковое число элементов в силу
симметрии задачи. Например, пусть n=12 и k=8 (сдвиг на 8 позиции вправо).
Подстановка индексов элементов
0 1 2 3 4 5 6 7 8 9 10 11
8 9 10 11 0 1 2 3 4 5 6 7
(нулевой элемент переходит в восьмой, первый в девятый и т.д.)
разбивается в произведение четырех независимых циклов длины 3:
(0 8 4) (1 9 5) (2 10 6) (3 11 7)
Каждая из скобок содержит орбиту первого записанного в ней элемента.
Внутри каждой орбиты элементы переставляются циклически. Используя
одну из важнейших теорем алгебры и теории чисел о том, что наибольший
общий делитель d чисел k и n выражается в виде линейной
комбинации чисел k и n с целыми коэффициентами u и v
d = u k + v n,
нетрудно убедиться, что наименьший положительный элемент в орбите нуля
равен наибольшему общему делителю чисел k и n, в данном примере
это 4. Отсюда следует, что всего орбит (циклов в разложении подстановки
на независимые циклы) будет d, где d — наибольший общий делитель
n и k.
Отсюда получается другой алгоритм реализации циклического сдвига на k
элементов массива длины n.
Сначала вычисляем наибольший общий делитель d = gcd(n, k),
эту функцию мы уже рассматривали ранее. Затем во внешнем цикле перебираем орбиты элементов
0, 1, 2, ..., d-1, всего внешний цикл выполняется d раз. В теле внешнего цикла
мы осуществляем сдвиг на одну позицию внутри каждой орбиты — это вложенный цикл,
очень похожий на тот, которым мы использовали в программе циклического сдвига на одну позицию:
запоминаем последний элемент во вспомогательной переменной x, затем последнему элементу
орбиты присваиваем значение предпоследнего, предпоследнему — предыдущего к нем
элемента и т.д., заканчивая вторым элементом; наконец, первому элементу присваиваем значение
последнего элемента, ранее запомненное в x.
void shiftk(int *a, int n, int k) {
k %= n;
if (k == 0)
return;
if (k < 0) // левый сдвиг на k позиций
k += n; // равен правому сдвигу на n-k
int i = 0; // индекс первого элемента текущей орбиты
int d = gcd(n, k); // число орбит = НОД(n, k)
while (i < d) { // цикл для каждой орбиты
// i - первый элемент орбиты
int j = i-k; // j - последний элемент орбиты
if (j < 0)
j += n;
int x = a[j]; // запомним значение последнего элемента
while (j != i) { // цикл для каждого элемента j орбиты
int l = j-k; // l - предыдущий элемент к j
if (l < 0)
l += n;
a[j] = a[l]; // копируем предыдущий элемент в текущий
j = l; // переходим к предыдущему элементу
}
a[i] = x; // копируем значение последнего элемента в первый
++i;
}
}
int gcd(int x, int y) {
while (y != 0) {
int r = x % y;
x = y; y = r;
}
return x;
}
В этой функции для каждой орбиты длины m выполняется
m+1 копирование, т.е. всего число операций копирования
равняется длине массива плюс число орбит:
num = n + gcd(n, k)
В частности, если числа n и k взаимно просты, то
число копирований равно n+1, что существенно быстрее, чем в
первом варианте программы. Это оправдывает несколько большую
сложность второго варианта.
Полный текст программы содержится в файле
"shiftk.cpp".
Лекция 7.
Задачи на работу с массивами. Часть 2
Рассмотрим еще несколько важных задач на работу с массивами.
1. Сортировка
Дан массив a длины n. Требуется упорядочить его
элементы по возрастанию (нестрогому):
a[0] ≤ a[1] ≤ ... ≤ a[n-1]
Задача сортировки очень популярна в программировании.
К ней сводятся очень многие другие задачи (например,
построение выпуклой оболочки множества точек на
плоскости). Поиск элемента в упорядоченном массиве длины n
осуществляется очень быстро, за время порядка O(log2 n).
Логарифм — очень медленно растущая функция, например, логарифм по основанию 2
от миллиона чуть меньше 20 (приближенно 19.932). При применении
последовательного поиска нам придется выполнить порядка 1000000 операций,
если элемент не содержится в массиве, и порядка 500000, если содержится —
сравните с 20 операциями при бинарном поиске! Поэтому
элементы массива, в котором часто осуществляется поиск, следует хранить
упорядоченными по возрастанию, что во многих случаях требует
сортировки элементов.
Нетрудно показать, что отсортировать элементы произвольного массива длины n
в общем случае невозможно, использовав менее чем log2(n!)
операций сравнения (это будет доказано в лекциях по программированию
на 2 курсе). При n → ∞ эта функция эквивалентна функции
log2(n!) ~
n log2 n
(это легко доказать, использовав формулу Стирлинга для представления n!).
Поэтому любой алгоритм сортировки в общем случае (когда нет никаких ограничений
на сортируемые элементы) не может работать быстрее, чем за время
n log2 n. Алгоритмы, которые работают за время
O(n log2 n),
называются оптимальными. Есть несколько
подобных алгоритмов: сортировка кучей HeapSort, сортировка слиянием MergeSort,
Radix-сортировка; наконец, популярный алгоритм "Быстрая сортировка" QuickSort
в среднем работает за время O(n log2 n), хотя
с очень небольшой вероятность существует вход, на котором "Быстрая сортировка"
работает за время всего лишь O(n2).
Оптимальные алгоритмы сортировки являются одной из тем лекций по программированию
на 2-м курсе. Мы же пока ограничимся двумя простейшими алгоритмами, работающими
очень медленно, за время O(n2).
Предупреждение! Подобные алгоритмы
на практике можно применять только для совсем маленьких массивов, но для
сдачи зачета по программированию на 1-м курсе даже они сгодятся (хотя, скорее,
алгоритм пузырьковой сортировки является примером того, как не надо писать
программы).
Пузырьковая сортировка
Мы просматривает массив слева направо от начального до предпоследнего
элемента и сравниваем два соседних элемента: текущий и следующий за ним.
Если они образуют инверсию, т.е. текущий элемент строго больше следующего,
то мы меняем их местами. Подобные просмотры массива повторяются до тех пор,
пока на очередном шаге мы не обнаружим ни одной инверсии.
Название "Пузырьковая сортировка" возникло из-за того, что в процессе
выполнения алгоритма "легкие" элементы (т.е. элементы с меньшими значениями)
как бы всплывают вверх (т.е. к началу массива) подобно пузырькам воздуха,
а тяжелые элементы опускаются вниз (к концу массива). Вот реализация
пузырьковой сортировки для массива вещественных чисел.
void bubbleSort(double *a, int n) {
bool inv = true; // были_инверсии = да
while (inv) { // Цикл пока были_инверсии
inv = false; // были_инверсии = нет
for (int i = 0; i < n-1; ++i) {// просматриваем эл-ты массива
// до предпоследнего
if (a[i] > a[i+1]) { // если соседние образуют инверсию
inv = true; // то были_инверсии = да
double tmp = a[i]; // меняем местами соседние эл-ты
a[i] = a[i+1]; a[i+1] = tmp;
}
}
}
}
Алгоритм можно чуть убыстрить, если заметить, что после первого прохода
максимальный элемент массива становится на последнее место, после второго
прохода второй по величине элемент — на предпоследнее место и т.д.
Поэтому после k проходов последние k
элементов уже стоят на своих местах и их можно не рассматривать.
void bubbleSort(double *a, int n) {
bool inv = true; // были_инверсии = да
int k = 0; // число выполненных проходов
while (inv && k < n-1) { // Цикл пока были инверсии и k < n-1
inv = false; // были_инверсии = нет
for (int i = 0; i < n-1-k; ++i) {// просматриваем эл-ты массива
// до индекса n-1-k
if (a[i] > a[i+1]) { // если соседние эл-ты образуют инверсию
inv = true; // то были_инверсии = да
double tmp = a[i]; // меняем местами соседние эл-ты
a[i] = a[i+1]; a[i+1] = tmp;
}
}
++k; // увеличиваем число выполненных проходов
}
}
Этот вариант алгоритма работает примерно вдвое быстрее предыдущего,
но всё равно очень медленно.
Пузырьковую сортировку можно значительно убыстрить, рассматривая поначалу
не пары соседних элементов, а пары элементов, расположенных на расстоянии d
друг от друга. Выполняются аналогичные проходы, пока не останется инверсий на
расстоянии d (т.е. сравниваются и при необходимости
обмениваются элементы a[i] и a[i+d] вместо a[i] и a[i+1]
при обычной пузырьковой сортировке).
Затем, когда в массиве уже не останется инверсий на расстоянии d,
величина d уменьшается, например, вдвое, и все повторяется.
Последний шаг всегда выполняется для d=1 (т.е. выполняется
обычная пузырьковая сортировка). Например, для n=100 последовательность
значений d может быть следующая: 50, 25, 12, 6, 3, 1. Убыстрение достигается
за счет того, что "тяжелые" элементы в случае d>1 при обменах быстрее перемещаются к
концу массива. Подобная сортировка называется Сортировкой Шелла
(у нее есть много вариантов в зависимости от стратегии выбора последовательности
значений d).
Сортировка методом прямого выбора
Идея сортировки методом прямого выбора совсем простая.
Находим в массиве минимальный элемент и ставим его в начало массива
(на место с индексом 0), меняя его с элементом a[0].
Затем из оставшихся элементов a[1], ..., a[n-1]
опять находим минимальный и ставим его
на место с индексом 1, меняя его с a[1].
На третьем шаге рассматриваем элементы a[2], ..., a[n-1],
находим среди них минимальный и меняем его местами с элементом a[2].
И так далее, пока не останется всего один элемент.
void directSort(double *a, int n) {
for (int i = 0; i < n-1; ++i) {
int indMin = i; // индекс минимального элемента
for (int j = i+1; j < n; ++j) {
if (a[j] < a[indMin])
indMin = j;
}
if (i != indMin) { // ставим минимальный эл-т на место i
double tmp = a[j];
a[j] = a[indMin]; a[indMin] = tmp;
}
}
}
Сортировка методом прямого выбора работает чуть быстрее, чем пузырьковая,
за счет того, что в ней намного меньше обменов элементов
(не больше, чем n-1).
Но все равно время выполнения пропорционально квадрату n
(т.е. при увеличении длины массива в 10 раз время увеличивается в 100 раз).
Еще раз отметим, что подобные алгоритмы сортировки можно использовать
только для совсем небольших значений n.
2. Поиск
Задача поиска элемента в некоторой структуре данных также очень важна
в программировании и встречается буквально на каждом шагу. Мы рассмотрим ее
в простейшей постановке: дан массив длины n, содержащий элементы некоторого
типа; мы хотим найти в нем элемент x либо убедиться, что x
в массиве не содержится. Если x содержится в массиве, то требуется
найти индекс ячейки массива, содержащей x. Кроме того, в случае, когда
элементы массива упорядочены (по возрастанию либо по убыванию), то, если
x не содержится в массиве, требуется найти индекс той ячейки,
в которую можно добавить елемент x (передвинув оставшиеся элементы
на одну позуцию вправо), сохранив при этом упорядоченность элементов
массива. В любом случае (и когда элементы массива не упорядочены, и когда
упорядочены) прототип функции поиска выглядит следующим образом (для
определенности мы ищем целое число в целочисленном массиве):
bool search( // Поиск элемента x в массиве a
const int *a, // Указатель на начало массива
int n, // Число элементов массива
int x, // Искомый элемент
int *idx // Результат: адрес переменной, в которую записывается
// индекс искомой ячейки массива
);
На вход функции search подается константный указатель на начало массива a
и его длина n. (Константность означает, что элементы массива можно
только читать, но нельзя записывать.) В результате работы функция возвращает
значение true, если элемент x содержится в массиве,
и false в противном случае; в выходную переменную
с адресом idx записывается индекс искомой
ячейки массива (она либо содержит x, либо в нее x следует
добавить для сохранения упорядоченности массива).
Последовательный поиск
Рассмотрим сначала простейший вариант, когда элементы массива, в котором
осуществляется поиск, не упорядочены. В этом случае нам не требуется определять
индекс ячейки массива, когда искомый элемент x в нем не содержится —
индекс определяется только тогда, когда элемент найден. Нетрудно реализовать
функцию последовательного поиска, перебирая подряд все элеметы массива до тех
пор, пока мы либо не найдем элемент, либо массив закончится.
bool search( // Последовательный поиск элемента x в массиве a
const int *a, // Указатель на начало массива
int n, // Число элементов массива
int x, // Искомый элемент
int *idx // Результат: адрес переменной, в которую записывается
// индекс ячейки массива, содержащей x
) {
for (int i = 0; i < n; ++i) { // цикл для каждого эл-та массива
if (a[i] == x) { // если a[i] == x
*idx = i; // то записываем i в вых.переменную
return true; // завершаем ф-цию, возвращая true
} // конец если
} // конец цикла
return false; // возвращаем false
}
Бинарный поиск
Последовательный поиск на практике применяется только для
небольших массивов, работает он за время порядка O(n).
Например, если длина массива равна 1000000 (миллион), то
в алгоритме последовательного поиска выполняется в среднем 500000
операций сравнения, когда искомый элемент x содержится в массиве, и
1000000 сравнений, когда не содержится. Поэтому для больших массивов
обязательно нужно хранить элементы в порядке возрастания
(или убывания) и применять бинарный поиск, который работает за время
порядка O(log2 n). Для n=1000000 (миллион)
log2 n ≅ 19.93,
т.е. при бинарном поиске выполняется
около 20 операций сравнения — намного меньше миллиона при последовательном
поиске!
Идея бинарного поиска иллюстрируется шуточной задачей
"Как поймать льва в пустыне". Нужно поделить пустыню забором пополам
и выбрать ту половину, в которой находится лев; ее снова поделить пополам
и продолжать так до тех пор, пока лев не окажется пойманным (т.е. площадь
огороженной части окажется достаточно небольшой). Поскольку на каждом шаге
площадь огороженного участка пустыни, в котором находится лев, уменьшается
вдвое, то время работы алгоритма логарифмическое, порядка
O(log2 n).
Применение схемы инварианта цикла в алгоритме бинарного поиска
Итак, предполагаем, что элементы массива упорядочены по возрастанию
(нестрого):
a[0] ≤ a[1] ≤ ... ≤ a[n-1].
В алгоритме бинарного поиска мы будем хранить два индекса
i0 < i1, задающие отрезок
массива, в котором может находиться искомых элемент x.
(Индексы i0 и i1 как бы задают огороженный участок
пустыни, в котором находится лев.) Определим точно неравенство,
которое должно выполняться для переменных
a[i0], x, a[i1]. Так как i0 —
начало, а i1 — конец отрезка массива, то
i0 < i1.
Лев считается пойманным, когда размер клетки минимален, т.е.
i1 - i0 = 1. При этом, если x
не содержится в массиве, то должны выполняться неравенства
a[i0] < x < a[i1].
Если x содержится в массиве, то мы находим его первое вхождение
в массив (в случае нескольких равных элементов), а этом случае предыдущий
элемент должен быть строго меньше, чем x:
a[i0] < x = a[i1].
Объединяя эти 2 случая, получаем неравенство
a[i0] < x ≤ a[i1].
Чтобы не исключать "крайние" случаи, будем считать, что
a[-1] = -∞, a[n] = +∞.
Основная идея реализации алгоритма бинарного поиска состоит в том,
что мы строим цикл так, чтобы сохранялось условие
a[i0] < x ≤ a[i1].
Более точно, из истинности этого условия до начала выполнения
тела цикла должна следовать его истинность по окончании выполнения тела цикла.
Также нам нужно обеспечить выполнение этого условия перед началом работы
цикла. Подобное условие называется инвариантом цикла. Цикл наш будет
завершаться, когда i1 - i0 = 1.
Из этого неравенства и инварианта
цикла будет следовать, что наша задача решена, поскольку
a[i1-1] < x ≤ a[i1].
Искомый индекс в этом случае равен i1, элемент x содержится
в массиве тогда и только тогда, когда выполняется равенство
x = a[i1].
Программа разбивается на 2 части. Сначала мы рассматриваем отдельно
вырожденные случаи, чтобы в общем случае обеспечить выполнение инварианта
перед началом работы цикла. Во второй части строится цикл, сохраняющий
инвариант и на каждом шаге уменьшающий расстояние между i0 и i1.
bool binSearch( // Бинарный поиск элемента x в массиве a
const int *a, // Указатель на начало массива
int n, // Число элементов массива
int x, // Искомый элемент
int *idx // Результат: адрес переменной, в которую
// записывается индекс ячейки массива, либо
// содержащей x, либо в которую следует добавить x
) {
// Сначала рассматриваем особые случаи
if (n < 0) { // Массив пуст
*idx = 0;
return false;
} else if (x <= a[0]) { // x <= мин. эл-та массива
*idx = 0;
return (x == a[0]);
} else if (x > a[n-1]) { // x > макс. эл-та массива
*idx = n;
return false;
} else { // Общий случай
assert(
n > 0 &&
a[0] < x && x <= a[n-1]
);
int i0 = 0; int i1 = n-1;
while (i1 - i0 > 1) { // цикл пока длина отрезка > 1
assert(a[i0] < x && x <= a[i1]); // Инвариант цикла
int c = (i0+i1)/2; // Середина отрезка
if (a[c] < x) { // Если x > среднего эл-та
i0 = c; // то выбираем правую половину
} else { // иначе
i1 = c; // выбираем левую половину
} // конец если
} // конец цикла
assert(a[i1-1] < x && x <= a[i1]);
*idx = i1; // Возвращаем результат
return (x == a[i1]);
}
}
Полный текст программы, готовой для выполнения на автоматическом тестере,
содержится в файле "binSearch.cpp".
Конструкция assert (утверждение)
В приведенной выше программе неоднократно использовалась
конструкция assert (утверждение). Она используется для проверки
правильности работы программы. После слова assert записывается
утверждение, которое по логике автора программы должно быть истинным
в данной точке. При выполнении компьютер проверяет истинность
утверждения. Если оно не выполняется, то это однозначно свидетельствует
об ошибке в программе, так что ее дальнейшее выполнение бессмысленно.
Поэтому выполнение программы прерывается, печатается сообщение об ошибке
с указание места в программе (имя исходного файла, номер строки), в котором
выявлена ошибка. Если же условие в операторе assert истинно, то
программа продолжает работу так, как будто оператора assert
вообще не было.
Отметим, что конструкцию assert никогда не следует использовать
для проверки корректности исходных данных! Некорректные данные —
это нормальная ситуация, которая должна учитываться правильной программой,
а срабатывание assert должно происходить только в случае ошибки
программиста. В правильной программе команда assert никогда не
должна срабатывать! Конструкция assert — это не вызов функции,
а макроопределение препроцессора: при компиляции в отладочном
режиме она реально приводит к проверке указанного условия, но когда
программа компилируется в окончательном варианте (release version), то
препроцессор попросту выкидывает все команды assert. Иными словами, при
компиляции окончательной версии программы
команды assert рассматриваются всего лишь как
комментарии. (При окончательной компиляции надо определить переменную
NDEBUG препроцессора.) Это дает возможность контролировать работу программы
в отладочном режиме, при этом не теряя скорости ее выполнения в окончательной
версии.
Конструкция assert — это очень мощное средство отладки программы,
поскольку она позволяет выявить ошибку на самой ранней стадии. Практическая
рекомендация состоит в том, чтобы использовать assert как можно чаще.
Если по замыслу программиста в конкретной точке программы должно выполняться
некоторое утверждение, то следует сформулировать его явно, используя assert.
Например, пусть в программе мы извлекаем квадратный корень из вещественного
числа x, вызывая функцию sqrt(x).
Тогда полезно перед извлечением корня явно написать утверждение,
что аргумент фунции sqrt неотрицательный:
assert(x >= 0.);
y = sqrt(x);
Если в результате ошибки программиста значение x при выполнении программы
в отладочном режиме будет отрицательным, то мы об этом тут же узнаем.
При выполнении программы в окончательном режиме все команды assert
выкидываются препроцессором, так что программа не замедляется.
В случае использования конструкции assert надо в начале файла
подключить стандартный заголовочный файл assert.h:
#include <assert.h>
Лекция 8.
Задачи на работу с массивами. Часть 3
Пример: работа с массивами как с множествами
Рассмотрим следующий пример на работу с массивами. Пусть два целочисленных
массива содержатся в файлах "ina.txt" и "inb.txt", при этом файлы содержат
просто наборы чисел без указания их количества в начале файла. Нужно прочесть
файлы в два массива, предварительно подсчитав количество элементов в каждом
файле и создав массивы соответствующих размеров в динамической памяти. При этом
считаем, что массивы должны быть непустыми. (При отсутствии файла или пустом файле
программа должна завершиться с кодом -1.) Далее нужно выполнить сортировку
массивов и удалить повторяющиеся элементы: подсчитать число различных элементов массива
и множество различных элементов записать в начало массива в порядке их возрастания.
Наконец, в выходной файл "output.txt" надо записать в порядке возрастания
те элементы первого массива, которые не встречаются во втором.
Поскольку мы делаем одни и те же действия с двумя разными массивами, удобно оформить
эти действия в виде функций. Первая функция inputArray
вводит массив из файла, подсчитывая
количество элементов в файле и захватывая память под массив в динамической памяти
(в куче). Функция возвращает true, если это удалось сделать, и false в противном случае
(если файл отсутствует или не открывается, либо файл не содержит ни одного числа).
Вот прототип функции ввода массива:
bool inputArray(const char *fileName, int **a, int *n);
Отметим, что у функции два выходных параметра: адрес начала массива и его длина.
Функции передаются адреса переменных, в которые она должна записать результат,
отсюда появляется дополнительная звездочка в описании формальных параметров
a и n
(например, "int **a" — это указатель на переменную, в которую нужно записать
адрес начала массива и которая имеет тип "int *"). Вот как используется функция
inputArray, например, в функции main():
int main() {
int *a;
int n;
if (!inputArray("ina.txt", &a, &n)) // если неуспех, то
return -1; // завершить программу с кодом ошибки
// Массив a создан в динамической памяти, его элементы успешно введены
// из файла "ina.txt", длина массива записана в переменную n.
. . .
Реализация этой функции:
bool inputArray(const char *fileName, int **a, int *n) {
FILE *f = fopen(fileName, "r");
if (f == NULL)
return false;
// Count the number of elements in the file
int x;
int m = 0;
while (fscanf(f, "%d", &x) == 1) {
++m;
}
rewind(f);
if (m == 0) {
// Empty file
fclose(f);
return false;
}
// Allocate a memory for array
int *arr = new int[m];
// Input elements
for (int i = 0; i < m; ++i) {
fscanf(f, "%d", arr+i);
}
fclose(f);
*a = arr;
*n = m;
return true;
}
Вторая функция, которую мы дважды используем в программе
для двух разных массивов — это функция редуцирования массива.
Она сортирует элементы массива по возрастанию и затем подсчитывает
число различных элементов, одновременно записывая различные элементы
в начало массива в порядке из возрастания.
Функция reduce возвращает число различных элементов массива. Вот ее прототип:
int reduce(int *a, int n);
Реализация функции reduce:
int reduce(int *a, int n) {
if (n == 0)
return 0;
sort(a, n);
int k = 1; // Number of different elements
for (int i = 1; i < n; ++i) {
// Invariant:
// i >= k &&
// a[0] < a[1] < ... < a[k-1]
if (a[i] > a[k-1]) {
if (i != k) {
a[k] = a[i];
}
++k;
}
}
return k;
}
Функция reduce использует функцию сортировки, которую мы
уже рассматривали. Вот прототип функции сортировки:
void sort(int *a, int n);
Реализация функции sort — например,
простейшая пузырьковая сортировка:
// Bubble Sort
void sort(int *a, int n) {
bool sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < n-1; ++i) {
if (a[i] > a[i+1]) {
// Swap elements
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
sorted = false;
}
}
}
}
Наконец, перейдем от вспомогательных функций к решению нашей задачи:
записать в файл "output.txt" в строго возрастающем порядке те элементы первого массива,
которых нет во втором массиве. Вот функция main:
int main() {
int *a, *b;
int n, m;
if (!inputArray("ina.txt", &a, &n)) {
return -1;
}
if (!inputArray("inb.txt", &b, &m)) {
return -1;
}
if (n == 0 || m == 0)
return -1;
int n0 = reduce(a, n); // n0 is the number of different elements in a
int m0 = reduce(b, m); // m0 is the number of different elements in b
// Write to the file "output.txt" those elements of the
// array a[] that do not belong to b[]
FILE *out = fopen("output.txt", "w");
if (out == NULL) {
perror("Could not open the output file");
return -1;
}
// fprintf(out, "%d %d\n", n0, m0);
// Invariant:
// a[i] > b[0], ..., b[k-1] &&
// a[i] <= b[k]
int i = 0;
int k = 0;
// Ensure the implementation of invariant
// before the main loop
while (k < m0 && a[i] > a[k]) {
++k;
}
while (i < n0) {
// Invariant: a[i] > b[k-1] && a[i] <= b[k]
if (k >= m0 || a[i] < b[k]) {
// The element a[i] does not belong to the array b
fprintf(out, "%d ", a[i]);
}
++i;
if (i >= n0)
break;
// Ensure the implementation of invariant
while (k < m0 && a[i] > b[k]) {
++k;
}
}
fprintf(out, "\n");
fclose(out);
// Release a memory
delete[] a;
delete[] b;
return 0;
}
Целиком программа содержится в файле "diffArr.cpp".
Лекция 9.
Представление целых чисел в компьютере
Лекция 10.
Представление вещественных чисел в компьютере.
Машинный эпсилон
Лекция 11.
Точность вычислений. Суммирование рядов,
устойчивые и неустойчивые вычислительные схемы.
Представление матриц. Метод Гаусса приведения
матрицы к ступенчатому виду