В
Все
М
Математика
А
Английский язык
Х
Химия
Э
Экономика
П
Право
И
Информатика
У
Українська мова
Қ
Қазақ тiлi
О
ОБЖ
Н
Немецкий язык
Б
Беларуская мова
У
Українська література
М
Музыка
П
Психология
А
Алгебра
Л
Литература
Б
Биология
М
МХК
О
Окружающий мир
О
Обществознание
И
История
Г
Геометрия
Ф
Французский язык
Ф
Физика
Д
Другие предметы
Р
Русский язык
Г
География
aliska561
aliska561
19.02.2023 00:56 •  Информатика

Как можно найти НОД двух натуральных чисел не используя алгоритм евклида? какой метод лучше? Сравните этот алгоритм с алгоритмом евклида. ​

Показать ответ
Ответ:
lenaguceva
lenaguceva
25.04.2021 11:40

для нахождения НОДа не мало, не буду углубляться во всякие сложные алгоритмы, так как вряд ли Вы их проходите.

Сравним перебор и алгоритм Евклида, сразу можем сказать, что алгоритм Евклида в разы быстрее, так как при переборе мы тупо перебираем значения, то есть, данный алгоритм зависит от величины числа очень сильно. Конечно, алгоритм Евклида также зависит от введенного числа, однако, в нём будет намного меньше повторений, нежели в с перебором.

Можем глянуть немного статистики:

Генерируется 500 пар чисел

Перебор - 0.5022 с

Алгоритм Евклида - 0.0008

Теперь мы точно можем сделать вывод, что алгоритм Евклида в разы быстрее простого перебора.

0,0(0 оценок)
Ответ:
Цωετοζεκ
Цωετοζεκ
25.04.2021 11:40

Відповідь:

#НОД чисел 45 и 105

a = 45;

b = 105;

result = False;

if (a > b):

   big = a;

else:

   big = b;

   

i = 2;

while (i <= big):

   if ((a % i == 0) and (b % i == 0)):

       result = i;

   i += 1;

print (result);

Пояснення:

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота