Задача: 819D6B

Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, кратное 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 3. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число – минимальное число, кратное 3. **Пример работы программы:** | **Входные данные** | **Выходные данные** | | --- | --- | | 3 21 12 31 | 12 | --- Номер задачи: 819D6B 📚 # Тема 16. Программирование: Циклы и Рекурсия На ОГЭ эта тема проверяет умение трассировать (выполнять вручную) программы с циклами, рекурсивными функциями и найти результат или нужное начальное значение. --- ## 1. Цикл WHILE (Пока) Выполняется, пока условие истинно. Количество итераций неизвестно заранее. ```python x = 100 while x > 1: x = x // 2 # целочисленное деление на 2 print(x) ``` **Трассировка (выполнение вручную):** | Итерация | x до | Условие x > 1 | x после | |----------|------|---------------|---------| | 1 | 100 | Да | 50 | | 2 | 50 | Да | 25 | | 3 | 25 | Да | 12 | | 4 | 12 | Да | 6 | | 5 | 6 | Да | 3 | | 6 | 3 | Да | 1 | | 7 | 1 | **Нет** | — | Вывод: `print(1)` → **1** > **Совет:** При трассировке рисуйте таблицу. Каждая строка — одна итерация цикла. --- ## 2. Цикл FOR (Для) Выполняется фиксированное количество раз или по диапазону. ```python for i in range(1, 6): # i = 1, 2, 3, 4, 5 print(i * i) ``` Вывод: 1, 4, 9, 16, 25 ### Параметры range: | Вызов | Числа | |-------|-------| | `range(5)` | 0, 1, 2, 3, 4 | | `range(1, 6)` | 1, 2, 3, 4, 5 | | `range(2, 10, 2)` | 2, 4, 6, 8 | | `range(10, 0, -1)` | 10, 9, 8, ..., 1 | > **Совет:** `range(a, b)` включает `a`, но **не включает** `b`. Часто ловушка для невнимательных. --- ## 3. Рекурсия Функция, которая вызывает саму себя. Обязательно должно быть **базовое условие** (когда остановиться). ```python def F(n): if n <= 1: return 1 # базовый случай return n + F(n-1) # рекурсивный случай ``` ### Ручная трассировка рекурсии: Чтобы вычислить `F(5)`, разворачиваем: ``` F(5) = 5 + F(4) F(4) = 4 + F(3) F(3) = 3 + F(2) F(2) = 2 + F(1) F(1) = 1 ← база, начинаем собирать обратно F(2) = 2 + 1 = 3 F(3) = 3 + 3 = 6 F(4) = 4 + 6 = 10 F(5) = 5 + 10 = 15 ``` **Ответ: `F(5) = 15`** (это $1 + 2 + 3 + 4 + 5$) > **Совет:** Начните с самых маленьких значений (базовые случаи) и идите вверх. --- ## 4. Типовые задачи ОГЭ ### Тип 1: Найти значение, которое выведет программа Трассируйте код шаг за шагом: 1. Запишите начальные значения переменных. 2. Выполняйте тело цикла, обновляя переменные. 3. Проверяйте условие после каждой итерации. 4. Когда условие стало ложным — цикл закончился. ### Тип 2: Найти наибольший/наименьший X при котором программа выводит Y ```python x = ? while x > 1: x = x // 3 print(x) ``` "При каком наибольшем начальном x программа выведет 1?" **Метод:** Проверяйте значения x от большего к меньшему, пока не найдёте нужный результат. Или используйте "обратный" анализ. Если финальный x = 1, значит на последнем шаге x // 3 = 1, то есть x было от 3 до 8 (3//3=1, 4//3=1, ..., 8//3=2≠1). Значит перед последним шагом x был 3, 4 или 5 (все дают 1 после //3). И так далее... --- ## 5. Целочисленные операции Эти операции очень важны для понимания алгоритмов: | Операция | Символ | Пример | Результат | |----------|--------|--------|-----------| | Целочисленное деление | `//` | `17 // 5` | 3 | | Остаток от деления | `%` | `17 % 5` | 2 | | Обычное деление | `/` | `17 / 5` | 3.4 | > **Совет:** `n // 2` — "сдвиг" числа вправо в двоичной записи. Это быстрый способ "срезать" последний бит. --- ## 6. Работа с цифрами числа Частые операции в задачах: ```python n = 1234 last_digit = n % 10 # 4 (последняя цифра) n_without_last = n // 10 # 123 (число без последней цифры) first_digit = n // 1000 # 1 (первая цифра — если число 4-значное) # Сумма цифр def digit_sum(n): s = 0 while n > 0: s += n % 10 n //= 10 return s ``` --- ## 7. Типичные ошибки - **Перепутать `//` и `/`.** В Python 3 оба работают, но дают разный результат: `7/2 = 3.5`, `7//2 = 3`. - **Неверное базовое условие рекурсии.** Если забыть base case — бесконечная рекурсия и ошибка. - **Не обновить переменную в цикле.** Если `x` не изменяется — бесконечный цикл. - **Перепутать `=` и `==`.** В условии всегда `==`, в присваивании `=`. - **Неверная граница range.** `range(1, 10)` — числа от 1 до 9 (10 не входит!). --- ## 8. Лайфхаки для ОГЭ > **Совет:** При трассировке сложного алгоритма нарисуйте таблицу: строки — итерации, столбцы — переменные. Обновляйте каждую ячейку. > **Совет:** Если в задаче просят "наибольшее X, при котором вывод равен Y" — попробуйте запустить код в голове для нескольких значений рядом с граничным. > **Совет:** Рекурсию удобно считать "снизу вверх": сначала вычислите F(1), потом F(2), F(3)... до нужного значения. > **Совет:** Если на экзамене есть компьютер — вы можете запустить Python и проверить свой ответ! Это официально разрешено для задач 15 и 16.