Выберите серию
\textbf{Алгоритм Евклида} — это эффективный алгоритм для нахождения \textbf{наибольшего общего делителя (НОД)} двух натуральных чисел.
Основная идея алгоритма содержится в следующем математическом свойстве
\[
\text{НОД}(a, b) = \text{НОД}(b, r)
\]
где $r$~--- остаток от деления $a$ на $b$.
Таким образом, алгоритм состоит из двух шагов:
1) для пары чисел $a\geq b$ если $b\neq 0$ находится остаток $r$ от деления $a$ на $b$;
2) пара $a\geq b$ меняется на пару $b\geq r$.
Процесс повторяется до тех пор, пока остаток не станет равен нулю. Последний ненулевой остаток и будет искомым НОД.
Пример работы.
Найдем $\text{НОД}(1071, 462)$:
\begin{align*}
1071 &= 462 \times 2 + 147 \\
462 &= 147 \times 3 + 21 \\
147 &= 21 \times 7 + 0 \\
\end{align*}
Последний ненулевой остаток~--- 21. Следовательно
\[
\text{НОД}(1071, 462) = 21.
\]
Ответ:
Варианты ответов:
У Кирилла есть клетчатый лист бумаги $6\times 39$ клеточек. 6 по вертикали, 39 по горизонтали. За один ход Кирилл вертикальным разрезом отрезает от своего листа $a\times b$, где $a<b$ квадрат со стороной $a$. Он повторяет ходы, пока у него не останется прямоугольник, у которого вертикальная сторона больше горизонтальной, или квадрат. В первом случае Кирилл поворачивает прямоугольник и продолжает ходы. Во втором заканчивает игру. Квадрат с какой стороной останется у Кирилла в конце?
Ответ:
Варианты ответов:
У Кирилла есть клетчатый лист бумаги $6\times 39$ клеточек. 6 по вертикали, 39 по горизонтали. За один ход Кирилл вертикальным разрезом отрезает от своего листа $a\times b$, где $a<b$ квадрат со стороной $a$. Он повторяет ходы, пока у него не останется прямоугольник, у которого вертикальная сторона больше горизонтальной, или квадрат. В первом случае Кирилл поворачивает прямоугольник и продолжает ходы. Во втором заканчивает игру. Сколько ходов сделает Кирилл до тех пор, пока первый раз не перевернет прямоугольник?
Ответ:
Варианты ответов:
Найдите наибольший общий делитель чисел 111\ldots1 (120 единиц) и 111\ldots1 (378 единиц).
Ответ:
Варианты ответов:
Найдите наибольший общий делитель чисел 6 и 39.
Ответ:
Варианты ответов: