Модуль 3. Циклы

Цикл задаёт повторяющееся преобразование состояния. Его поведение определяется четырьмя элементами: начальным состоянием, условием продолжения, телом и изменением, которое переводит выполнение к следующей проверке. Выбор между for, while и do while следует не из внешнего вида задачи, а из того, известен ли диапазон заранее, проверяется ли условие до первого шага и какое состояние управляет остановкой.

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

Стоимость алгоритма выводится из структуры повторения, а не из времени одного запуска. Постоянное число шагов, линейный проход, последовательное уменьшение размера в несколько раз и зависимые вложенные диапазоны приводят к различным точным счётчикам и классам роста. Машинная арифметика способна нарушить математическую модель цикла: счётчик переполняется, дробный шаг не достигает границы, а численное приближение перестаёт изменяться раньше заданного допуска.

Опора — Раздел 12: циклы, инварианты и завершимость. Дополнительно используются присваивание, составные присваивания, ++ и -- из Раздела 6, числовая модель и допуски из Раздела 7, операции Math из Раздела 8 и безопасный консольный разбор из Раздела 11.

Каждая задача оформляется отдельной консольной программой полным шаблоном курса и компилируется с <Nullable>enable</Nullable>. Разрешены только конструкции Разделов 1–12. Массивы, коллекции, собственные методы, рекурсия, исключения, DateTime, Stopwatch, Random, LINQ и конструкции последующих разделов не используются. Для циклов с численным критерием обязательны содержательный допуск, обнаружение отсутствия прогресса там, где оно возможно, и независимый предел MaxIterations. Если условие требует доказательства, отдельно формулируются предусловия, начальное состояние, мера прогресса, инвариант, его инициализация и сохранение, условие завершения и получаемое постусловие.

База практических заданий

Уровень I. Базовый

Форма цикла, управляющая переменная, начальное значение, конечная граница и правило изменения заданы условием. Число итераций либо его точная формула известны до запуска и не зависят от вводимых по ходу выполнения данных. Требуется без искажения реализовать заданную схему, назвать первый и последний обрабатываемые элементы, вывести точное число шагов и подтвердить указанный инвариант.

1. Полуинтервал индексов: Дано целое $n\ge0$. Циклом for вывести индексы полуинтервала

Отдельно подсчитать число выполнений тела, сохранить первый и последний выведенные индексы только при $n>0$ и подтвердить, что число итераций равно $n$. Для $n=0$ объяснить, почему тело не выполняется. Затем в отдельной версии заменить < n на <= n, заранее предсказать новый последний индекс и число итераций и объяснить ошибку на единицу.

2. Обратный отсчёт: Дано $n\ge0$. Циклом while вывести последовательность $n,n-1,\ldots,0$. Управляющая переменная уменьшается ровно на единицу после вывода. Подсчитать итерации и подтвердить формулу $n+1$. Инвариант перед очередной проверкой: уже выведены все целые от исходного $n$ до значения, на единицу большего текущего счётчика.

3. Обязательная первая итерация: Дано $n\ge1$. Циклом do while вывести числа от 1 до $n$ включительно и вычислить их сумму. До запуска указать число итераций, первый и последний члены. Инвариант после вывода $k$: накопитель равен $1+2+\dots+k$. Объяснить, почему предусловие $n\ge1$ позволяет использовать do while без отдельной обработки пустого диапазона и чем его семантика отличается от while.

4. Арифметическая прогрессия: Даны целые первый член $a$, разность $d$ и число членов $n\ge0$. Циклом for вычислить

без пересчёта текущего члена по формуле на каждой итерации: начать с current = a и обновлять его через current += d. Сравнить сумму с

Потенциально опасные произведения выполнять в long. Инвариант после $i$ итераций: накопитель равен сумме первых $i$ членов, а current = a + id.

5. Факториал: Дано $0\le n\le20$. Циклом for вычислить $n!$ в long, начиная с накопителя 1 и множителя 2. Вывести точное число умножений и подтвердить, что оно равно $\max(0,n-1)$. Инвариант перед итерацией с множителем $k$: накопитель равен $(k-1)!$. Объяснить роль нейтрального элемента произведения в случаях $0!$ и $1!$.

6. Целая степень последовательным умножением: Даны double baseValue и целый показатель $n\ge0$. Выполнить ровно $n$ умножений и получить $baseValue^n$ без Math.Pow внутри цикла. Инвариант после $i$ итераций:

После цикла сравнить результат с Math.Pow(baseValue, n) по абсолютной разности. Отдельно разобрать $n=0$ и объяснить начальное значение 1.0.

7. Последовательность Фибоначчи фиксированной длины: Для $1\le n\le91$ вывести первые $n$ чисел $F_0=0$, $F_1=1$, $F_k=F_{k-1}+F_{k-2}$ и вычислить их сумму. Использовать for и только две переменные для соседних членов. Для $n=1$ и $n=2$ не обращаться к несуществующим позициям и не вводить отдельные массивы. Инвариант перед формированием очередного члена связывает две рабочие переменные с соседними числами последовательности, а накопитель — с уже выведенным префиксом.

8. Табулирование без дробного счётчика: Получить таблицу

на отрезке $[-2,2]$ с шагом $0{,}25$. Управлять циклом целым индексом $i=0,\ldots,16$, а аргумент каждый раз вычислять как

Накопление x += 0.25 запрещено. До запуска определить точное число строк и значения крайних аргументов. Вывести $i$, $x$ и $y$ с выравниванием и четырьмя знаками после запятой.

9. Фиксированная серия измерений с пропусками: Дано число наблюдений $n\ge0$; далее программа получает ровно $n$ корректных целых значений от 0 до 100, где 0 означает пропуск. Циклом for вычислить число пропусков, количество принятых измерений, сумму, минимум, максимум и среднее только по принятым значениям. После пропуска использовать continue; экстремумы инициализировать первым принятым значением, а не искусственными пределами. Число итераций всегда равно $n$, независимо от числа пропусков. Для серии без принятых значений вывести отдельный итог без деления на ноль.

10. Прямоугольный вложенный обход: Даны rows >= 0 и columns >= 0. Двумя вложенными циклами вывести все пары

в построчном порядке. Для внутреннего цикла сформулировать инвариант обработанного префикса текущей строки, для внешнего — инвариант полностью завершённых строк. Подсчитать число посещений и доказать точную формулу rows * columns. При rows = columns = n указать класс $O(n^2)$.

11. Треугольный вложенный обход: Дано $n\ge0$. Вывести все пары

в лексикографическом порядке: внешний цикл идёт по $i$, внутренний — от $i+1$ до $n-1$. Подсчитать число пар и сравнить его с

Получить точное число итераций каждого запуска внутреннего цикла и общую сумму. Объяснить, почему зависимая граница уменьшает точный счётчик примерно вдвое, но не меняет класс $O(n^2)$.

12. Последовательные и вложенные фрагменты: Дано $n\ge0$. Первый цикл выполняет $3n$ элементарных действий, второй — $n^2$ действий прямоугольным вложенным обходом, третий всегда выполняет ровно 100 действий. Реализовать только увеличение трёх отдельных счётчиков, затем вывести их сумму и сравнить с формулой

Объяснить, почему последовательные стоимости складываются, почему фиксированный фрагмент имеет класс $O(1)$ и почему общий класс равен $O(n^2)$.

Уровень II. Продвинутый

Задан требуемый результат или свойство процесса, но не управляющее состояние, форма цикла и момент остановки. Число итераций заранее неизвестно: оно определяется входным потоком, достижением порога, уменьшением состояния или численной сходимостью. Требуется самостоятельно выбрать for, while, do while либо бесконечный цикл с контролируемым break, вывести меру прогресса и инвариант и обосновать завершение либо явно ограничить процесс, завершимость которого не следует из предусловий.

1. Повторный запрос числа: Запрашивать целое число из диапазона $[1,100]$ до первого корректного результата. null, неверный формат и число вне диапазона имеют разные исходы; при null дальнейшие запросы прекращаются, поскольку входной поток завершён. Самостоятельно выбрать do while либо while (true) с break, подсчитать фактически прочитанные строки и объяснить, почему число итераций нельзя определить до запуска. Успешное значение должно использоваться только после подтверждённого разбора и диапазона.

2. Поток измерений до маркера: Читать строки до маркера "stop" или null. Пустую строку и неверный формат целого отвергать через continue; корректное значение является измерением, включая ноль. Для непустого принятого потока вычислить количество, сумму, минимум, максимум и среднее. Экстремумы инициализировать первым принятым значением. Инвариант после каждой принятой строки должен описывать весь принятый префикс, а не число всех прочитанных строк.

3. Первое превышение порога: Даны первый положительный член $a$, неотрицательная разность $d$, положительный порог $L$ и предел MaxTerms. Последовательно суммировать арифметическую прогрессию до первого момента, когда сумма станет строго больше $L$, либо до исчерпания предела. Самостоятельно выбрать состояние и форму остановки, сохранить номер первого превышающего члена и различить исходы Exceeded и LimitReached. Инвариант до добавления очередного члена: сумма равна уже обработанному префиксу и не превышала $L$ после ни одного более раннего шага.

4. Числовой профиль: Дано неотрицательное значение long. За один проход по десятичным цифрам получить количество цифр, сумму, произведение ненулевых цифр, максимум, минимум, число нулей и разворот. Для исходного нуля принять одну цифру 0. Затем определить, является ли число палиндромом. Самостоятельно выбрать нейтральные значения и сформулировать инвариант, связывающий рабочий остаток, обработанный суффикс исходного числа и все накопители.

5. Алгоритм Евклида: Для двух положительных long найти НОД переходом

до $b=0$. Подсчитать итерации и доказать:

• инвариант $\gcd(a,b)$;
• сохранение неотрицательности;
• завершимость из $0\le a\bmod b<b$.

Сравнить число шагов для соседних чисел Фибоначчи и для пары, где одно число делит другое. Обосновать класс $O(\log\min(a,b))$ без измерения времени.

6. Быстрое возведение в степень: Даны double baseValue и целый показатель $n\ge0$. Самостоятельно построить бинарный алгоритм: при нечётном текущем показателе домножать результат на текущую базу, затем возводить базу в квадрат и делить показатель на 2. Использовать инвариант

Подсчитать отдельно умножения результата и возведения базы в квадрат, сравнить их с $n$ умножениями последовательного алгоритма и обосновать $O(\log n)$.

7. Целая часть квадратного корня: Для $0\le n\le\texttt{long.MaxValue}$ найти наибольшее целое $r$, для которого

двоичным поиском по диапазону кандидатов. Переполнение mid * mid исключить сравнением mid <= n / mid, отдельно обработав ноль. Самостоятельно определить границы, лучший подтверждённый ответ и инвариант отброшенных областей. Вывести число итераций и обосновать $O(\log n)$.

8. Геометрический ряд по допуску: Даны $|q|<1$, $\varepsilon>0$ и MaxIterations. Суммировать

рекуррентно, пока модуль первого ещё не добавленного члена не станет меньше $\varepsilon$ либо не будет достигнут предел. Инвариант после $k$ добавлений:

Сравнить сумму с $1/(1-q)$ и проверить оценку остатка

Различить успешную остановку по допуску и остановку по пределу.

9. Квадратный корень методом Ньютона: Для $a>0$ и $x_0>0$ повторять

до выполнения

либо достижения MaxIterations. Вывести приближение, остаток $|x^2-a|$, отклонение от Math.Sqrt(a) и число шагов. Проверить отсутствие прогресса условием next == current. Обосновать сохранение положительности и различие критериев по изменению состояния и по невязке уравнения.

10. Метод половинного деления: Найти корень $f(x)=x^3-x-2$ на $[1,2]$. Сохранять замкнутый отрезок, на концах которого значения имеют разные знаки, и делить его пополам до длины не больше $\varepsilon$, отсутствия прогресса или MaxIterations. До запуска получить верхнюю оценку числа шагов как минимальное $k$, для которого

Сформулировать инвариант локализации корня и меру прогресса — длину интервала.

11. Суммарная длина двоичных записей: Для каждого $k$ от 1 до $n$ внутренним циклом последовательного деления рабочей копии на 2 определить число двоичных разрядов и прибавить его к общему счётчику. Строки не строить. Связать результат внутреннего цикла с

как математической формулой, не вызывая логарифм в коде. Получить

Для $n=2^m-1$ вывести точную сумму по блокам одинаковой длины.

12. Пары делимости: Для каждого $d$ от 1 до $n$ перебрать положительные кратные $d,2d,\ldots\le n$ и подсчитать пары $(d,m)$, где $d\mid m$. Доказать точный счётчик

Через сравнение с гармонической суммой получить $O(n\log n)$. Объяснить, почему оценка $O(n^2)$ формально является верхней, но скрывает реальную структуру зависимых границ.

Уровень III. Экспертный

Исследуется не прикладной результат, а граница семантики или доказательства цикла. До запуска требуется предсказать последовательность состояний, достижимость условия остановки, точное либо асимптотическое число шагов и возможное нарушение инварианта. После запуска наблюдение связывается с порядком вычисления, переполнением, конечной точностью и положением break, continue или изменения управляющего состояния. Защитный предел используется только для безопасного эксперимента и не считается доказательством завершимости.

1. Границы, инкремент и ошибка на единицу: Исследовать схемы:

for (int i = 0; i < n; i++)
for (int i = 0; i <= n; i++)
for (int i = 1; i <= n; ++i)
for (int i = n; i > 0; i--)
for (int i = 0; i < n; i += k)
for (int i = 1; i < n; i *= 2)

Для каждой до запуска вывести первый и последний обрабатываемые элементы и точное число итераций при заданных $n$ и $k>0$, затем подтвердить отдельным счётчиком. Сравнить i++ и ++i в секции изменения for, где значение выражения отбрасывается, и в выражениях sum += i++ и sum += ++i, где результат используется. Объяснить связь границы, момента изменения и ошибки на единицу.

2. Переполнение управляющей переменной: Исследовать отдельно:

for (byte i = 250; i <= 255; i++)
{
    Console.WriteLine(i);
}

и

for (int i = int.MaxValue - 2; i <= int.MaxValue; i++)
{
    Console.WriteLine(i);
}

Добавить независимый аварийный счётчик, не изменяющий исследуемую переменную. До запуска предсказать значения после достижения максимума в обычном unchecked-контексте и объяснить, почему математически конечный диапазон превращается в незавершающийся цикл. Затем повторить изменение счётчика в checked и зафиксировать исключение в отдельном запуске без try/catch. Сформулировать предусловие, при котором обычное доказательство меры прогресса действительно применимо к конечному машинному типу.

3. Дробный счётчик и недостижимая граница: Начать с double x = 0.0 и десять раз выполнить x += 0.1, выводя G17. Сравнить итог с 1.0. Затем исследовать циклы с условиями x != 1.0 и x < 1.0, ограничив их независимым аварийным счётчиком, и каноническую версию с целым индексом и вычислением x = i * 0.1. До запуска предсказать число итераций; после объяснить двоичную непредставимость шага, накопление ошибки и различие равенства, диапазона и вычисления значения из целого индекса.

4. break, continue и потеря прогресса: Сравнить три программы. Первая использует for, пропускает кратные трём через continue и суммирует остальные числа от 1 до $n$. Вторая реализует то же через while, но располагает i++ после возможного continue; для безопасного запуска используется отдельный предел. Третья содержит два вложенных цикла и выполняет break во внутреннем при первом $j$, для которого $ij>L$. До запуска составить трассы для малых входов. Объяснить, почему continue в for всё равно приводит к секции изменения, почему в while он способен уничтожить меру прогресса и почему break завершает только ближайший цикл.

5. Лаборатория асимптотики: Реализовать шесть фрагментов, каждый из которых только увеличивает счётчик элементарной операции:

1. фиксированные 100 действий;
2. один проход длины $n$;
3. последовательное деление положительного значения $n$ на 2;
4. прямоугольный проход $n\times n$;
5. внешний проход $1,\ldots,n$ с внутренним делением текущего индекса на 2;
6. перебор кратных из задачи II.12.

Для $n=1,2,4,8,16,32,64$ вывести счётчики. Получить точные формулы либо двусторонние оценки и классифицировать фрагменты как $O(1)$, $O(n)$, $O(\log n)$, $O(n^2)$ и $O(n\log n)$. Соединить линейный и квадратичный фрагменты последовательно и объяснить сложение стоимостей. Отдельно указать, почему счётчик абстрактных операций подтверждает порядок роста, но не сравнивает реальное время разных операций и сред выполнения.

6. Недостижимый допуск и застой приближения: Методом половинного деления приближать $\sqrt2$ как корень $x^2-2$ на $[1,2]$. Сравнить критерии:

1. ширина отрезка не больше допуска;
2. $|x^2-2|$ не больше допуска;
3. точное равенство x * x == 2.0.

Для допусков $10^{-6}$, $10^{-12}$ и $10^{-30}$ использовать MaxIterations и отдельно обнаруживать mid == left || mid == right. До запуска предсказать достижимость критериев; после объяснить конечность множества double, округление середины, непредставимость $\sqrt2$ и различие трёх защит: содержательного допуска, обнаружения застоя и предела итераций.

Обязательные контрольные наборы

Итог модуля

Ученик строит повторение как явную систему «начальное состояние → условие продолжения → тело → изменение», выбирает for, while или do while по природе управляющего состояния и отличает заранее ограниченный диапазон от остановки по данным, порогу или сходимости. Для каждого содержательного цикла формулируются мера прогресса и инвариант, доказываются их инициализация и сохранение и выводится постусловие при завершении. Ученик управляет полуинтервалами и граничными значениями, безопасно применяет break и continue, повторяет консольный ввод, защищает численные процессы допуском, обнаружением застоя и пределом итераций и выводит точные счётчики и классы $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$ и $O(n^2)$ из структуры повторения.

Покрытие опоры и границы

• for, while, do while, инициализация, условие и изменение: I.1–I.8; самостоятельный выбор формы — II.1–II.10.
• Полуинтервалы, первый и последний элементы, ошибка на единицу и заранее известное число итераций: I.1–I.12, III.1.
• Остановка по состоянию, маркеру, порогу и допуску: II.1–II.10, III.3 и III.6.
• Вложенные циклы и зависимые границы: I.10–I.12, II.11–II.12, III.4–III.5.
• break, continue и повторный запрос ввода: I.9, II.1–II.3, III.4.
• Мера прогресса, инвариант, инициализация, сохранение и постусловие: I.2–I.12, II.2–II.10.
• Точные счётчики и классы $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$: I.10–I.12, II.5–II.7, II.11–II.12, III.1 и III.5.
• Переполнение счётчика, дробный шаг, недостижимый допуск и отсутствие прогресса: III.2–III.4, III.6.
• Различие асимптотической оценки и фактического времени: I.12 и III.5.

За границей: массивы и коллекции, foreach, собственные методы, рекурсия, генераторы последовательностей, параллельные циклы и измерение производительности через Stopwatch вводятся позднее. Завершимость процессов, не доказуемая в рамках изученной модели, не объявляется установленной только потому, что контрольный запуск закончился; для безопасного исследования применяется явный предел итераций.