Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает С ОБЪЯСНЕНИЕМ
В цикле описан алгоритм Евклида: пока числа не равны, из большего вычитается меньшее. Известно, что в результате работы алгоритма Евклида получается наибольший общий делитель двух чисел.
Здесь ищется НОД чисел L = x - 18 и M = x + 36, и должно получиться 9. Если x - 18 делится на 9, то и x делится на 9. Наименьшее число, большее 100 и делящееся на 9, - это 108.
117
Объяснение:
В цикле описан алгоритм Евклида: пока числа не равны, из большего вычитается меньшее. Известно, что в результате работы алгоритма Евклида получается наибольший общий делитель двух чисел.
Здесь ищется НОД чисел L = x - 18 и M = x + 36, и должно получиться 9. Если x - 18 делится на 9, то и x делится на 9. Наименьшее число, большее 100 и делящееся на 9, - это 108.
Проверяем:
L = 108 - 18 = 90 = 5 * 18
M = 108 + 36 = 144 = 8 * 18
Нехорошо, НОД равен 18, а не 9.
Берём следующее делящееся на 9 число, x = 117:
L = 117 - 18 = 99 = 11 * 9
M = 117 + 36 = 153 = 17 * 9
Подходит, НОД(L, M) = 9