Двоичный поиск по массиву и по ответу, решето Эратосфена, целочисленный квадратный корень — тест для 9 класса

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

Что проверяется

Двоичный поиск в упорядоченном массиве: границы, середина, условие продолжения, поиск первого элемента не меньше заданного. Двоичный поиск по ответу: монотонность проверки «подходит ли значение», число шагов на большом диапазоне. Решето Эратосфена: с какого числа вычёркивать кратные и до какого p продолжать. Простые и составные числа, перебор делителей до квадратного корня. НОД и НОК. Целочисленный квадратный корень math.isqrt и его вычисление.

Задания

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

Разбор

Пояснения показывают, почему вычёркивание начинают с p², почему для диапазона до миллиарда достаточно тридцати проверок, почему round(n ** 0.5) даёт неверную целую часть корня и как бинарный поиск находит первое вхождение среди повторяющихся значений.

Назначение

Работа рассчитана на первые восемь часов 9 класса и полезна при подготовке к олимпиадам и ОГЭ по информатике, где задачи на делители, простые числа и поиск по ответу встречаются постоянно. Девятый класс завершает трёхлетний курс «Программирование» ИТ-вертикали: тридцать четыре часа на Python, посвящённые структурам данных и классическим алгоритмам. Это материал, с которого начинаются олимпиадная информатика и профильные ИТ-классы, куда поступает большинство выпускников вертикали. Эта работа — первая из 5 по курсу.

Условия прохождения

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