C ++ алгоритм для вычисления наименьшего общего кратного для нескольких чисел - PullRequest
Новая
       26

C ++ алгоритм для вычисления наименьшего общего кратного для нескольких чисел

24 голосов
/ 20 ноября 2010

Существует ли алгоритм C ++ для вычисления наименьшего общего кратного для нескольких чисел, например lcm(3,6,12) или lcm(5,7,9,12)?

Ответы [ 15 ]

45 голосов
/ 20 ноября 2010

Вы можете использовать std :: накопить и некоторые вспомогательные функции: 

#include <iostream>
#include <numeric>

int gcd(int a, int b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

int lcm(int a, int b)
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

int main()
{
    int arr[] = { 5, 7, 9, 12 };

    int result = std::accumulate(arr, arr + 4, 1, lcm);

    std::cout << result << '\n';
}
17 голосов
/ 20 ноября 2010

boost предоставляет функции для вычисления lcm 2 чисел (см здесь )

Тогда, используя тот факт, что 

lcm(a,b,c) = lcm(lcm(a,b),c)

Вы также можете легко рассчитать lcm для нескольких чисел

6 голосов
/ 20 ноября 2010

Алгоритм не является специфичным для C ++. AFAIK, нет стандартной библиотечной функции.

Чтобы вычислить LCM, вы сначала рассчитываете GCD (Величайший общий делитель), используя алгоритм Евклида.

http://en.wikipedia.org/wiki/Greatest_common_divisor

Алгоритм GCD обычно задается для двух параметров, но ... 

GCD (a, b, c) = GCD (a, GCD (b, c))
              = GCD (b, GCD (a, c))
              = GCD (c, GCD (a, b))
              = ...

Чтобы вычислить LCM, используйте ... 

                a * b
LCM (a, b) = ----------
             GCD (a, b)

Логика для этого основана на простой факторизации. Более общая форма (более двух переменных): ... 

                                          a                 b        
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
                                    GCD (a, b, ...)   GCD (a, b, ...)

РЕДАКТИРОВАТЬ - на самом деле, я думаю, что последний бит может быть неправильным. Впрочем, первый LCM (для двух параметров) правильный.

4 голосов
/ 16 декабря 2016

Используя GCC с C ++ 14, у меня работал следующий код: 

#include <algorithm>
#include <vector>

std::vector<int> v{4, 6, 10};    
auto lcm = std::accumulate(v.begin(), v.end(), 1, [](auto & a, auto & b) {
    return abs(a * b) / std::__gcd(a, b);
});

В C ++ 17 есть функция std :: lcm (http://en.cppreference.com/w/cpp/numeric/lcm), которую можно использовать в накоплениинепосредственно.

3 голосов
/ 25 ноября 2017

Начиная с C ++ 17, вы можете использовать std::lcm.

А вот небольшая программа, которая показывает, как специализировать ее для нескольких параметров 

#include <numeric>
#include <iostream>

namespace math {

    template <typename M, typename N>
    constexpr auto lcm(const M& m, const N& n) {
        return std::lcm(m, n);
    }

    template <typename M, typename ...Rest>
    constexpr auto lcm(const M& first, const Rest&... rest) {
        return std::lcm(first, lcm(rest...));
    }
}

auto main() -> int {
    std::cout << math::lcm(3, 6, 12, 36) << std::endl;
    return 0;
}

Проверьте это здесь: https://wandbox.org/permlink/25jVinGytpvPaS4v

1 голос
/ 01 декабря 2012

Я только что создал gcd для нескольких номеров: 

#include <iostream>    
using namespace std;
int dbd(int n, int k, int y = 0);
int main()
{
    int h = 0, n, s;
    cin >> n;
    s = dbd(n, h);
    cout << s;
}

int dbd(int n, int k, int y){
        int d, x, h;
        cin >> x;
        while(x != y){
            if(y == 0){
                break;
            }
            if( x > y){
                x = x - y;
            }else{
                y = y - x;
            }
        }
        d = x;
        k++;
        if(k != n){
        d = dbd(n, k, x);
        }
    return d;
}

dbd - gcd.

n - количество чисел.

1 голос
/ 20 ноября 2010

Не встроено в стандартную библиотеку.Вам нужно либо собрать его самостоятельно, либо получить библиотеку, которая это сделала.Бьюсь об заклад, Boost имеет один ...

0 голосов
/ 14 ноября 2015

Используя тот факт, что lcm должен делиться на все числа в списке.Здесь список представляет собой вектор, содержащий числа 

        int lcm=*(len.begin());
    int ini=lcm;
    int val;
    int i=1;
    for(it=len.begin()+1;it!=len.end();it++)
    {
        val=*it;
        while(lcm%(val)!=0)
        {
            lcm+=ini;
        }
        ini=lcm;
    }
    printf("%llu\n",lcm);
    len.clear();
0 голосов
/ 30 сентября 2014

Я нашел это при поиске аналогичной проблемы и хотел внести то, что я придумал, для двух чисел. 

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    cin >> x >> y;

    // zero is not a common multiple so error out
    if (x * y == 0)
        return -1;

    int n = min(x, y);
    while (max(x, y) % n)
        n--;

    cout << n << endl;
}
0 голосов
/ 06 июля 2014

В приведенных выше кодах обсуждается только оценка LCM для нескольких чисел, однако вполне вероятно, что при выполнении умножения мы можем переполнение целочисленное ограничение для хранения типов данных

* Угловой регистр: - *

например, если при оценке вы попадаете в такую ​​ситуацию, что если LCM_till_now = 1000000000000000 next_number_in_list = 99999999999999 и следовательно GCD = 1 (поскольку оба они относительно взаимно просты друг с другом)

Поэтому, если вы выполняете операцию (LCM_till_now * next_number_in_list), она даже не поместится в "unsigned long long int"

Помощь: - 1.Используйте класс Big Integer 2. Или, если проблема требует LCM% MOD ----------->, тогда примените свойства модульной арифметики.

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