Нахождение LCM диапазона чисел - PullRequest
Новая
       85

Нахождение LCM диапазона чисел

20 голосов
/ 09 октября 2008

Сегодня я прочитал интересный пост DailyWTF, "Из всех возможных ответов ..." , и он заинтересовал меня достаточно, чтобы выкопать оригинальное сообщение на форуме , где оно было отправлено. , Это заставило меня задуматься о том, как бы я решил эту интересную проблему - оригинальный вопрос поставлен на Project Euler как:

2520 - наименьшее число, которое можно разделить на каждое из числа от 1 до 10 без остатка.

Какое наименьшее число делится на все цифры от 1 до 20?

Чтобы преобразовать это как вопрос программирования, как бы вы создали функцию, которая может найти наименьшее общее кратное для произвольного списка чисел?

Я невероятно плох с чистой математикой, несмотря на мой интерес к программированию, но я смог решить эту проблему после небольшого поиска в Google и некоторых экспериментов. Мне любопытно, какие другие подходы могут использовать пользователи SO. Если вы так склонны, опубликуйте код ниже, надеюсь, вместе с объяснением. Обратите внимание, что хотя я уверен, что существуют библиотеки для вычисления GCD и LCM на разных языках, меня больше интересует то, что отображает логику более непосредственно, чем вызов библиотечной функции :-)

Я больше всего знаком с Python, C, C ++ и Perl, но любой язык, который вы предпочитаете, приветствуется. Бонусные баллы за объяснение логики для других людей с математическими проблемами, таких как я.

РЕДАКТИРОВАТЬ : После отправки я нашел этот похожий вопрос Наименьшее общее множитель для 3 или более чисел , но на него ответил тот же базовый код, который я уже понял, и нет реального объяснение, поэтому я чувствовал, что это было достаточно по-другому, чтобы оставить открытым.

Ответы [ 14 ]

0 голосов
/ 22 апреля 2015

Вот мой ответ в JavaScript. Сначала я подошел к этому из простых чисел и разработал замечательную функцию многократно используемого кода для поиска простых чисел, а также для поиска простых факторов, но в итоге решил, что этот подход был проще.

Нет ничего уникального в моем ответе, который не был опубликован выше, просто в Javascript, который я не видел специально. 

//least common multipe of a range of numbers
function smallestCommons(arr) {
   arr = arr.sort();
   var scm = 1; 
   for (var i = arr[0]; i<=arr[1]; i+=1) { 
        scm =  scd(scm, i); 
    }
  return scm;
}


//smallest common denominator of two numbers (scd)
function scd (a,b) {
     return a*b/gcd(a,b);
}


//greatest common denominator of two numbers (gcd)
function gcd(a, b) {
    if (b === 0) {  
        return a;
    } else {
       return gcd(b, a%b);
    }
}       

smallestCommons([1,20]);
0 голосов
/ 12 апреля 2015

Это, наверное, самый чистый, самый короткий ответ (с точки зрения строк кода), который я когда-либо видел. 

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

n = 1
for i in xrange(1, 21):
    n = lcm(n, i)

источник: http://www.s -anand.net / euler.html

0 голосов
/ 11 октября 2008

Вот мой удар по Python: 

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2 
    while i <= n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

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

0 голосов
/ 09 октября 2008

Продолжая @ комментарий Александра, я хотел бы отметить, что если вы можете скомпоновать числа с их простыми числами, удалить дубликаты, а затем умножить, у вас будет свой ответ.

Например, 1-5 имеют главные коэффициенты 2,3,2,2,5. Удалите дублированный «2» из списка факторов «4», и у вас есть 2,2,3,5. Умножая их вместе, получим 60, что является вашим ответом.

Ссылка на Wolfram, приведенная в предыдущем комментарии, http://mathworld.wolfram.com/LeastCommonMultiple.html использует гораздо более формальный подход, но короткая версия приведена выше.

Приветствие.

Страница:
...