Завершение цикла
Завершение цикла означает, что выполнение алгоритма когда-нибудь прекратится, а не будет продолжаться бесконечно. Чтобы доказать остановку, нужно проследить изменение управляющей величины и показать, что условие цикла станет ложным; чтобы найти число итераций, — определить её начальное значение, шаг изменения и границу остановки.
Что значит завершение цикла
Цикл состоит из многократно выполняемого тела и условия продолжения. Одна полная проверка тела называется итерацией. В цикле с предусловием условие проверяется до выполнения тела, поэтому при ложном условии тело может не выполниться ни разу. В цикле с постусловием тело выполняется хотя бы один раз, а остановка определяется проверкой после тела. Перед решением задач полезно повторить условие цикла и способы записи циклического алгоритма.
Цикл завершается, если после конечного числа итераций его условие продолжения становится ложным. Если условие остаётся истинным всегда или выполнение не может дойти до проверки условия, цикл является бесконечным.
Обычно в задачах есть величина, которая меняется на каждой итерации: счётчик, координата, остаток, сумма или значение переменной исполнителя. Её называют управляющей величиной. Если она движется к границе, после которой условие нарушается, цикл остановится.
Найдите величину, которая на каждой итерации изменяется в одном направлении, и докажите, что она за конечное число шагов достигнет границы остановки. Например, при условии \(i \le n\) и изменении \(i := i+1\) значения \(i\) растут, поэтому условие станет ложным после достижения \(n+1\).
Счёт итераций по управляющей величине
Сначала определите, когда тело выполняется, а затем перечислите значения управляющей переменной. Для цикла с предусловием нужно учитывать, что первое значение проверяется до входа в тело. Если стартовое условие уже ложно, число итераций равно нулю. Связь с типичными задачами о начальном значении и шаге разобрана на странице Счётчик цикла.
Пусть переменная \(i\) сначала равна \(i_0\), после каждой итерации изменяется на постоянный шаг \(d\), а условие продолжения имеет вид \(i \le n\). При \(d>0\) значения перед выполнением тела таковы: \(i_0\), \(i_0+d\), \(i_0+2d\) и так далее. Последнее допустимое значение должно удовлетворять условию.
Здесь \(k\) — число итераций, а \(\lfloor x\rfloor\) обозначает целую часть числа. Если \(i_0>n\), тело не выполняется и \(k=0\). Аналогично, если переменная уменьшается: при условии \(i\ge n\) и шаге \(d<0\) нужно найти последнее значение, не меньшее \(n\).
| Условие продолжения | Изменение | Направление проверки |
|---|---|---|
| \(i\le n\) | \(i:=i+d\), \(d>0\) | от начального значения вверх |
| \(i\ge n\) | \(i:=i-d\), \(d>0\) | от начального значения вниз |
| \(i<n\) | \(i:=i+d\), \(d>0\) | последнее значение строго меньше \(n\) |
| \(i>n\) | \(i:=i-d\), \(d>0\) | последнее значение строго больше \(n\) |
Сколько раз выполнится тело цикла: \(i:=2\); пока \(i\le 11\) выполнять \(i:=i+3\)?
Алгоритм доказательства остановки
Для экзамена удобно использовать один и тот же порядок действий. Он помогает не перепутать число проверок условия с числом выполнений тела.
- Запишите условие продолжения цикла и определите, при каком значении оно перестаёт выполняться.
- Найдите управляющую величину: переменную, которая меняется на каждой итерации.
- Определите направление изменения: она возрастает, убывает, приближается к нулю или делится на некоторое число.
- Выразите её значение после \(k\) итераций.
- Найдите наибольшее допустимое число итераций или проверьте значения напрямую.
- Проверьте граничный случай: первая итерация и значение сразу после последней.
Если целочисленная неотрицательная величина на каждой итерации уменьшается хотя бы на 1, цикл обязательно завершится: она не может уменьшаться бесконечно, оставаясь неотрицательной.
Это правило особенно полезно для циклов, где переменная уменьшается не на постоянную величину, а, например, делится на 2. В таком случае число итераций удобно находить последовательным делением или сравнением степеней двойки. Если же величина иногда увеличивается, нужно анализировать весь алгоритм, а не только одну команду.
Разобранный пример
Рассмотрим цикл: \(x:=7\); пока \(x<40\) выполнять \(x:=x+6\). Требуется доказать завершение и найти число итераций.
Итак, цикл завершается после 6 итераций. Доказательство остановки основано на том, что \(x\) увеличивается на 6 и после конечного числа шагов превышает границу 40.
Показать проверку по значениям Решение
| Номер итерации | Значение \(x\) перед телом | Значение после тела |
|---|---|---|
| 1 | 7 | 13 |
| 2 | 13 | 19 |
| 3 | 19 | 25 |
| 4 | 25 | 31 |
| 5 | 31 | 37 |
| 6 | 37 | 43 |
| следующая проверка | 43 | тело не выполняется |
Особые случаи и типичные ошибки
Не каждый цикл можно считать по формуле арифметической прогрессии. Если шаг зависит от текущего значения, сначала выпишите несколько состояний или найдите другой инвариант. Для сложных алгоритмов полезна инвариант цикла: свойство, которое сохраняется после каждой итерации и помогает описать состояние.
При анализе программ исполнителя учитывайте не только переменную-счётчик, но и положение или состояние исполнителя. Команда может менять координаты, направление и другие параметры; для таких задач пригодятся страницы Состояние исполнителя и Положение исполнителя.
1. Считать последнюю проверку условия отдельной итерацией. Проверка, при которой условие уже ложно, не является выполнением тела. 2. Забывать о строгом знаке: \(i< n\) и \(i\le n\) дают разные ответы. 3. Использовать формулу для шага \(d>0\), когда переменная убывает. 4. Считать, что цикл обязательно выполнится хотя бы раз: это неверно для предусловия. 5. Проверять только рост переменной, не убеждаясь, что условие действительно связано с ней.
После вычисления числа итераций подставьте найденное число \(N\): значение управляющей величины после \(N\) итераций должно нарушать условие, а перед последней итерацией — удовлетворять ему.
Циклы с постусловием и переменным шагом
В цикле с постусловием тело выполняется до проверки условия, поэтому даже при начальном значении, которое уже соответствует остановке, одна итерация всё равно произойдёт. Сравните это с циклом с постусловием и не переносите без проверки формулу для цикла с предусловием.
Если шаг меняется, удобно составлять таблицу состояний: номер итерации, значение до тела, выполненная команда, значение после тела. Для алгоритмов с повторяющейся командой исполнителя проверьте, не возникает ли состояние, в котором переменная возвращается к прежнему значению. Возврат к состоянию без изменения условия часто является признаком бесконечного цикла.
Проверь себя
Главное
- Итерация — одно выполнение тела цикла; ложная финальная проверка итерацией не считается.
- Для доказательства остановки найдите управляющую величину и покажите, что она за конечное число шагов достигает границы.
- При постоянном шаге используйте \(i_k=i_0+kd\) и учитывайте строгие или нестрогие знаки условия.
- Для цикла с предусловием число итераций может быть нулевым, а цикл с постусловием выполняет тело хотя бы один раз.
- Всегда проверьте два соседних состояния: последнее допустимое и первое недопустимое.