Нахождение НОД нескольких чисел на Python

Question

Нахождение НОД нескольких чисел на Python

Рейтинг: 0Ответов: 2Опубликовано: 12.02.2023

Всем привет! Занимаюсь изучением языка Python. Никак не могу решить задачу с академии яндекса по нахождению НОДа нескольких чисел :(. Задача из раздела "Вложенные Циклы". Суть заключается в следующем:

"В одном из местных НИИ часто требуется находить наибольший общий делитель (НОД) нескольких чисел. Вам уже доверяют, так что вновь пришли с этой задачей. Формат ввода В первой строке записано одно число NN — количество данных. В каждой из последующих NN строк записано по одному натуральному числу. Формат вывода Требуется вывести одно натуральное число — НОД всех данных чисел (кроме NN)"

Но, решить надо, как я понял, без использования списков, словарей, готовых функций (типа math.gcd()) и т.д., т.к. тема вложенные циклы идет после тем: Ввод и вывод данных. Операции с числами, строками. Форматирование Условный оператор Циклы. Т.е. предполагается, что я владею только перечисленными выше темами.

Даже не знаю с какой стороны подойти. Конечно, можно использовать уже готовую функцию math.gcd(), но очень хочется понять алгоритм решения. Спасибо всем откликнувшимся ☻

python

Источник: Stack Overflow на русском

Answer 1

▲ 1

В общем, получилось все-таки решить без использования функций и готовых решений...

n = int(input())  # вводим сколько будет чисел
second_number = 0  # второе число для расчета НОДа на первом цикле

for i in range(1, n + 1):
    first_number = int(input())
    # Ищем НОД по алгоритму Евклида (делением)
    while first_number != 0 and second_number != 0:
        if first_number > second_number:
            first_number %= second_number
        else:
            second_number %= first_number
    # Перезаписываем вторую переменную num2 НОДом.
    # На следующем цикле будем искать НОД нового введенного числа и полученного НОД
    second_number += first_number

print(second_number)

Либо можно с функциями...

 from functools import reduce


 def gcd_multiple(num1, num2):
     '''
     Функция считает НОД num1 и num2 по Алгоритму Евклида (делением)

     Параметры:
         num1 - первое число
         num2 - второе число

     Return:
         НОД чисел num1 и num2
     '''

     while num1 != 0 and num2 != 0:
         if num1 > num2:
             num1 %= num2
         else:
             num2 %= num1
     return num1 + num2


 n = int(input())  # вводим сколько будет чисел
 list_num = []  # в этот список будем добавлять числа, введенные пользователем
 count_num = 0  # счетчик для выхода из цикла, когда закончатся числа

 for i in range(n):
     num = int(input())
     list_num.append(num)
     while count_num < len(list_num):
         gcd_multiple_result = reduce(gcd_multiple, list_num)
         count_num += 1

 print(gcd_multiple_result)

Answer 2

▲ 0

Короче будет

from math import gcd
from functools import reduce

print(reduce(gcd, [int(input()) for _ in range(int(input()))]))

Нахождение НОД нескольких чисел на Python

Ответы