Exemple Python montrant comment trouver le plus grand diviseur commun basé sur la division euclidienne

Cet article présente principalement la méthode Python de résolution du plus grand diviseur commun basée sur la méthode de division euclidienne. Il analyse la méthode de mise en œuvre et les compétences opérationnelles d'optimisation de Python en utilisant la méthode de division euclidienne pour résoudre le plus grand diviseur commun sous forme d'exemples. Les amis qui en ont besoin peuvent s'y référer

L'exemple de cet article décrit la méthode Python de résolution du plus grand diviseur commun basée sur la méthode de division euclidienne. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

J'ai déjà résumé la solution du plus grand diviseur commun dans Knuth TAOCP. En fait, la modification de l'algorithme dans les questions parascolaires nécessite la réalisation. du plus grand diviseur commun par division euclidienne.

Ma compréhension initiale de cette question était fausse et, naturellement, je n'avais pas de réponse standard. Écrivez maintenant l'implémentation du code correspondante selon la réponse standard :

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(55,120))

Le résultat de l'exécution du programme :

Échangez les positions des deux nombres. Le code est le suivant :

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(120,55))

Le résultat de l'exécution du programme :

La question posée mentionne que cela réduira l'efficacité. À en juger par le code ci-dessus, la perte d'efficacité devrait être due à la division et au jugement. Ici, prenez le code de l'algorithme précédent et comparez-le :

def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

Résultats d'exécution :

Le nouvel algorithme comporte une opération supplémentaire de division et de comparaison dans la boucle. En fait, l'efficacité de la comparaison est toujours bonne, mais l'opération de division entraînera une diminution de l'efficacité.

PS : Voici quelques outils de calcul supplémentaires recommandés pour votre référence ultérieure :

Fonction unaire en ligne (équation ) outils de calcul de résolution :
http://tools.jb51.net/jisuanqi/equ_jisuanqi

Calculatrice scientifique en ligne use_advanced calculator Calcul en ligne :
http://tools.jb51.net/jisuanqi/jsqkexue

Calculatrice en ligne_Calculatrice standard :
http://tools. jb51.net/jisuanqi/jsq

Recommandations associées :

résumé php des algorithmes courants pour calculer le plus grand diviseur commun de deux entiers_Tutoriel PHP

Comment utiliser Python pour résoudre le plus grand diviseur commun

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!