Привет, ребятки! Сегодняшняя заметка будет состоять из разбор 6 задач уровня 9 класса (ОГЭ). Задачки можно решить аналитически, но мы попробуем их закодить, решить методом перебора. Все эти задачи будут полезны учащимся средней школы для тренировки навыков программирования. Реализация примеров выполнена с помощью Python.
Задача 1
У исполнителя Альфа две команды. которым присвоены номера:
1. Вычти b;
2. Умножь на 5.
(b — неизвестное натуральное число).
Выполняя первую из них, Альфа уменьшает число на экране на b, а выполняя вторую, умножает это число на 5. Программа для исполнителя Альфа — это последовательность номеров команд. Известно, что программа 21121 переводит число 2 в число 17. Определите значение b.
Решение:
Всегда с учениками решали эту задачу аналитически (так вроде быстрее). Но на последнем занятии я подумал, а если алгоритм будет сложный, можно ли написать что-то универсальное? Например, программу, которую можно будет масштабировать до любого количества инструкций любой сложности... И вот пришла такая идея:
Такой вот брутфорс получился. Если программа исполнителя состоят из большого количества инструкций, то, возможно, написать код будет быстрее, чем считать аналитически. Ну и в любом случае это полезно для тренировки навыков написания программ.
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов.
Изначально для решения этой задачи (5 тип задач из ОГЭ по информатике) была написана вот такая программа:
Но мне не понравилась сильная вложенность функций и отсутствие возможности масштабировать код.
Задача 2
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Решение:
Если расписать хотя бы один пример работы алгоритма, то аналитически задача решается нетрудно. Попытаюсь расписать кратко, но подробно:
Но если в нашем инструментарии есть Python, то расчёты можно упростить.
Давайте так... Да, программу можно написать и в одну-две строчки, но читабельность такой программы будет очень низкая для учащихся 8-11 классов, у которых возникают сложности с алгоритмизацией и программированием. Но я всё же приведу пример:
Задача 3 * (измененная версия предыдущей задачи)
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Решение:
Эту задачу можно решить аналитически, но придется напрячь мозг, догадаться до некоторых тонкостей и подвохов.
Стоит заметить очень интересный факт: количество остатков зависит только от конечного числа в диапазоне от 10 до 1000. Для диапазона от 65 до 1000 будет такой же результат. Почему? Это будет происходить до тех пор, пока в диапазоне будет находиться хотя бы одна степень двойки. В двоичной системе степень двойки всегда представлена «1», стоящей на определенном k-м месте и некоторым количество нулей «0» (последовательностью из k нулей). Поэтому, обрезая самую левую единицу «1», мы получаем 0 в качестве результата работы алгоритма. Значит более всего результат зависит от конца диапазона (в нашем случае от 1000), чем от начала.
И всё-таки закодить эту задачу будет проще по умственным затратам:
Задача 4 (тип 15.2)
Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, оканчивающееся на 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 4. Количество чисел не превышает 1000. Введенные числа не превышают 30 000. Программа должна вывести одно число — минимальное число, оканчивающееся на 4.
Решение:
Здесь уже аналитическое решение не подразумевается. Но почему-то эта задача стоит (на момент написания статьи) самой сложной из 15.2 в ОГЭ по информатике. Накидаем алгоритм решения на словах:
1. Ввести количество чисел и сохранить их в какой-нибудь переменной, которую можем назвать как хотим (например N, count, k).
2. Нужно запустить цикл и продумать условия выхода из цикла (чтобы он не был бесконечный). Ориентироваться мы можем на количество чисел (когда в условии просят ввести количество изначально), либо можно ориентироваться на ввод определенного терминального числа (признак конца ввода), например "О".
3. До цикла нужна начальная инициализация минимума (min_4). Данная переменная должна обновляться, значит в начале она должна принимать значение БОЛЬШОЕ, ЧТОБЫ ТОЧНО ОБНОВИТЬСЯ. Допустим min_4 = 30000.
4. Допустим, выбран цикл for...in... Внутри цикла мы должны считывать текущее число в какую-нибудь переменную (например current_number, num, х,...). Затем нужно сразу же исследовать это число (потому что на следующем шаге мы затрем это число другим введенным). Если число подходит (оканчивается на "4" и меньше предыдущего подходящего), то мы обновляем наш минимум. Обновиться (если current_number подходит) означает присвоить current_number в текущее значения минимума, оканчивающегося на 4.
(сделать min_4 = current_number в теле условного оператора if)
5. Вывод минимального числа, оканчивающегося на 4.
Теперь реализация данного алгоритма на Python:
Задача 5
Ниже приведена программа, записанная на пяти языках программирования.
Было проведено 9 запусков программы, при которых в качестве значений переменных s и k вводились следующие пары чисел:
(1, 2); (8, 4); (6, −12); (−5, −5); (3, 11); (−10, 12); (−10, −2); (4, 1); (2, 5).
Сколько было запусков, при которых программа напечатала «ДА»?
Решение:
На мой взгляд, эту задачу тоже легче сделать устно, но если у вас будет много времени на экзамене, то можно и запрограммировать решение. По сути, код задачу нужно обернуть в цикл, а входные данные в список из кортежей (пар).
Задача 6 (тип 10, математика ОГЭ)
Коля выбирает трехзначное число. Найдите вероятность того, что оно делится на 5.
Решение:
Задача не очень сложная, но чисел уже довольно много, а это значит, что нужно подумать логически. Трехзначные числа ∈ [100, 999]. Их количество будет n = 999 - 100 + 1 = 900. Каждое пятое делится на 5, начиная со 100. Количество чисел, кратных 5, будет определяться как m = 900/5 = 180. Тогда вероятность того, что Коля выберет число, кратное 5, будет равна p = m/n = 180/900 = 0.2.
Понравилась статья? Поставьте лайк, подпишитесь на канал, напишите комментарий! Вам не сложно, а мне очень приятно :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Лучший канал для физиков, математиков и программистов
Репетитор IT mentor в telegram