编程知识 cdmana.com

Algorithme | plusieurs méthodes pour trouver le plus grand diviseur commun

Préface

Je crois que les gars ont demandé le plus grand diviseur commun de deux nombres?

Apprenons quelques façons différentes de trouver le plus grand diviseur commun aujourd'hui!

Nous pouvons améliorer notre pensée et notre code!

Conseils chaleureux:Les algorithmes d'aujourd'hui sont tousCMise en oeuvre linguistique Oh!

Méthode de l'épuisement

La méthode de l'épuisement peut aussi être appelée:Méthode directe、Méthode de définition.

L'idée est la suivante:

Définir une variable pour tenir le plus petit des deux nombres,Ensuite, essayez de faire une boucle pour voir si le nombre dans cette variable peut être divisé par les deux nombres en même temps,Si ça ne marche pas, ça diminue1,Essayez encore.

Le Code implémenté est le suivant:

#include<stdio.h>

int main()
{
    
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &a, &b);
	
	//cPour le stockageaEtbLe plus petit
	c = a < b ? a : b;

	//SiaEtbLe plus grand diviseur commun de ces deux nombres est1,AlorswhileDernier à1Encore.c--La boucle s'arrête également après
	while (c > 0)
	{
    
		if (a % c == 0 && b % c == 0)
		{
    
			printf("Le plus grand diviseur commun est:%d", c);
			break;
		}
		c--;

	}
	
	return 0;
}

Division de la phase de laminage

La Division de phase par laminage est également appelée algorithme euclidien .

Leur plus grand diviseur commun est divisé en deux cas :

(Par défautaDiviser par,bDiviseur,cReste)

L'un est quand aAvecb Reste entre c À zéro , Le plus grand diviseur commun de ces deux nombres est le diviseur b.
Deuxièmement, quand aAvecb Reste entre c Quand ce n'est pas zéro , Le plus grand diviseur commun de ces deux nombres est égal au reste des deux. c Et diviseur bLe plus grand diviseur commun entre.

C'est - à - dire que le diviseur de la première division est le diviseur de la deuxième division. , Le reste obtenu après la Division de deux nombres est le diviseur de la deuxième division jusqu'à ce que le reste soit 0, Le diviseur est le plus grand diviseur commun .

Cette approche peut être mise en œuvre de deux façons: : L'une est la méthode directe. , L'autre est la récursion des fonctions .

Les implémentations spécifiques du Code sont les suivantes:

#include<stdio.h>

int func1(int a, int b)
{
    
	int c = 0;
	while (c = a % b)
	{
    
		a = b;
		b = c;

	}
	return b;
}

int func2(int a, int b)
{
    
	if (!(a % b))
		return b;
	else
		return func2(b, a % b);

}

int main()
{
    
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &a, &b);

	// Réalisation intuitive 
	int ret1 = func1(a, b);
	printf("Le plus grand diviseur commun est:%d\n", ret1);

	//Mise en œuvre récursive
	int ret2 = func2(a, b);
	printf("Le plus grand diviseur commun est:%d\n", ret2);


	return 0;
}

Loi dérogatoire

Cette méthode est dérivée de l'ancienne 《Chapitre 9 arithmétique》, Incarne la sagesse des anciens chinois !

L'idée est la suivante::
Compte tenu de deux entiers positifs, Le plus grand diviseur de tolérance de ces deux nombres est la différence entre les deux nombres ( Non négatif ) Le plus grand diviseur commun avec le plus petit nombre .

Cette méthode convient à la solution récursive .

Les codes spécifiques sont les suivants::

#include<stdio.h>

int func1(int a, int b)
{
    
	if (a == b)
		return a;
	else if (a > b)
		return func1(a - b, b);
	else
		return func1(b - a, a);

}

int main()
{
    
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &a, &b);


	//Mise en œuvre récursive
	int ret1 = func1(a, b);
	printf("Le plus grand diviseur commun est:%d\n", ret1);


	return 0;
}

SteinAlgorithmes

Cet algorithme est également appelé algorithme binaire , L'algorithme est défini par J. Stein 1961Présenté en, C'est aussi le plus grand diviseur commun de deux nombres. .

Insérer la description de l'image ici

Insérer la description de l'image ici

(Conseils chaleureux: Les deux images ci - dessus proviennent du Web )

Les codes sont les suivants::

//SteinAlgorithmes

#include<stdio.h>

//Loi dérogatoire
int func1(int a, int b)
{
    
	if (a == b)
		return a;
	else if (a > b)
		return func1(a - b, b);
	else
		return func1(b - a, a);
}

//Stein
int func2(int a, int b)
{
    
	// Si les deux chiffres sont égaux , Alors le plus grand diviseur commun est lui - même 
	if (a == b)
		return a;
	if (0 == a)
		return b;
	if (0 == b)
		return a;
	if (a % 2 == 1)
	{
    
		if (b % 2 == 1)
		{
    
			// Assurez - vous d'obtenir un nombre positif lorsque vous soustrayez 
			int tmp1 = a > b ? a : b;
			int tmp2 = a < b ? a : b;
			return func1((tmp1 - tmp2), tmp2);

		}
		else
		{
    
			return func2(a, b / 2);
		}
	}
	else
	{
    
		if (b % 2 == 1)
		{
    
			return func2(a / 2, b);
		}
		else
		{
    
			return func2(a / 2, b / 2) * 2;
		}
	}

}


int main()
{
    
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);

	int ret = func2(a, b);

	printf("%d\n", ret);

	return 0;
}

C'est la réalisation de base de l'algorithme ,Mais,En cours de développement, Le nombre entré peut être grand , Donc le module et la Division perdent du temps. ,Nous avons remarqué, Dans ce code , La Division est divisée par 2Principalement, L'Arithmétique modulaire est la principale méthode de jugement de la parité .

Ensuite, nous pouvons optimiser le code ci - dessus .

Déterminer si un nombre impair ou pair : Un nombre par bit et 1,Les résultats sont les suivants:1 Ce nombre est impair. ,Les résultats sont les suivants:0 Ce nombre est pair. .

Multiplier par deux : Un chiffre à gauche 1Bits

Divisé par deux : Un nombre à droite 1Bits

Nous pouvons maintenant modifier le code ci - dessus

//SteinAlgorithmes

#include<stdio.h>

//Loi dérogatoire
int func1(int a, int b)
{
    
	if (a == b)
		return a;
	else if (a > b)
		return func1(a - b, b);
	else
		return func1(b - a, a);
}

//Stein
int func2(int a, int b)
{
    
	// Si les deux chiffres sont égaux , Alors le plus grand diviseur commun est lui - même 
	if (a == b)
		return a;
	if (0 == a)
		return b;
	if (0 == b)
		return a;
	if (a&1)
	{
    
		if (b&1)
		{
    
			// Assurez - vous d'obtenir un nombre positif lorsque vous soustrayez 
			int tmp1 = a > b ? a : b;
			int tmp2 = a < b ? a : b;
			return func1((tmp1 - tmp2), tmp2);

		}
		else
		{
    
			return func2(a, b>>1);
		}
	}
	else
	{
    
		if (b&1)
		{
    
			return func2(a>>1, b);
		}
		else
		{
    
			return func2(a>>1, b>>1)<<1;
		}
	}

}


int main()
{
    
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);

	int ret = func2(a, b);

	printf("%d\n", ret);

	return 0;
}

L'Opération bit est l'opération directe sur les données en mémoire. ,Dans ce cas, L'efficacité sera beaucoup plus élevée que la Division et le module. ~

Conclusion

L'apprentissage de l'algorithme ne dépend pas de la quantité de code ou non , La clé est de savoir si vous avez appris quelque chose. , Les gars ne doivent pas se limiter à lire le Code. , Il faut écrire plus de code. .

Enfin... ,La création n'est pas facile, J'espère que les gars bougeront les mains. , Fais - moi attention. 、 Un Oui et un commentaire. ~

En raison de mes capacités limitées,S'il y a une erreur, J'espère que les grands hommes feront remarquer !
Insérer la description de l'image ici

版权声明
本文为[Ersansui]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211538501r.html

Scroll to Top