Информатика · 11 класс · Урок 01

Анализ алгоритмов без полной трассировки

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

🎯 Цели урока и планируемые результаты

Определять результат работы алгоритма без полной трассировки.
Использовать инварианты и вариант цикла.
Определять входные данные, приводящие к заданному выходу.
Применять обратные рассуждения.

Шаблоны: сумма/счётчик, обработка цифр, разворот числа.
Границы: ноль, минимум/максимум, пустые данные.
Оценка сложности: O(1) · O(n) · O(n²).

📚 Ключевые понятия

Предусловие — что верно о входе до запуска.
Постусловие — что гарантированно верно после завершения.
Инвариант цикла — истинно до и после каждой итерации.
Вариант цикла — величина, монотонно движущаяся к остановке.
Трассировка и статический анализ.

Инвариант помогает держать в голове смысл состояния цикла, а не только значения переменных.

🧭 Приёмы быстрого анализа

1) Укрупнение (сверху‑вниз)

Сначала цель блока/цикла, потом детали.

Опишите словами: «суммирует элементы», «считает количество» и т.п.
Смотрите на имена: s — сумма, cnt — счётчик, r — результат.

2) Инвариант

s — сумма уже обработанных элементов.
r — развёрнутая часть числа.

3) Крайние случаи

Пустая последовательность, n=0.
Отрицательные, одинаковые элементы.

4) Обратные рассуждения

От результата — к условию входа («когда печатается …?»).

🌿 Анализ ветвлений

if x % 3 == 0 and x % 2 != 0:
    print("YES")
else:
    print("NO")

Без перебора: YES — для кратных 3 и нечётных чисел (3, 9, 15, …).

Приёмы: переводите условие на русский; проверьте 0 и отрицательные.

🔁 Анализ циклов и инвариантов

# Сумма 1..n (вариант цикла: i растёт к n)
s = 0
for i in range(1, n+1):
    s += i
# Инвариант: s = сумма первых i-1 чисел

Итог без трассировки: s = n(n+1)/2.

# Разворот цифр числа (while)
r = 0
while n > 0:
    r = r*10 + n % 10
    n //= 10
# Инвариант: r — разворот снятой справа части числа

Результат: r — исходное n в обратном порядке.

Если количество итераций зависит от данных — оцените его прежде, чем считать.

↩️ Определяем вход по известному выходу

def f(x):
    if x % 2 == 0:  # чётные
        return x // 2
    else:           # нечётные
        return 3*x + 1
# Для каких x получим y = 10?

Левая ветка: x//2 = 10 ⇒ x = 20.
Правая ветка: 3x+1=10 ⇒ x=3.

Ответ: x ∈ {3, 20}.

🧪 Разбор примеров (Python)

1) Счётчик по свойству

a = [6, 1, 9, 12, 7, 5]
cnt = 0
for x in a:
    if x % 3 == 0 and x % 2 != 0:
        cnt += 1
print(cnt)  # 1

2) Обработка цифр

n = 12030
s = 0
while n > 0:
    s += n % 10
    n //= 10
print(s)  # 6

3) Восстановление входа

def g(n):
    r = 1
    for k in range(1, n+1):
        r *= 2
    return r
# g(n) = 32 ⇒ n = 5

📝 Практикум (самопроверка)

Чему равен результат?
```
s = 1
for i in range(1, 6):
    s *= i
print(s)
```
Показать ответ
120

Когда печатается YES?

n = int(input())
if n % 5 == 0 and n % 2 == 0:
    print("YES")
else:
    print("NO")

Показать ответ

Кратные 10.

Сумма цифр числа 10⁶

Показать ответ
1.
Восстановите вход (результат 7):
```
def h(x):
    if x < 0: return -x
    if x % 2: return x
    return x // 2
```
Показать ответ
- x = -7
- x = 7
- x = 14

✅ Чек‑лист анализа

Цель фрагмента: что он накапливает/считает?
Сформулируйте инвариант простыми словами.
Оцените число итераций и «вариант цикла».
Проверьте крайние случаи: 0, пустые данные, одинаковые значения.
Для задач «по результату» — разбирайте ветви в обратном порядке.

Для вопроса «что выведет программа?» часто достаточно смыслового просмотра переменных.

🖼 Иллюстрации и ссылки

Пример блок-схемы — Пример блок‑схемы (локальный ресурс, Astra Child)

Граф потока управления — Граф потока управления (локальный ресурс, Astra Child)

Доп. чтение: Loop invariant, Big‑O notation, Control‑flow graph.