Le 28/09/2022 08:49, Dominique a écrit :
Il m'est demandé "d'arranger la liste en 15 nombres entiers de 1 à 15 de
telle sorte que la somme de 2 nombres voisins soit toujours un carré
parfait".
En partant de l'idée d'Alain Ketterlin, j'obtiens une solution plus courte
et plus élégante que celle donnée dans ton livre. En plus, elle permet de
trouver rapidement les solutions pour n'importe quel ensemble de nombres
de 1 à MAX, et pas seulement le cas où MAX = 15
=================================================================
import math
def est_un_carre(n):
isqrt = math.isqrt(n)
return isqrt * isqrt == n
def cherche(sequence, restant):
if not restant:
print(sequence)
else:
for x in restant:
if est_un_carre(sequence[-1] + x):
cherche(sequence + [x], restant - {x})
MAX_MAX=20
for MAX in range(1, MAX_MAX+1):
print("MAX =", MAX)
valeurs = {n for n in range(1,MAX+1)}
for i in valeurs:
cherche([i], valeurs - {i})
=================================================================
Résultat de l'exécution en 0,05 seconde pour MAX de 1 à 20 :
=================================================================
MAX = 1
[1]
MAX = 2
MAX = 3
MAX = 4
MAX = 5
MAX = 6
MAX = 7
MAX = 8
MAX = 9
MAX = 10
MAX = 11
MAX = 12
MAX = 13
MAX = 14
MAX = 15
[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]
MAX = 16
[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16]
[16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]
MAX = 17
[16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17]
[17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16]
MAX = 18
MAX = 19
MAX = 20
=================================================================
-- Olivier Miakinen