c++ - mcm - minimo comun multiplo de 5

Algoritmo de C++ para calcular el mínimo común múltiplo para múltiples números

Question

¿Existe un algoritmo de C ++ para calcular el mínimo común múltiplo para números múltiples, como el lcm(3,6,12) o el lcm(5,7,9,12) ?

Answer 1

A partir de C ++ 17, puede usar http://en.cppreference.com/w/cpp/numeric/lcm .

Y aquí hay un pequeño programa que muestra cómo especializarlo para múltiples parámetros.

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

Pruébelo aquí: https://wandbox.org/permlink/25jVinGytpvPaS4v

Answer 2

Acabo de crear gcd para múltiples números:

#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 - número de números.

Answer 3

El algoritmo no es específico de C ++. AFAIK, no hay una función de biblioteca estándar.

Para calcular el LCM, primero debe calcular el GCD (el divisor común más grande) utilizando el algoritmo de Euclids.

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

El algoritmo GCD se da normalmente para dos parámetros, pero ...

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

Para calcular el MCM, use ...

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

La lógica para eso se basa en la factorización prima. La forma más general (más de dos variables) es ...

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

EDITAR - en realidad, creo que el último bit puede estar equivocado. Sin embargo, el primer MCM (para dos parámetros) es correcto.

Answer 4

Encontré esto mientras buscaba un problema similar y quería contribuir con lo que se me ocurrió para dos números.

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

Answer 5

Los Códigos dados anteriormente solo tratan sobre la evaluación de LCM para múltiples números, sin embargo, es muy probable que ocurra que al realizar multiplicaciones podemos desbordar el límite entero para el almacenamiento de tipos de datos

* Un caso de la esquina: - *

por ejemplo, si mientras evalúa, llega a una situación tal que si LCM_till_now = 1000000000000000 next_number_in_list = 99999999999999 y por lo tanto GCD = 1 (ya que ambos son relativamente primos entre sí)

Por lo tanto, si realiza una operación (LCM_till_now * next_number_in_list) no encajará en "unsigned long long int"

Remedio: - 1.Utilice Big Integer Class 2.O si el problema es pedir LCM% MOD -----------> luego aplique las propiedades de la aritmética modular.

Answer 6

No integrado en la biblioteca estándar. Necesitas construirlo tú mismo o conseguir una biblioteca que lo haya hecho. Apuesto que Boost tiene uno ...

Answer 7

Puedes calcular LCM y / o GCM al alza de esta manera:

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

(Ejemplo tomado de http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html )

Answer 8

Puedes usar std :: acumulación y algunas funciones de ayuda:

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

Answer 9

Si miras esta página , puedes ver un algoritmo bastante simple que podrías usar. :-)

No digo que sea eficiente ni nada de eso, pero sí se puede escalar conceptualmente a múltiples números. Solo necesita espacio para mantener un registro de sus números originales y un conjunto clonado que manipule hasta que encuentre el MCM.

Answer 10

Usando GCC con C ++ 14 me funcionó el siguiente código:

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

En C ++ 17 hay una función std :: lcm ( http://en.cppreference.com/w/cpp/numeric/lcm ) que se puede utilizar para acumular directamente.

Answer 11

Usando el hecho de que mcm debe ser divisible por todos los números en la lista. Aquí la lista es un vector que contiene números.

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

Answer 12

boost proporciona funciones para el cálculo del mcm de 2 números (ver here )

Entonces usando el hecho de que

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

También puedes calcular fácilmente el mcm para múltiples números

Answer 13

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

Answer 14

/*
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;
}

Referencia del código fuente

Answer 15

• deja que el conjunto de números cuyo mcm deseas calcular sea theta
• sea ​​i, el multiplicador, be = 1
• sea ​​x = el número más grande en theta
• x * i
• si para cada elemento j en theta, (x * i)% j = 0 entonces x * i es el menor MCM
• Si no, bucle, e incremente i por 1