Am wenigsten häufiges Vielfaches von n Zahlen, unter Verwendung der Rekursion

Question

Ich muss eine rekursive Funktion schreiben, die die wenigsten gemeinsamen Mehrfachelemente der Liste mit n Länge findet. Mein Code:

import random 

def random_num(n): 
    return [random.randint(-20,20) for i in range(n)] 

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

def my_nok(n,m): 
    return (n/gcd(n,m))*m 

Das erste Problem ist: meine Funktionen arbeiten nur mit zwei Argumenten, nicht mit der ganzen Liste.

Das zweite Problem: Ich muss die einzige Funktion haben, um das kleinste gemeinsame Vielfache zu finden (mein Code enthält zwei dafür).

Answer 1

Sie benötigen etwas, um durch eine Liste, z. Wenn es zwei Elemente in der Liste gibt, mache dein normales LCM. Wenn es länger ist, dann wiederhole das Listenende und führe LCM mit diesem Ergebnis und dem ersten Element aus.

def lcm(in_list): 
    if len(in_list) == 2: 
     # Do your normal LCM computation here 
    else: 
     return lcm([in_list[0], lcm(in_list[1:])) 

Answer 2

müssen Sie zu LCM der gesamten Liste finden. Lass "l" das LCM des gesamten Arrays sein und wenn wir 2 Zufallszahlen aus dem Array auswählen, haben sie ein LCM, sagen "l1" und so weiter und so weiter "l2", "l3", "l4" .. .. das LCM von diesen wird auch das LCM des gesamten Arrays sein.

# we can find LCM of two numbers by the basic prime factorizing method 
# but i will use the idea that GCD(a,b) * LCM(a,b) = a*b 
# and it is easy to find the GCD(a,b)=[GCD(a,a%b)or GCD(b,b%a)] depending on if a is bigger or b 
# i have used this idea because factoring large numbers take time. 

so ist meine Idee, die Sie teilen können und

def LCM_of_array(array): 
    if len(array)==2: 
     return LCM(a,b) 
    else: 
     return LCM(LCM_of_array(n[0:len(array)/2]) , LCM_of_array(n[len(array)/2:len(array)]) 

Sie LCM explizit definieren erobern kann (a, b) oder einfach nur ein paar weitere Linie von Codes in dieser nur

hinzufügen Edit: Code

def nod(a, b): #to find GCD 
    if b == 0: 
     return a 
    else: 
    if a>b: 
     return nod(b, a % b) 

    else: 
     return nod(a,b%a) 
def nok(a, b): #to find LCM of two numbers 
    return a * b/nod(a, b) 

def nok_of_array(n): #function for LCM of array 
    if len(n) == 2: 
     return nok(n[0], n[1]) 
    else: 
     return nok (nok_of_array(n[ 0:len(n)/2 ]) , nok_of_array(n [ len(n)/2 : len(n)])) 

Answer 3

Mein Code, die letzte Rückkehr funktioniert nicht korrekt.

import random 
def nod(a, b): 
    if b == 0: 
     return a 
    else: 
     return nod(b, a % b) 
def nok(a, b): 
    return a * b/nod(a, b) 
def nok_of_array(n): 
    if len(n) == 2: 
     return nok(n[1], n[2]) 
    else: 
     return nok(nok_of_array[0:len(n)/2], nok_of_array[len(n)/2:len(n)]) 
n = [random.randint(-20,20) for i in range(0, random.randint(1, 20))] 
print(nok_of_array(n)) 
print(n) 

Answer 4

Hier ist eine Lösung, die ich erarbeiten konnte und es hat für mich funktioniert.

def findDivisor(num): 
    if num%2 == 0: 
     return 2 
    elif num%3==0: 
     return 3 
    return num 

def LCM(nums): 
    lcm = 1 
    while len(nums) > 0: 
     minOfnums = min(nums) 
     divisor = findDivisor(minOfnums) 

     for x in range(0, len(nums)): 
      Quotient = nums[x]/divisor 
      Reminder = nums[x]%divisor 
      if Reminder == 0: 
       nums[x] = Quotient 

     lcm*=divisor 
     minOfnums = min(nums) 
     if minOfnums == 1: 
      nums.remove(minOfnums) 
    return lcm