Ponyatie-algoritma-i-osnovnye-algoritmicheskie-struktury

1.

Понятие алгоритма и основные
алгоритмические структуры
Информатика и программирование · Лекция

2.

ТЕОРИЯ
Что такое алгоритм?
Алгоритм — это точная, конечная последовательность
инструкций (шагов), предназначенная для решения
определённой задачи или класса задач.
Термин происходит от имени математика Аль-Хорезми (IX в.), чьи
труды по арифметике заложили основы вычислительной
математики.
Алгоритм обязательно должен быть понятен исполнителю — человеку,
машине или другой вычислительной системе — и приводить к результату
за конечное число шагов.

3.

СВОЙСТВА
Основные свойства алгоритма
Дискретность
Детерминированность
Конечность
Алгоритм состоит из отдельных,
чётко разграниченных шагов
(команд), выполняемых
последовательно.
Каждый шаг однозначен — никаких
двусмысленностей. Один и тот же
алгоритм при одних данных всегда
даёт одинаковый результат.
Алгоритм завершается за конечное
число шагов и обязательно приводит
к результату.
Результативность
Массовость
По окончании работы алгоритм выдаёт результат: число,
строку, файл или другой значимый выход.
Алгоритм применим к целому классу однотипных задач, а
не только к одному конкретному случаю.

4.

СПОСОБЫ ЗАПИСИ
Формы представления алгоритмов
Словесный (вербальный)
Формульный (математический)
Описание шагов на естественном языке. Доступно, но
допускает неоднозначность.
Пример: «Взять число, умножить на 2, вывести
результат».
Запись через математические формулы и выражения.
Применяется в вычислительных задачах и научных
алгоритмах.
Псевдокод
Язык программирования
Структурированная запись, напоминающая
программный код, но без строгого синтаксиса
конкретного языка. Удобен для проектирования.
Точная запись, понятная компилятору или
интерпретатору. Алгоритм превращается в исполняемую
программу.
Pascal · Python · Java · C++ · C#
Блок-схема (графический способ)
Трассировочная таблица
Визуальное представление с помощью стандартных
геометрических фигур: прямоугольник — действие,
ромб — условие, эллипс — начало/конец.
Табличная пошаговая запись, фиксирующая значения
переменных на каждом шаге выполнения. Используется
для анализа и отладки.

5.

СТРУКТУРЫ
Основные алгоритмические структуры
Линейная
Ветвление (условие)
Цикл (повторение)
Команды выполняются строго одна за
другой, в порядке записи. Нет
ветвлений и повторений.
В зависимости от условия
выполняется один из двух (или более)
блоков команд.
Блок команд повторяется заданное
число раз или пока выполняется
условие.
a = 5
b = 3
c = a + b
print(c)
if a > b:
print("a больше")
else:
print("b больше")
for i in range(5):
print(i)
while a > 0:
a -= 1
Любой алгоритм можно построить, используя только три перечисленные структуры — это доказывает теорема Бёма —
Якопини.

6.

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Алгоритм «Сумма двух чисел» на разных языках
Pascal
var a, b, c: integer;
begin
readln(a, b);
c := a + b;
writeln(c);
end.
Python
a = int(input())
b = int(input())
print(a + b)
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt(), b = sc.nextInt();
System.out.println(a + b);
}
}
C++
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << a + b;
return 0;
}
C#
using System;
class Program {
static void Main() {
int a = int.Parse(Console.ReadLine());
int b = int.Parse(Console.ReadLine());
Console.WriteLine(a + b);
}
}
Алгоритм один и тот же — меняется только синтаксис языка. Это наглядно демонстрирует
независимость алгоритма от языка реализации.

7.

АНАЛИЗ АЛГОРИТМОВ
Трассировочные таблицы
Трассировочная таблица:
Трассировочная таблица — это таблица, в которой
пошагово фиксируются значения всех переменных при
выполнении алгоритма. Позволяет понять логику
работы программы и найти ошибки.
Алгоритм (Python):
s = 0
for i in range(1, 5):
s = s + i
print(s)
Шаг
i
s (до)
s = s + i (после)
Нач.
—
0
0
1
1
0
1
2
2
1
3
3
3
3
6
4
4
6
10
Конец
—
—
print(10)
Алгоритм суммирует числа от 1 до 4. Ниже —
трассировка по шагам:
Итог: s = 10. Трассировка подтверждает корректность
алгоритма на каждом шаге.

8.

ПРАКТИКА · PYTHON
Практические задания
Демонстрационный пример — Чётность числа
Средний пример — Факториал числа
Вычислите факториал натурального числа n, введённого
пользователем. Напомним: n! = 1 × 2 × 3 × … × n
Программа проверяет, является ли введённое пользователем
число чётным или нечётным.
1
n = int(input("Введите число: "))
if n % 2 == 0:
print("Чётное")
else:
print("Нечётное")
1
Прочитайте число n с клавиатуры
Используйте цикл for и переменную-накопитель для
произведения
Выведите результат
Чему равен 0!? Обработайте этот случай в вашей
программе.
Структуры: линейная + ветвление. Оператор % — остаток от деления.
2
Лёгкий пример — Максимум из двух чисел
Сложный пример — Числа Фибоначчи
Пользователь вводит два числа. Программа должна вывести
наибольшее из них.
Выведите первые n чисел последовательности Фибоначчи, где
каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2,
3, 5, 8, …
Прочитайте два числа с клавиатуры
Сравните их с помощью условия if
Выведите большее число на экран
2
Прочитайте количество элементов n
Инициализируйте начальные значения: a = 0, b = 1
В цикле вычисляйте следующий элемент и обновляйте
переменные
Выведите все элементы последовательности
Что выведет программа, если оба числа равны? Учтите
этот случай.
Составьте трассировочную таблицу для n = 6 и проверьте
свою программу.

9.

Итог лекции
01
02
03
Алгоритм
Свойства
Структуры
Конечная, однозначная, результативная
последовательность шагов для решения
задачи
Дискретность · Определённость ·
Конечность · Результативность ·
Массовость
Линейная · Ветвление · Цикл — три
кирпича любого алгоритма
04
05
Языки
Трассировка
Pascal · Python · Java · C++ · C# — один алгоритм, разный
синтаксис
Пошаговая проверка алгоритма по таблице значений
переменных