Понятная теория и эффективные тренажеры с объяснением! Вы успеете подготовиться к экзамену! Начните занятия прямо сейчас!
Понятие алгоритма
Впервые определение алгоритма появляется в 1930 году и с тех пор становится неотъемлемой частью информатики. Это понятие характеризует алгоритм, как точную последовательность действий над исходными данными, которая позволяет получить в итоге определенный результат.
Таким образом, любую задачу можно разложить на составляющие, которые обычно представляют собой элементарные действия. Типовая схема алгоритма представлена ниже:
С развитием компьютерных технологий алгоритмы позволили преобразовать в конечные и понятные последовательности большинство различных процессов, что привело к компьютеризации и роботизации большого количества сфер жизни.
Параметры алгоритма
Но не каждая последовательность действий может называться алгоритмом – имеется несколько требований, которые предъявляются для соответствия последовательности действий общепринятым стандартам. Сюда входит:
-
Дискретность: возможность разложить задачу на определенный набор конечных заранее определенных этапов.
-
Детерминированность: каждый шаг можно трактовать одинаково. К тому же любой шаг должен быть понятен исполнителю алгоритма.
-
Массовость: набор действий должен подходить не для одной задачи, а для целого класса задач.
-
Результативность: правильный алгоритм приводит к результату при рассмотрении различных наборов исходных данных.
-
Конечность: любой алгоритм имеет определенное количество шагов.
-
Эффективность: алгоритм решает задачу за столь малое время, что его использование оправдано.
Отдельно стоит упомянуть, что любую задачу можно решить несколькими способами, которые отличаются друг от друга по эффективности. Суть эффективности заключается в минимальном использовании ресурсов, в которые входит время и память компьютера. Чем меньшими ресурсами удается обойтись при построении алгоритма, тем более эффективным он считается.
Составные части алгоритмов
Алгоритм включает в себя три основных логических структуры, которые применяются повсеместно. Это алгоритмы ветвления, цикла и следования. Имеется большой блок заданий к ЕГЭ, включающий данную тему.
-
Следование – переход от одной команды к другой
-
Ветвление – при проверке условия определяет выбор той или иной ветви алгоритма.
-
Цикл – многократное выполнение определенной последовательности действий. Набор команд, которые выполняются в рамках цикла, называются телом цикла.
Более подробно стоит остановиться на алгоритмах с использованием ветвлений и циклов. Если следование выполняется всегда безусловно, то ветвления и циклы содержат в себе определенные условия для их выполнения или невыполнения. В случае с циклом также можно выделить еще и условие завершения цикла – в противном случае такой цикл может уйти в бесконечность, что сделает программу заведомо невыполнимой.
При записи алгоритмов очень важно пользоваться комментариями, которые смогут пояснить то или иное действие. Кроме того, также можно использовать «говорящие» переменные. В примере на языке Си это показано.
Примеры
Подготовка к ЕГЭ включает в себя список задач, в которых проблему, описанную словами, необходимо преобразовать в конечный алгоритм. Для простоты понимания далее примеры будет приводиться на языке псевдокод и Си.
В качестве примера работы с алгоритмами ветвления, цикла и следования рассмотрим поиск наибольшего числа в наборе.
ПРИМЕР 1
НАЧ
ТАБ A[15, 42, 73, 8, 23, 91, 34]
ЦЕЛ X := длина(А)
ЦЕЛ max :=A[0]
НЦ для j от 1 до X
ЕСЛИ A[X] > max
ТО max := A[X]
КЦ
КОН
Тот же алгоритм на языке Си
#include <stdio.h>
int main() {
int arr[] = {15, 42, 73, 8, 23, 91, 34}; // создать и заполнить массив цикла
int n = sizeof(arr); // присвоить размер массива выделенной переменной
int max = arr[0]; // Инициализируем max первым элементом массива
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i]; // Обновляем max, если текущий элемент больше
}
}
printf("Наибольшее число в массиве: %d\n", max);
return 0;
}
Поиск наибольшего числа в массиве представляет собой простую вариацию поиска, в которой перебираются все элементы массива на соответствие определенному условию. Данный пример можно считать базовым при подготовке к изучению алгоритмов сортировки.
Фактически, использование алгоритмов ветвления и цикла позволяет перебрать элементы массива в заданных пределах, в том числе и ограничиться какой-либо его частью.
ПРИМЕР 2. Вывести все четные числа в массиве
НАЧ
ТАБ A[12, 3, 45, 6, 22, 8, 11, 14]
ЦЕЛ X := длина(А)
НЦ для j от 1 до X
ЕСЛИ A[X] mod 2 = 0
ТО ВЫВОД A[X]
КЦ
КОН
Тот же алгоритм на языке Си
#include <stdio.h>
int main() {
int arr[] = {12, 3, 45, 6, 22, 8, 11, 14}; // заполненный исходный массив
int n = sizeof(arr); // присвоить размер массива переменной
printf("Четные числа в массиве:\n");
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) { // Проверка элемента массива на четность
printf("%d ", arr[i]); // Вывод четного числа на экран
}
}
printf("\n");
return 0;
}
Существует множество алгоритмов по обработке одномерных массивов. Алгоритмы ветвления и цикла в тех или иных формах встречаются в поиске, сортировке, замене и иных заданиях к ЕГЭ.
Примеры задач, алгоритмы в которым можно написать самостоятельно в рамках подготовки к ЕГЭ
-
Посчитать сумму значений в массиве
-
Заменить все значения в массиве, которые меньше 0
-
Выбрать все нечетные значения массива
-
Выбрать второй по величине элемент массива
-
Выбрать минимальный элемент массива
-
Вывести на экран каждый четный элемент массива
-
Вывести на экран номер максимального элемента
-
Вывести на экран номера элементов, которые больше 0.
Заключение
Определение алгоритма задает четкую последовательность определенных действий.
Алгоритмы ветвления и цикла – необходимый элемент современного программирования, необходимый для перебора больших объемов данных и проверки соответствия определенному условию.
Важно помнить основные требования к алгоритму: дискретность, детерминированность, массовость, результативность, конечность, эффективность – и соблюдать их при составлении алгоритмов решений собственных задач.
Более сложные примеры задач, включая работу с двумерными массивами, будут разобраны в следующих уроках.