Алгоритмы и структуры данных

Информация - сведение, независимое от типов данных. Информация бывает аналоговой и цифровой.

Данные - сведение для вывода, решения

Алгоритмы – это конечный набор инструкций на определенном языке, который описывает последовательность выполнимых и определенных шагов для решения задачи. Они применимы к разным входным данным

Особенности алгоритма:

1) Конечность: Алгоритм всегда должен завершаться после выполнения конечного числа шагов. Это означает, что он не бесконечно продолжается, а имеет четкую точку завершения.

2) Определенность: Каждый шаг алгоритма должен быть четко определен и иметь однозначное значение. Это означает, что действия, которые нужно выполнить, не могут иметь двусмысленных интерпретаций.

3) Ввод: Алгоритм имеет некоторое число входных данных, которые задаются до начала его работы или динамически определяются во время выполнения. Простыми словами, алгоритму нужно знать, с чем он будет работать.

4) Вывод: У алгоритма есть одно или несколько выходных данных, которые связаны с входными данными.

5) Эффективность: Эффективность алгоритма определяется тем, насколько простыми являются его операторы. Если мы можем точно выполнить эти операторы с помощью карандаша и бумаги в течение ограниченного времени, то алгоритм считается эффективным.

Псевдокод — это способ описания алгоритмов и структур данных с использованием естественного языка и элементов программирования. Он позволяет выразить основные идеи без деталей реализации. Проще говоря, это “черновик” для программы, который помогает программистам понять, как решить задачу, не вдаваясь в код.

В псевдокоде используется:

1. Выражения: Используйте арифметические операции, чтобы вычислить значения.
2. Объявления метода: Определите функции или методы для выполнения конкретных задач.
3. Структура принятия решений: Используйте условные операторы (if-else) для выбора разных путей в зависимости от условий.
4. Циклы: Используйте циклы (например, for или while) для повторения действий.
5. Индексирование массива: Обращайтесь к элементам массива по индексу.
6. Обращения к методам: Вызывайте методы объектов для выполнения определенных действий.
7. Возвращаемое значение метода: Убедитесь, что ваши методы возвращают нужные значения.

Давайте подробнее разберемся с алгоритмом нахождения наибольшего общего делителя (НОД) для двух натуральных чисел N и M.

1. Инициализация: Пусть P будет минимальным из чисел N и M. Это позволяет сократить диапазон поиска общих делителей.
2. Инициализация t: Устанавливаем t равным 1. Начальное значение НОД.
3. Проверка P: Если P равно 1, переходим к шагу 5. В противном случае переходим к шагу 4.
4. Поиск делителей:Задаем i последовательностью всех целых чисел от 2 до P.
5. По возрастанию проверяем каждое i:Если M делится на i без остатка (M % i == 0) и N делится на i без остатка (N % i == 0), то обновляем t: t = i. Это означает, что i является общим делителем для N и M.
6. Завершение алгоритма: Результатом НОД будет значение t.

Пример: Пусть N = 12 и M = 18.

• P = min(12, 18) = 12.
• t = 1 (начальное значение).
• Проверяем i от 2 до 12:i = 2: 12 % 2 == 0 и 18 % 2 == 0, обновляем t: t = 2.
• i = 3: 12 % 3 == 0 и 18 % 3 == 0, обновляем t: t = 3.
• i = 4: 12 % 4 == 0 и 18 % 4 != 0 (не делится на 4).
• …
• i = 12: 12 % 12 == 0 и 18 % 12 == 0, обновляем t: t = 12.
• НОД(12, 18) = 6 (так как 6 - наибольший общий делитель).

Этот алгоритм помогает найти наибольший общий делитель двух чисел, используя поиск общих делителей и выбор наибольшего из них.