Mission 2

Durant cette partie de la mission vous allez écrire un petit programme Python permettant de rechercher les racines entières d'une équation diophantienne :

Cette recherche se fera en énumérant toutes les valeurs possibles de x, y et z et en vérifiant pour chacun triplet de valeurs si l'équation diophantienne est vérifiée (attention, vous ne pouvez pas utiliser les fonctions du package math dans cette mission). Cette technique d'énumération est parfois utilisée dans le domaine de la sécurité informatique pour décoder des messages cryptés sans connaître la clé de cryptage qui a été utilisée. Elle s'appelle attaque par force brute ou recherche exhaustive.

• Groupes : A partir de cette deuxième mission, vous travaillerez en binômes de deux étudiants. Associez-vous en binômes au sein de votre groupe ou de votre local. Si vous êtes en nombre impair dans votre local, un étudiant devra travailler seul. Vous devrez travailler avec un étudiant différent chaque semaine; organisez une tournante des binômes.

• Organisation : Décidez comment vous allez faire, dans votre sous-groupe, pour travailler à deux : est-ce toujours le même qui travaille à l'ordinateur ou allez-vous alterner au milieu de la mission ? Que fait celui qui n'est pas à l'ordinateur pour aider celui qui l'est ? A quel moment faut-il aller consulter le livre de référence ? Faut-il avoir lu toutes les sections du livre indiquées dans la rubrique Ressources avant de faire le travail ?

• Analyse : Considérez le programme ci-dessous :

  # Recherche des racines d'une équation a x + b y = c
  # Charles Pecheur, septembre 2018
  
  solutions = 0
  a = int(input("Entrez la valeur du coefficient a : "))
  b = int(input("Entrez la valeur du coefficient b : "))
  c = int(input("Entrez la valeur du coefficient c : "))
  max = int(input("Entrez la valeur maximale pour x et y : "))
  
  for x in range(1,max):
      for y in range(1,max):
         if a*x + b*y == c:
             print("x =", x, " y =", y)
             solutions += 1
  
  if solutions == 0:
      print("Aucune solution trouvee")
  else:
      print(solutions, "solutions trouvees")
  

  Ce programme recherche les racines entières de l'équation diophantienne simple ax + by = c. Essayez de le lire et de bien comprendre comment il fonctionne. Dans Thonny, recopiez le programme dans un fichier equation_simple.py (copiez-collez à partir du syllabus) et testez-le en l'exécutant avec différentes valeurs de a, b et c. Vérifiez notamment que l'équation 8 x + 4 y = 1 n'admet aucune solution alors que l'équation 2 x + y = 3 en admet une infinité.

  Vous pouvez inspecter les valeurs des différentes variables en affichant le panneau des variables (menu View > Variables) et en exécutant le programme pas à pas (bouton Debug). Attention, vous devez interrompre votre programme en cours d'exécution (bouton Stop) avant de pouvoir lancer une nouvelle exécution.

• Vous pouvez maintenant créer un nouveau programme equation.py permettant de trouver des solutions à des équations diophantiennes du type x^a + y^b = z^c.

  • Recherchez les racines d'une équation particulière. Prenons comme exemple x³ + y² = z⁹.
  • Généralisez votre programme de façon à ce que par exemple l'utilisateur puisse, en utilisant la fonction input(), entrer la valeur de l'exposant de z. Utilisez z ** c pour calculer la valeur de z^c. Vérifiez que votre programme permet de retrouver les racines de x³ + y² = z⁹, c'est-à-dire 7, 13 et 2.
  • Continuez à généraliser votre programme en permettant à l'utilisateur d'entrer au clavier les valeurs des exposants de x, y et z.
  • Testez votre programme avec différents exposants. Vous trouverez sur Internet des solutions pour de nombreuses équations de ce type [1] et par exemple :
    • x⁷ + y³ = z²
    • x⁵ + y⁴ = z²
    • x³ + y² = z⁷

  Si vous n'obtenez pas le bon résultat, analysez ce qui se passe et corrigez jusqu'à obtention du résultat désiré. Cette phase de test est essentielle dans le développement d'un programme. Indiquez dans le fichier README.TXT que vous renverrez à votre tuteur les tests que vous avez réalisés pour le convaincre du bon fonctionnement de votre programme.

  N'oubliez pas de bien documenter votre programme en utilisant des commentaires.

• Si vous avancez vite, modifiez votre programme de façon à ce qu'il n'affiche que les racines qui n'ont aucun diviseur commun à l'exception de 1. Pour cela, vous devrez écrire un programme permettant de vérifier si trois nombres ont un diviseur commun. En Python, l'expression a \% b calcule le reste de la division euclidienne de a par b. Cela pourrait vous aider dans cette extension.

Soumettez votre travail au serveur de soumission. Indiquez dans le fichier README.TXT les tests que vous avez effectués et les problèmes éventuels que vous avez eu. Votre tuteur pourra les lire afin de préparer la réunion de bilan final.

Please log in to see this exercise