Присоединиться

9–11 класс·базовый уровень

Алгоритм Евклида: найдите НОД(1071, 462) и число квадратов из листа картона

Условие

Прямоугольный лист картона имеет размеры 1071 мм × 462 мм. Его требуется разрезать без остатка на одинаковые квадраты наибольшего возможного размера, причём стороны квадратов параллельны сторонам листа. Пользуясь алгоритмом Евклида, найдите сторону такого квадрата в миллиметрах и определите, сколько всего квадратов получится.

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

Решение по шагам

  1. Шаг 1. Переводим задачу на язык делимости

    Пусть сторона квадрата равна aa мм. Чтобы вдоль длинной стороны уместилось целое число квадратов, нужно, чтобы 10711071 делилось на aa без остатка. Аналогично по короткой стороне: 462462 должно делиться на aa.

    Значит, aa — общий делитель чисел 1071 и 462. Квадраты нужны наибольшие, поэтому

    a=НОД(1071, 462).a = \text{НОД}(1071,\ 462).

    Искать НОД перебором делителей до 462 долго — здесь и нужен алгоритм Евклида.

  2. Шаг 2. Первый шаг алгоритма Евклида

    Алгоритм Евклида в варианте с остатками опирается на свойство

    НОД(a, b)=НОД(b, a mod b),b≠0.\text{НОД}(a,\ b) = \text{НОД}(b,\ a \bmod b), \qquad b \neq 0.

    Большее число заменяется остатком от деления, пара «уменьшается», а НОД при этом не меняется.

    Делим с остатком: 1071=2⋅462+1471071 = 2 \cdot 462 + 147, то есть 1071 mod 462=1471071 \bmod 462 = 147.

    Следовательно, НОД(1071, 462)=НОД(462, 147)\text{НОД}(1071,\ 462) = \text{НОД}(462,\ 147). Задача уже стала меньше — повторяем то же действие.

Осталось ещё 2 шага

  1. Шаг 3. Доводим алгоритм до нулевого остатка

  2. Шаг 4. Считаем количество квадратов и проверяем ответ

Получить полное решение

Бесплатно · займёт минуту

Частые ошибки

  • Берут НОК вместо НОД: 21 — наибольший общий делитель, а не наименьшее общее кратное (которое здесь равно 23 562).

  • Останавливают алгоритм на нулевом остатке и записывают в ответ сам ноль вместо последнего ненулевого остатка 21.

  • Переносят в следующую строку частное вместо остатка: после 1071=2⋅462+1471071 = 2 \cdot 462 + 147 переходят к паре (462, 2)(462,\ 2), а не к правильной паре (462, 147)(462,\ 147).

  • Складывают 51 и 22 вместо умножения — получают 73 «квадрата», хотя резать надо в двух направлениях.

  • Пробуют «на глаз» сторону 7 мм или 3 мм: делить будет без остатка, но квадраты не наибольшие.

Другие задачи по теме «Алгоритмы и программирование»