Бумажные ленты надо разрезать на одинаковые целые длины. Ищем наибольшую допустимую длину, поэтому направление границ отличается от поиска минимального времени.
Учителю: подготовка и план на 45 минут
Подготовьте компьютер, редактор, папку с правом записи, распечатку ученической части PDF, бумагу и ручку. Компилятор G++ с поддержкой C++17 и редактор. Сборка: g++ -std=c++17 -Wall -Wextra -pedantic main.cpp -o lesson. Запуск ./lesson в Linux/macOS или .\lesson.exe в Windows (при сборке задайте -o lesson.exe). Установку и проверку запуска учитель выполняет заранее. Все программы, данные и ожидаемые ответы даны; регистрация детей и интернет на занятии не нужны.
Уровень — начинающий программист, 9 класс. Предпосылки: long long, функция-предикат, границы двоичного поиска. В паре автор прогнозирует и вводит код, проверяющий ведёт журнал, затем роли меняются. Без компьютера выполните трассировку полного кода на бумаге и сопоставьте с готовыми результатами; учитель демонстрирует подготовленный запуск. Бумажный вариант не считается фактическим запуском ученика. Перед практикой учитель выдаёт готовый файл разобранного примера, чтобы дети тратили время на изменение и проверку, а не длинное перепечатывание. Матрица программы предназначена учителю.
| Минуты | Работа | Результат |
|---|---|---|
| 0–5 | Проблема | Вопрос и первое решение |
| 5–14 | Понятия и пример | Способ проверки |
| 14–25 | Практика 1 | Готовый продукт и проверка |
| 25–33 | Практика 2 | Перенос способа |
| 33–40 | Обсуждение | Аргумент и ограничение |
| 40–45 | Индивидуальная проверка | Самостоятельный ответ |
01. Проблемная ситуация
0–5 минут. Есть ленты длиной 8,5,8 см. Нужно не менее 5 кусков одинаковой целой длины; обрезки соединять нельзя, шириной разреза пренебрегаем. Проверьте длины 3 и 4 см.
02. Понятия и разобранный пример
5–14 минут: 4 минуты на понятия, 3 на пример, 2 на объяснение способа партнёру.
Последняя истина вместо первой
При длине d>0 лента L даёт L/d целых кусков, где / для положительных целых в C++ отбрасывает дробную часть. Число кусков не возрастает при увеличении d. Поэтому условие «кусков не меньше k» истинно слева и ложно справа; ищем последнюю истину.
Контракт: 0…100 лент, длина каждой 0…1000000 см, заказ 1…1000000 кусков. Для невозможного заказа возвращаем 0 как сигнал, а не длину реального куска. lo=0 — условная граница, делить на неё нельзя; hi=max(L)+1 заведомо невозможно. Середина в цикле положительна.
Сохраняем допустимую lo и недопустимую hi, проверяем только положительную середину. При hi-lo=1 ответ lo. long long хранит сумму числа кусков и вычисления; ограничения явно ограничивают их размер. Пустой набор и все нулевые длины дают 0 без деления.
Отступы набирайте обычными пробелами: 4 на уровень. При копировании с веб-страницы замените неразрывные пробелы обычными; полный код с обычными пробелами есть в PDF.
8,5,8; k=5: lo=0,hi=9. d=4 даёт 2+1+2=5, lo=4; d=6 даёт 1+0+1=2, hi=6; d=5 даёт 1+1+1=3, hi=5. Ответ 4 см. В отличие от урока 27 выбираем последний подходящий размер.
| #include <iostream> #include <vector> #include <algorithm> using namespace std; long long best(const vector<long long>& a, long long k) { long long lo=0, hi=1; for (long long x:a) hi=max(hi,x+1); while (hi-lo>1) { long long d=lo+(hi-lo)/2, count=0; for (long long x:a) count+=x/d; if (count>=k) lo=d; else hi=d; } return lo; } int main() { vector<long long> a={8,5,8}; cout << best(a,5); } |
03. Практика 1. Проверяем материал
Проверяем крайние случаи
14–25 минут. Проверку контракта выполняйте до вызова: k положительно, длины неотрицательны и в заданных пределах.
| Ленты; k | Назначение теста |
|---|---|
| [8,5,8]; 5 | Обычный заказ |
| [4]; 2 | Одна лента |
| [1,1]; 3 | Невозможный заказ |
| []; 1 и [0,0]; 1 | Нет материала |
| [1000000]; 1 | Максимальная длина |
2 минуты — прогноз, 4 — шесть запусков, 3 — проверка T и T+1 для положительных результатов, 2 — журнал. Критерии: правильный максимум, нет деления на ноль, сигнал невозможности отличён от реального куска.
Практика 1: разбор и критерии
Ответы: 4,2,0,0,0,1000000. Для [4],k=2 длина 2 даёт 2 куска, длина 3 только 1. Для [1,1],k=3 даже длина 1 даёт лишь 2; 0 обозначает невозможность. Отрицательные длины и k=0 за пределами контракта.
04. Практика 2. Перенос способа
Учитываем ширину разреза
25–33 минуты. В новой модели каждая заготовка требует d см полезного материала и ещё 1 см расхода, в том числе последняя. Для лент [8,5,8] нужно 5 заготовок. За 2 минуты запишите счётчик, за 4 измените копию кода, за 2 объясните границу и единицы.
Практика 2: разбор и критерии
Замените count+=x/d на count+=x/(d+1). Ответ 3 см: при d=3 получается 2+1+2=5, при d=4 — 1+1+1=3. Это специально заданная модель расхода на каждую заготовку, не универсальная формула пиления. Предикат остаётся невозрастающим, прежняя hi достаточна.
05. Обсуждение и границы вывода
33–40 минут. Ученик предлагает сначала просуммировать длины и поделить на k. За 2 минуты проверьте [2,2],k=1, за 3 объясните роль запрета соединения, за 2 сравните верхнюю оценку с достижимым ответом.
Обсуждение: возможный вывод
Сумма/k=4 см, но ни одна лента не даёт куска 4 см; максимум 2. Общая длина даёт только верхнюю оценку, если части нельзя соединять. Для корректного решения проверяем каждую ленту отдельно.
06. Индивидуальная проверка
40–45 минут. В исходной модели [9,7],k=4 найдите T, количества при T и T+1, объясните, почему lo=0 не делитель. Четыре балла.
Индивидуальная проверка: ответ и критерии
T=3; при 3: 3+2=5, при 4: 2+1=3. Ноль — сигнал и условная граница; цикл делит только на положительную середину. По баллу за каждый пункт.
07. Соответствие исходной программе
Пункт программы → действие → результат
| Пункт программы | Действие ученика | Проверяемый результат |
|---|---|---|
| Алгоритмы поиска | Проверяем крайние случаи | Найти максимальную целую длину заготовки и доказать достаточность ответа и невозможность следующего значения. |
| Самостоятельная проверка результата | Учитываем ширину разреза | Обоснованный ответ и исправление ошибки |
Источники и права на изображения
Тексты, учебные данные, реплики, программы и схемы подготовлены для уроков портала «Школы России». Числовые серии — учебные модели, не результаты проведённых классом опытов. Схемы авторские, сторонние фотографии не используются. Методические ссылки приведены для учителя; ученик получает все материалы здесь. Проверка первичных источников: 18.10.2026.