Fonction GCD dans la bibliothèque c++ sans cmath
j'écris une classe de nombres mixtes et j'ai besoin d'une fonction rapide et facile de "grand diviseur commun". Quelqu'un peut-il me donner le code ou un lien vers le code?
5 réponses
je suis tenté de voter pour fermer -- il semble difficile de croire qu'une implémentation serait difficile à trouver, mais qui sait avec certitude.
unsigned GCD(unsigned u, unsigned v) {
while ( v != 0) {
unsigned r = u % v;
u = v;
v = r;
}
return u;
}
en C++ 17 ou plus récent, vous pouvez juste #include <numeric> , et utiliser std::gcd (et si vous vous souciez, de la gcd, les chances sont assez justes que vous serez intéressé par le std::lcm qui a été ajouté ainsi).
la bibliothèque d'algorithmes libstdc++ a une fonction gcd cachée (j'utilise g++ 4.6.3).
#include <iostream>
#include <algorithm>
int main()
{
cout << std::__gcd(100,24);
return 0;
}
Vous êtes les bienvenus :)
mise à JOUR: @chema989 noté, en C++17 il y a std::gcd() fonction disponible avec <numeric> en-tête.
Un rapide une version récursive:
unsigned int gcd (unsigned int n1, unsigned int n2) {
return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}
ou la version itérative équivalente si vous êtes violemment opposé à la récursion (a) :
unsigned int gcd (unsigned int n1, unsigned int n2) {
unsigned int tmp;
while (n2 != 0) {
tmp = n1;
n1 = n2;
n2 = tmp % n2;
}
return n1;
}
remplacez simplement dans votre propre méthode de type de données, de comparaison zéro, d'affectation et de module (si vous utilisez un type non-basique comme une classe bignum , par exemple).
cette fonction provient en fait d'une réponse précédente de de la mienne pour l'élaboration des rapports d'aspect intégraux pour les tailles d'écran, mais la source originale était l'algorithme euclidien que j'ai appris il y a longtemps, détaillé ici sur Wikipedia si vous voulez savoir les mathématiques derrière elle.
(a) le problème avec certaines solutions récursives est qu'ils approchent la réponse si lentement que vous avez tendance à manquer d'espace de pile avant d'y arriver, comme avec le très mal pensé (pseudo-code):
def sum (a:unsigned, b:unsigned):
if b == 0: return a
return sum (a + 1, b - 1)
vous trouverez que très cher sur quelque chose comme sum (1, 1000000000) que vous (essayer) d'utiliser un milliard de cadres de pile. Le cas d'utilisation idéal pour la récursion est quelque chose comme une recherche binaire où vous réduisez l'espace de la solution de moitié pour chaque itération. Le plus grand diviseur commun est également un où l'espace de solution réduit rapidement de sorte que les craintes au sujet de l'utilisation massive de la pile sont infondées là.
pour C++17 Vous pouvez utiliser std::gcd défini dans l'en-tête <numeric> :
auto res = std::gcd(10, 20);
l'algorithme euclidienne est assez facile à écrire en C.
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}