Question

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

Answer 1

Программа:

from math import gcd, lcm

n, a = int(input()), []

while n != 0:

   a += [n]

   n = int(input())

print(f'НОД: {gcd(*a)}\nНОК: {lcm(*a)}')

Answer 2

Для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) для чисел в последовательности, введенной с нулем в качестве признака конца, можно использовать алгоритм Евклида и формулу НОК. Алгоритм Евклида позволяет эффективно находить НОД двух чисел, а затем можно использовать формулу для вычисления НОК на основе НОД и самих чисел.

Вот подробные шаги для решения этой задачи:

1. Инициализация переменных: - `gcd` (НОД) начинается с первого числа в последовательности. - `lcm` (НОК) начинается с первого числа в последовательности.

2. Чтение чисел из последовательности до тех пор, пока не встретится ноль (признак конца).

3. Для каждого числа в последовательности: - Найдите НОД текущего числа и `gcd` с использованием алгоритма Евклида. Обновите значение `gcd` этим НОДом. - Найдите НОК текущего числа и `lcm` с использованием формулы: `lcm = lcm * число / НОД(число, lcm)`.

4. После завершения обработки всех чисел в последовательности, `gcd` будет содержать НОД всех чисел, а `lcm` - НОК всех чисел.

5. Выведите полученные значения НОД и НОК.

Этот алгоритм эффективен, так как он использует алгоритм Евклида для нахождения НОДа и обновляет НОК на основе текущего числа и НОК, что минимизирует количество вычислений.

Пример (псевдокод):

gcd = первое число
lcm = первое число

Пока (ввод ≠ 0):
    число = следующее введенное число
    gcd = НОД(gcd, число)
    lcm = lcm * число / НОД(число, lcm)

Вывести "Наибольший общий делитель: " + gcd
Вывести "Наименьшее общее кратное: " + lcm

Этот алгоритм обеспечивает эффективное вычисление НОДа и НОКа для любой последовательности натуральных чисел без дополнительных затрат по времени или памяти.