0

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

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

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

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

10

1 ответ 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)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.