Как написать цикл, чтобы он был верным,
и как записать, что он
делает. 10 класс, углублённый уровень — занятие седьмое.
Два урока плана за одну пару: «Инвариант цикла» и «Документирование программ». Они про одно и то же: самая ценная строка документации цикла — та фраза, которая верна на каждом его витке.
total = 1000
year = 0
while total < 2000:
total = total + total * 20 // 100
year = year + 1
print(year, total)| проверка условия | year | total |
|---|---|---|
| до цикла | 0 | 1000 |
| после 1-го витка | 1 | 1200 |
| после 2-го | 2 | 1440 |
| после 3-го | 3 | 1728 |
| на выходе | 4 | 2073 |
В каждой строке верно одно и то же: total — сумма на счёте через year лет. Переменные меняются, фраза — нет.
Утверждение о переменных, которое верно перед каждой проверкой условия: до первого витка, после каждого и на выходе.
Условие на выходе становится ложным. Инвариант остаётся верным всегда.
Меняется всё. Не меняется связь между переменными.
total ≥ 2000 (условие ложно) и «total — сумма через year лет»
(фраза верна). Значит, year — первый год, когда вклад дорос до цели.
Наибольшее из n чисел. Запускаем — проверяем.
m = 0
for i in range(n):
x = int(input())
if x > m:
m = x
print(m)| ввод | напечатала | |
|---|---|---|
| 3 7 2 | 7 | верно |
| 5 1 8 | 8 | верно |
m = 0 утверждает, что ноль среди них
есть. Фраза неверна до первого витка — ошибка найдена без запуска.
-5 -2 -9 программа печатает
0, а нуля во вводе нет.
Тест проверяет те случаи, которые ты догадался придумать. Фраза проверяет все случаи сразу.
n = 5372
s = 0
while n > 0:
s = s + n % 10
n = n // 10
print(s)| n | s | s + сумма цифр n |
|---|---|---|
| 5372 | 0 | 0 + 17 |
| 537 | 2 | 2 + 15 |
| 53 | 9 | 9 + 8 |
| 5 | 12 | 12 + 5 |
| 0 | 17 | 17 + 0 |
Фраза: s + сумма цифр n = сумма цифр исходного числа. Проще: s — сумма уже оторванных цифр, n — то, что осталось.
На выходе n == 0 — подставляем в фразу: s + 0 = 17.
Программа считает сумму цифр — это доказано, а не проверено на трёх
примерах.
| Место | Вопрос к фразе | Сумма цифр |
|---|---|---|
| Начало | при каких значениях фраза верна до первого витка? | ничего не оторвано: s = 0 |
| Шаг | как сдвинуться к цели, чтобы фраза снова стала верной? | оторвали n % 10 — прибавили к s |
| Выход | когда фраза превращается в ответ? | n == 0 → while n > 0 |
Это и есть «составление цикла по заранее определённому инварианту» из плана: сначала фраза, потом код.
Наибольшая степень двойки, не больше N. Фраза: p = 2 ** k и p ≤ N.
k = 0
p = 1 # 2 ** 0 = 1 ≤ N
while p * 2 <= N:
p = p * 2
k = k + 1
print(k, p)while p <= NЛишний виток: на выходе p > N — фраза сломалась.
while p * 2 < NФраза цела, но на N = 16 выходим на 8: «не больше» — это
<=.
Проверять фразу надо на границе: N = 1, N — точная степень двойки, N на единицу меньше степени.
Тот же приём, что с максимумом в начале, — теперь для наименьшего, и как починить.
mn = 0
for i in range(K):
x = int(input())
if x < mn:
mn = x«mn — наименьшее из прочитанных» неверна уже до цикла. На 5, 8, 3 напечатает 0.
mn = int(input())
for i in range(K - 1):
x = int(input())
if x < mn:
mn = xИз одного прочитанного числа оно само и наименьшее — фраза верна с начала.
И номер первого наибольшего: строгое >.
С >= равное число перезапишет номер.
while a != b:
if a > b:
a = a - b
else:
b = b - a
print(a)| a | b |
|---|---|
| 12 | 18 |
| 12 | 6 |
| 6 | 6 |
Фраза: НОД(a, b) не меняется. Общий делитель a и b делит и a − b — поэтому вычитание НОД не трогает.
Выход: a == b. А НОД двух равных чисел — само число. Из кода
этого не видно; из фразы — сразу. Это задание 3 практикума.
i = i + 1 # увеличиваем i
# цикл
while n > 0:Пересказ строки: читать надо, нового ноль.
# Инвариант: s — сумма
# уже оторванных цифр
while n > 0:То, что верно, — и чего в строках не видно.
Комментарий, который врёт, хуже, чем никакого: без него читают код, а с ним верят и ошибаются. Сейчас поймаем такой.
Три комментария к одному циклу. Два — правда, один — нет. Какой?
s = 0
i = 0 # ① ещё ничего не сложено
while i < M:
i = i + 1
s = s + i # ② s — сумма от 1 до i
print(s) # ③ s — сумма от 1 до M−1s = 0, i = 0: чисел не
сложено, сумма пустая. Правда.
i единицу — и
прибавили новое i к сумме. На каждом витке снова верна.
Правда.
i < M ложно, а i рос
по единице — значит, i = M. Подставляем в ②:
s — сумма от 1 до M. Врёт.
M = 3 печатается 6
(1 + 2 + 3), а не 3 (1 + 2).
Условие i < M подсказывает «до M − 1» —
так ошибаются и авторы комментариев. Комментарий проверяют как код:
фразой и запуском.
# Ввод: натуральное число n
# Вывод: сумма цифр числа n
# Пример: 5372 -> 17
n = int(input())Что дать, что получить и пример. Карточка задания в практикуме устроена ровно так же — это и есть документация.
input("Введите число: ") — подсказка человеку за
клавиатурой.
Когда вывод читает машина (оболочка, ЕГЭ), текста в input()
нет.
>>> help(abs)
>>> help(round)Шапки, которые написали авторы Python. Попробуйте в IDLE.
| № | Программа | Фраза |
|---|---|---|
| 1 | Степень двойки: наибольшая, не больше N | p = 2 ** k и p ≤ N |
| 2 | Наименьшее и наибольшее из K чисел и номер первого наибольшего | mn, mx — из прочитанных; num — первый наибольший |
| 3 | НОД вычитанием и число вычитаний — с шапкой | НОД(a, b) не меняется |
zadanie1.py, zadanie2.py, zadanie3.py.Проверка.bat → «Найти мои файлы» → «Проверить всё».# Ввод:, # Вывод:,
# Пример: вход -> вывод и # Инвариант: ... перед
циклом. Без них оболочка задание не примет, даже если программа считает верно.
Отметка: три задания — «5», два — «4», одно — «3». Попыток сколько угодно.
Сначала тренажёр, потом три программы.
Домашнее задание — на странице «Домашнее задание»: шесть типов задач на чтение циклов и документации, Python дома не нужен. В начале следующей пары — проверочная по этим же типам.