3. На самом деле, алгоритмом Евклида чаще называют "ускоренную" версию описанного нами ранее алгоритма: на каждом шаге вместо большего из двух чисел записывается меньшее, а вместо меньшего - остаток от деления большего на меньшее. Так продолжается, пока одно из чисел не поделится нацело на другое (то есть, пока остаток не равен нулю). Последний ненулевой остаток является наибольшим общим делителем (НОД) исходных чисел a и b. Пример: пара (16; 6) превращается в (6; 4), потом в (4,2). 4 делится на 2, поэтому НОД(10; 6) = 2. Докажите, что этот алгоритм Евклида работает не хуже, чем предыдущий.

vikapataeva    1   12.08.2020 05:38    0