1

我在使用这个算法时遇到了一些问题。我试图找到给定数字范围的最小公倍数。下面的函数求一个数的因数，数出数中不同的因数，数出因数，这样我就可以根据这个算法求出数范围的lcm，最后计算出lcm；但是，如果您运行此代码，则底部的打印语句不会打印正确的答案。相反，我得到一个我知道肯定不正确的数字。我主要需要第二双眼睛来指出这段代码的问题。任何人都可以帮忙吗？

from collections import defaultdict

def factors_of(number):
    factors = [];
    i = 2
    while number >= 2:
        if number % i == 0:
            factors.append(i)
            number = number / i
        else:
            i += 1
    return factors

def count_factors(number):
    count = {}
    factors = factors_of(number)
    for factor in factors:
        if not factor in count:
            count[factor] = 1
        else:
            count[factor] += 1
    return count

def count_factors_of_numbers_in_range(start, stop):
    count = defaultdict(int)
    for number in range(start, stop):
        factor_count = count_factors(number)
        for key in factor_count:
            if count[key] < factor_count[key]:
                count[key] = factor_count[key]
    return dict(count)

def find_lcm_of_numbers_in_range(start, stop):
    count = count_factors_of_numbers_in_range(start, stop)
    lcm = 1
    for key in count:
        total = count[key] * key
        lcm = total * lcm
    return lcm

print find_lcm_of_numbers_in_range(1, 21)
4

2 回答 2

0

为什么不能简单地通过 euclid 算法找到 gcd，然后将数字相乘并除以 gcd 以找到 LCM？

def decorator(d):
    """This is a decorator that will decorate all decorators. This will add update_wrapper
    to all decorators.
    (fun) -> fun
    """
    def _d(f):
        return update_wrapper(d(f), f)
    return update_wrapper(_d, d)



@decorator
def nary(f):
    """This is docp implementation of n_ary function above.
    (function) -> function
   Tue-23-April-2013
    """
    def n_ary(x, *args):
        if len(args) == 0:
            return x
        return f(x, n_ary(*args))
    return n_ary

@nary
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a
于 2013-07-18T06:07:36.393 回答
0

我弄清楚我做错了什么。我想我只是需要睡个好觉。

问题不在于 Python 的怪癖（我认为这可能是这样），而在于我自己的算法实现。在我的代码中

def find_lcm_of_numbers_in_range(start, stop):
    count = count_factors_of_numbers_in_range(start, stop)
    lcm = 1
    for key in count:
        total = count[key] * key
        lcm = total * lcm
    return lcm

我搞砸了将语句中的所有数字相乘total。我不需要将数字 2 乘以数字 4，而是需要将 2 自身乘以 4 次 ( 2 ** 4)。通过简单地调整代码看起来像

def find_lcm_of_numbers_in_range(start, stop):
    count = count_factors_of_numbers_in_range(start, stop)
    lcm = 1
    for key in count:
        total = key ** count[key]
        lcm = total * lcm
    return lcm

一切都解决了，我现在很开心。:)

于 2013-07-18T17:42:14.430 回答