2

这是我的代码：

def lcm(a, b):
    if b == 0:
        return a
    return a * b / lcm(a, b)

print lcm(5,3)

到目前为止，这是我可以管理的，关于如何使用递归和一个函数找到两个数字的 LCM（最小公倍数）的任何想法？

4

6 回答 6

2

我们有lcm(a, b) * gcd(a, b) = a * b. 所以我们可以写出如下等式：

lcm(a, b) = a; 如果 a % b == 0

lcm(a, b) ; 如果 a % b != 0
= a * b / gcd(a, b)
= a * b / gcd(b, a % b)
= a * b / (b * (a % b) / lcm(b, a % b))
= a / (a % b) * lcm(b, a % b)

翻译成 Python，我们有：

def lcm(a, b):
  t = a % b
  if t == 0: return a
  return a * lcm(b, t) / t
于 2018-11-02T05:50:51.683 回答
1

编辑：我没有阅读您问题中的递归/一个函数位，因为我很愚蠢。现已纳入。

lcm 不是a * b / lcm(a, b)，它是a * b / gcd(a, b)（最大公约数）。

所以最干净的方法是：

def gcd(x, y):
    while y:      
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y / gcd(x, y)

如果您仅限于递归（例如对于考试），那么这不一定是有效的，所以您不妨递归地计数，直到找到 x 和 y 都分为的最低数字：

def lcm(x, y, counter=1):
    if (counter%x == 0 and counter%y == 0):
        return counter
    return lcm(x, y, counter+1)

这只会增加计数器，直到counter%x == 0 and counter%y == 0为真，即 LCM。但是不要在大数上尝试它，你只会得到堆栈溢出。

于 2015-09-22T23:25:01.217 回答
1

使用两个数的乘积等于这两个数的最大公约数和最小公乘数的乘积的数学关系：A * B = GCD(A,B) * LCM(A,B)

def gcd(a,b):
    if a % b == 0: return b
    return gcd(b, a % b)

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

第一个函数是递归的，它用于找到最大公约数，它的成本为 O(log(n))。

于 2019-07-11T15:40:10.053 回答
1

如此处其他答案所述，lcm = a*b / gcd(a, b)但您将需要gcd(a, b)为它定义另一个函数。

由于您只需要一个递归函数，也许这段代码就可以了。

注意：这个函数有一个额外的参数c，当只在函数外调用它时，它应该始终作为 1 传递：

def lcm(a, b, c):
d = c
m = min(a, b)
while m > 1 :
    if a%m == 0 and b%m == 0 :
        d*=m 
        return lcm(int(a/m), int(b/m), d)
    else:
        m-= 1
d*= a*b
return d
于 2018-04-07T21:18:21.007 回答
0

这应该这样做：

# Python Program to find the L.C.M. of two input number

# define a function
def lcm(x, y):
   """This function takes two
   integers and returns the L.C.M."""

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while True:
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm


# take input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

print("The L.C.M. of", num1,"and", num2,"is", lcm(num1, num2))
于 2015-09-22T23:17:11.273 回答
0

我创建了自己的简单程序。

def lcm(greater,a,b):
# while(True):
    if (greater % a == 0 and greater % b == 0):
        lcm1 = greater
        return lcm1
    else:

        lcm1=lcm(greater + 1,a,b)
        return lcm1
a=int(input(" Enter 1st number :"))
b=int(input(" Enter 2nd number :"))
if(a>b):
  greater=a
else:
  greater=b

print(lcm(greater,a,b))
于 2018-09-19T13:34:11.887 回答