1A.2 - Classes, méthodes, attributs, opérateurs et carré magique (correction)

Correction.

Exercice 1 : carré magique

Exercice 2 : à faire à trois, carré magique (suite)

Exercice 3 : trouver tous les carrés magiques

La première version est fastidieuse à écrire mais simple à comprendre.

La seconde version n'est pas plus rapide mais elle contient moins de boucles.

La troisième version utilise le fait que les chiffres d'un carré magique sont tous différents. Il suffit de regarder seulement tous les permutations. La variable stop_after permet de se limiter seulement aux premiers.

Le langage Python propose une fonction qui parcourt toutes les permutations d'un ensemble : itertools.permutation. Cela réduit de beaucoup la longueur du programme.

Exercice 4 : faire plus rapide

Est-il possible d'aller plus vite que de parcourir l'ensemble des permutations ? La réponse est oui. En parcourant les permutations, la fonction qui teste si les chiffres sont uniques est devenue inutile. Pour vérifier qu'on va plus vite, on peut mesurer le temps que met la fonction pour trouver tous les carrés :

Pour aller plus vite, il faut utiliser la contrainte des sommes. Comment ? Lorsqu'on permute les nombres, on peut simplement vérifier que les deux premières lignes ont la même somme. L'utilisation de cette contrainte nous permet de d'aller 10 fois plus vite et d'obtenir le résultat en moins d'une seconde. L'inconvénient est que l'optimisation fonctionne parce qu'on ne parcourt pas toutes les permutations. On ne peut plus utiliser la fonction itertools.permutation.

Programme complet

On peut faire encore plus rapide en utilisant les contraintes pour inférer les autres coefficients (solution venant d'un élève) :