Algorithme C++ pour calculer le multiple le moins commun pour les nombres multiples
15 réponses
Vous pouvez utiliser std::accumulate et des fonctions d'aide:
#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';
}
l'algorithme n'est pas spécifique au c++. AFAIK, il n'y a pas de bibliothèque standard.
pour calculer le MCP, vous devez d'abord calculer le DCG (diviseur le plus commun) en utilisant L'algorithme Euclids.
http://en.wikipedia.org/wiki/Greatest_common_divisor
l'algorithme GCD est normalement donné pour deux paramètres, mais...
GCD (a, b, c) = GCD (a, GCD (b, c))
= GCD (b, GCD (a, c))
= GCD (c, GCD (a, b))
= ...
pour calculer le CMV, utilisez...
a * b
LCM (a, b) = ----------
GCD (a, b)
la logique pour cela est basée sur prime factorisation. La plus générale (plus de deux variables)...
a b
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
GCD (a, b, ...) GCD (a, b, ...)
EDIT-en fait, je pense que le dernier morceau peut être erroné. Le premier LCM (pour deux paramètres) est bon, cependant.
utiliser GCC avec C++14 le code suivant a fonctionné pour moi:
#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 il y a std::lcm fonction (http://en.cppreference.com/w/cpp/numeric/lcm) qui pourraient être utilisés dans d'accumuler directement.
std::lcm.
Et voici un petit programme qui montre comment se spécialisent pour de multiples paramètres
#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;
}
non intégré à la bibliothèque standard. Vous devez construire vous-même ou obtenir une bibliothèque qu'il a fait. Je parie Boost a un...
je viens de créer gcd pour plusieurs nombres:
#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 - pgcd.
n - nombre de numéros.
/*
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;
}
Vous pouvez calculer LCM et ou GCM dans boost comme ceci:
#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;
}
(exemple tiré de http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html)
Les Codes donnés ci-dessus ne présente que sur l'évaluation de LCM pour plusieurs numéros, mais il est très probable que en effectuant des multiplications nous pouvons overflow limite entière pour le stockage de type de données
*Un Coin De Cas :- *
e.g. Si lors de l'évaluation vous atteignez situation telle que si LCM_till_now=1000000000000000 next_number_in_list=99999999999999 et donc GCD=1 (comme les deux sont relativement co-premier unes des autres)
donc si vous effectuez une opération (LCM_till_now*next_number_in_list) ne rentre même pas dans "unsigned long long int"
Remède :- 1.Utiliser Grande Classe Entière 2.Ou si le problème est de demander le LCM%MOD----------->puis appliquer les propriétés de l'arithmétique modulaire.
en utilisant le fait que la GCV devrait être divisible par tous les nombres dans la liste. Ici, la liste est un vecteur contenant des nombres
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();
j'ai trouvé ceci en cherchant un problème similaire et je voulais contribuer ce que j'ai trouvé pour les deux nombres.
#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;
}
Si vous regardez cette page, vous pouvez voir un algorithme assez simple que vous pouvez utiliser. : -)
Je ne dis pas que c'est efficace ou quoi que ce soit, mais ça a une échelle conceptuelle à plusieurs nombres. Vous avez seulement besoin d'espace pour garder la trace de vos nombres originaux et un ensemble cloné que vous manipulez jusqu'à ce que vous trouviez le LCM.
#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();
}
- laissez l'ensemble des nombres dont vous voulez calculer le lcm être theta
- laissez-je, le multiplicateur, = 1
- let x = le plus grand nombre de thêta
- x * i
- si pour chaque élément j dans theta, (x*i)%j=0 alors x*i est le plus petit LCM
- si non, en boucle, et incrémenter i de 1