C ++ - Algorithmus zum Berechnen des kleinsten gemeinsamen Vielfachen für mehrere Zahlen

Gibt es eine C++ - Algorithmus zur Berechnung des kleinsten gemeinsamen vielfachen für mehrere Nummern, wie lcm(3,6,12) oder lcm(5,7,9,12)?

InformationsquelleAutor der Frage Askener | 2010-11-19

algorithm c++lcm

Können Sie die Verwendung von std::accumulate und einige Hilfsfunktionen:

#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';
}

InformationsquelleAutor der Antwort Blastfurnace

17

boost bietet Funktionen für die Berechnung lcm von 2 zahlen (siehe hier)

Dann mit der Tatsache, dass
```
lcm(a,b,c) = lcm(lcm(a,b),c)
```
Können Sie leicht berechnen, lcm für mehrere Nummern sowie

InformationsquelleAutor der Antwort Vladimir
6

Der Algorithmus ist nicht spezifisch für C++. AFAIK, es gibt keine standard-library-Funktion.

Zur Berechnung des LCM, müssen Sie zunächst die Berechnung der GCD (Greatest Common Divisor) mit Euclids algorithm.

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

Den GCD-Algorithmus ist in der Regel für zwei Parameter, aber...
```
GCD (a, b, c) = GCD (a, GCD (b, c))
              = GCD (b, GCD (a, c))
              = GCD (c, GCD (a, b))
              = ...
```
Zur Berechnung der LCM verwenden...
```
                a * b
LCM (a, b) = ----------
             GCD (a, b)
```
Die Logik, basierend auf der Primzahl-ZERLEGUNG. Die allgemeinere form (mehr als zwei Variablen) ist...
```
                                          a                 b        
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
                                    GCD (a, b, ...)   GCD (a, b, ...)
```
EDIT - tatsächlich, ich glaube, das Letzte bit falsch sein kann. Die erste LCM (zwei Parameter), ist richtig, aber.

InformationsquelleAutor der Antwort Steve314
4

Verwendung von GCC mit C++14 folgenden code war für mich:
```
#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);
});
```
In C++17 es gibt std::lcm-Funktion (http://en.cppreference.com/w/cpp/numeric/lcm) genutzt werden können, reichern sich direkt.

InformationsquelleAutor der Antwort dividedbyzero

Als C++17, die Sie verwenden können,std::lcm.

Und hier ist ein kleines Programm, das zeigt, wie spezialisiert es für mehrere Parameter

#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;
}

Test gibt es hier: https://wandbox.org/permlink/25jVinGytpvPaS4v

InformationsquelleAutor der Antwort smac89

1

Nicht gebaut, um die standard-Bibliothek. Sie müssen entweder selbst erstellen oder Holen Sie sich eine Bibliothek, die es getan hat. Ich Wette Boost hat eine...

InformationsquelleAutor der Antwort John Dibling

Ich gerade erstellt gcd für mehrere Nummern:

#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 - Anzahl der zahlen.

InformationsquelleAutor der Antwort TheHaris

/*

Copyright (c) 2011, Louis-Philippe Lessard
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

unsigned gcd ( unsigned a, unsigned b );
unsigned gcd_arr(unsigned * n, unsigned size);
unsigned lcm(unsigned a, unsigned b);
unsigned lcm_arr(unsigned * n, unsigned size);
int main()
{
    unsigned test1[] = {8, 9, 12, 13, 39, 7, 16, 24, 26, 15};
    unsigned test2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
    unsigned result;

    result = gcd_arr(test1, sizeof(test1) / sizeof(test1[0]));
    result = gcd_arr(test2, sizeof(test2) / sizeof(test2[0]));
    result = lcm_arr(test1, sizeof(test1) / sizeof(test1[0]));
    result = lcm_arr(test2, sizeof(test2) / sizeof(test2[0]));

    return result;
}


/**
* Find the greatest common divisor of 2 numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] a First number
* @param[in] b Second number
* @return greatest common divisor
*/
unsigned gcd ( unsigned a, unsigned b )
{
    unsigned c;
    while ( a != 0 )
    {
        c = a;
        a = b%a;
        b = c;
    }
    return b;
}

/**
* Find the least common multiple of 2 numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] a First number
* @param[in] b Second number
* @return least common multiple
*/
unsigned lcm(unsigned a, unsigned b)
{
    return (b / gcd(a, b) ) * a;
}

/**
* Find the greatest common divisor of an array of numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return greatest common divisor
*/
unsigned gcd_arr(unsigned * n, unsigned size)
{
    unsigned last_gcd, i;
    if(size < 2) return 0;

    last_gcd = gcd(n[0], n[1]);

    for(i=2; i < size; i++)
    {
        last_gcd = gcd(last_gcd, n[i]);
    }

    return last_gcd;
}

/**
* Find the least common multiple of an array of numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return least common multiple
*/
unsigned lcm_arr(unsigned * n, unsigned size)
{
    unsigned last_lcm, i;

    if(size < 2) return 0;

    last_lcm = lcm(n[0], n[1]);

    for(i=2; i < size; i++)
    {
        last_lcm = lcm(last_lcm, n[i]);
    }

    return last_lcm;
}

Source code-Referenz

InformationsquelleAutor der Antwort yayay

Können Sie berechnen, LCM und oder GCM in boost wie diese:

#include <boost/math/common_factor.hpp>
#include <algorithm>
#include <iterator>


int main()
{
    using std::cout;
    using std::endl;

    cout << "The GCD and LCM of 6 and 15 are "
     << boost::math::gcd(6, 15) << " and "
     << boost::math::lcm(6, 15) << ", respectively."
     << endl;

    cout << "The GCD and LCM of 8 and 9 are "
     << boost::math::static_gcd<8, 9>::value
     << " and "
     << boost::math::static_lcm<8, 9>::value
     << ", respectively." << endl;
}

(Beispiel entnommen aus http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html)

InformationsquelleAutor der Antwort portforwardpodcast

0

Die Codes gegeben, nur oben erläutert, über die Bewertung von LCM für mehrere zahlen jedoch ist es sehr wahrscheinlich passieren, dass während der Durchführung der Multiplikationen können wir überlauf integer-limit für Daten Typ Speicher

*Eine Ecke Fall :- *

z.B.
wenn bei der Auswertung erreichen Sie die situation so, dass, wenn LCM_till_now=1000000000000000 next_number_in_list=99999999999999 und Damit GCD=1 (beide co sind relativ prim zueinander)

Also, wenn u ausführen Betrieb (LCM_till_now*next_number_in_list) wird auch nicht fit in "unsigned long long int"

Abhilfe :-
1.Big Integer Klasse
2.Oder wenn das problem ist zu Fragen für die LCM - %MOD----------->dann gelten die Eigenschaften der modularen Arithmetik.

InformationsquelleAutor der Antwort user3166642

Wobei die Tatsache, dass lcm sollten teilbar sein
von allen zahlen in der Liste. Hier ist die Liste ist ein Vektor mit zahlen

        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();

InformationsquelleAutor der Antwort Archit Kansal

Ich fand diese während der Suche ein ähnliches problem und wollte dazu beitragen, was ich kam mit zwei zahlen.

#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;
}

InformationsquelleAutor der Antwort Chuck Claunch

-1

Wenn man sich auf dieser Seitesehen Sie einen ziemlich einfachen Algorithmus, den Sie verwenden konnten. 🙂

Ich sage nicht, dass es effizient oder alles, Geist, aber es funktioniert konzeptionell Skala um mehrere Nummern. Sie brauchen nur Raum für die Verfolgung Ihrer ursprünglichen zahlen und eine geklonte Satz, den Sie manipulieren, bis Sie die LCM.

InformationsquelleAutor der Antwort Platinum Azure

-1

#include
#include

void main()
{
    clrscr();

    int x,y,gcd=1;

    cout<>x;

    cout<>y;

    for(int i=1;i<1000;++i)
    {
        if((x%i==0)&&(y%i==0))
        gcd=i;
    }

    cout<<"\n\n\nGCD :"<
    cout<<"\n\n\nLCM :"<<(x*y)/gcd;

    getch();
}

InformationsquelleAutor der Antwort MUHAMMAD USMAN ANJUM

-1
- lassen Sie die Menge der zahlen, deren lcm, die Sie wünschen zu berechnen, werden theta -
- lassen, ich, der Multiplikator, be = 1
- let x = die größte Zahl in theta
- x * i
- wenn für jedes element j in theta, (x*i)%j=0, dann ist x*i ist die am wenigsten LCM
- wenn nicht, Schleife und erhöhen i um 1
InformationsquelleAutor der Antwort TheJackal

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.