Номер LCM и GCD 3 - Python

Это мой код до сих пор.

from math import gcd

#3 digit lcm calculation
h=input("(1) 2 Digit LCM Or \n(2) 3 Digit LCM\n :")
if h == "2":
    while True:
        def lcm(x, y, z):
            a = gcd(x, y, z)
            num = x
            num2 = y * z // a
            LCM = num * num2 // a

            return LCM

        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        z = int(input("Number 3: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " And " + str(z) +         " Is " + str(lcm(x, y, z)))

if h == "1":
    while True:
        def lcm(x, y):
            a = gcd(x, y)
            num = x
            num2 = y
            LCM = num * num2 // a

            return LCM
        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " Is " + str(lcm(x, y)))

Моя проблема в том, что 3 цифры просто находят общее кратное, а не самое низкое, например, 10, 5, 8 составляют 400 вместо возможных 40. Любая помощь будет полезна!

Новый код благодаря обрезке

from math import gcd

#3 digit lcm calculation
h=input("(1) 2 Digit LCM Or \n(2) 3 Digit LCM\n :")
if h == "2":
    while True:
        def lcm(x, y, z):
            gcd2 = gcd(y, z)
            gcd3 = gcd(x, gcd2)

            lcm2 = y*z // gcd2
            lcm3 = x*lcm2 // gcd(x, lcm2)
            return lcm3

        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        z = int(input("Number 3: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " And " + str(z) + " Is " + str(lcm(x, y, z)))

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

Источник

1 ответ

Решение

АНАЛИЗ

Как вы только что обнаружили (но еще не осознали), отношение, которое выполняется для пар целых чисел:

x * y = GCD (x, y) * LCM (x, y)

не держится для троек. Основная логика для простой факторизации состоит в том, что GCD берет минимальный показатель степени для каждого простого фактора; ЖК-дисплей принимает максимальный показатель. Имея только два целых числа, это означает, что каждый показатель степени используется ровно один раз, что позволяет выполнить приведенное выше уравнение.

Однако с тремя целыми числами вы гарантируете, что средний показатель для каждого простого множителя будет исключен из вычислений LCM и GCD.

 10 = 2^1 * 3^0 * 5^1
  8 = 2^3 * 3^0 * 5^0
  5 = 2^0 * 3^0 * 5^1
----------------------
GCD = 2^0 * 3^0 * 5^0
LCM = 2^3 * 3^0 * 5^1

Обратите внимание на исключенные факторы: 2 ^ 1 * 3 ^ 0 * 5 ^ 1 = 10, поэтому ваши вычисления LCM высоки в 10 раз.

РЕШЕНИЕ

Вам нужно разделить логику, когда вы используете третье целое число, что-то вроде этого:

# Find the 2-number and 3-number GCDs
gcd2 = gcd(y, z)
gcd3 = gcd(x, gcd2)

# Find the 2-number and 3-number LCMs
lcm2 = y*z // gcd2
lcm3 = x*lcm2 // gcd(x, lcm2)

return lcm3
Источник

Чтобы вычислить НОД более двух чисел, вы можете сделать это следующим образом:

Например: НОД для a, b, c, d

  1. gcd (a, b) = x
  2. gcd (x, c) = y
  3. gcd (y, d) = z

А чтобы вычислить НОК более двух чисел, вы можете сделать это следующим образом:

Например: НОК a, b, c, d

  1. a * b // gcd (a, b) = x
  2. x * c // gcd (x, c) = y
  3. y * d // gcd (y, d) = z

*Оператор двойного слэша (//) для деления "пола" (округление до ближайшего целого числа).

GCD в Python 3:

Итак, сначала мы могли бы сделать это с помощью следующего простого whileитерация и использование функции gcd() из математического модуля следующим образом:

from math import gcd

def gcd_n(*args):
    i = 1
    x = args[0]

    while i < len(args):
        x = gcd(x, args[i])
        i += 1
    return x

Это также можно сделать немного проще с помощью лямбда- функции и функции reduce() из модуля functools следующим образом:

from math import gcd
from functools import reduce

def gcd_n(*args):
    f = lambda a,b:gcd(a,b)
    return reduce(lambda x,y:f(x,y),args)

Но если вы думаете, что это невозможно сделать проще... ДА, это можно сделать еще проще:

from math import gcd
from functools import reduce

def gcd_n(*args):
    return reduce(gcd, args)

В любом случае возврат одинаков. С помощью этих простых функций вы можете вычислить НОД всех желаемых чисел, независимо от того, являются ли они числами 2, 3, 4 или N.

>>> gcd_n(3355, 985)
5
>>> gcd_n(3465, 6615, 7875)
315
>>> gcd_n(6930, 13230, 15760)
10
>>> gcd_n(1750, 1960, 3080)
70
>>> gcd_n(85, 96, 100, 225)
1

LCM в Python 3:

Следуя той же философии, что и в простейшем примере выше, для вычисления НОК двух или более чисел достаточно этих двух функций:

from math import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_n(*args):
    return reduce(lcm, args)

Вот вам образец серии тестов:

>>> lcm_n(77, 9)
693
>>> lcm_n(5, 10, 15)
30
>>> lcm_n(62, 89, 13)
71734
>>> lcm_n(21, 4, 17, 2)
1428

Надеюсь, это поможет, у меня это хорошо работает.

Источник
Другие вопросы по тегам