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