1

このアルゴリズムに問題があります。特定の範囲の数値の最小公倍数を見つけようとしています。次の関数は、数値の因数を見つけ、数値のさまざまな因数を数え、因数を数えて、このアルゴリズムに基づいて数値の範囲の lcm を見つけ、最後に lcm を計算します。ただし、このコードを実行すると、一番下の print ステートメントは正しい答えを出力しません。代わりに、確かに正しくないことがわかっている番号を取得します。このコードの問題点を指摘するには、主に 2 番目の目が必要です。誰でも助けることができますか？

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

ユークリッドのアルゴリズムで単純に 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 に答える