Представьте прямоугольник 252 × 105 см. Какими самыми большими одинаковыми квадратными плитками можно покрыть его без обрезки? Сторона плитки должна делить оба размера без остатка — это и есть наибольший общий делитель (НОД).
Алгоритм Евклида находит его простым повторением: заменяем первое число вторым, а второе — остатком от деления первого на второе.
(252, 105) → (105, 42) → (42, 21) → (21, 0)
Когда второе число стало нулём, первое — ответ.
Здесь НОД = 21, значит, подойдут плитки 21 × 21 см.
Меняйте A и B в полях ввода, и смотрите на результат работы алгоритма.
НОД используют, например, для сокращения дробей. А сам алгоритм учит важному приёму программирования: упрощать задачу, сохраняя её ответ.
| Oberon & OberonJSSource code | Result |
|
|