Je poursuis avec "100 énigmes mathématiques résolues avec Python" et un
exercice sur lequel je bute.
L'énoncé me donne cette liste :
liste=[2,14,11,5,8,12,6,3,1,9,7,13,5,4,10,15]
et me fait remarquer que la somme de chacun des trois premiers couples
me donne un carré. Arrivé au 4e couple, il n'y a plus de carré (5+8)
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".
J'ai créé une liste (resu) avec chaque couple susceptible de me donner
un carré parfait :
liste=[2,14,11,5,8,12,6,3,1,9,7,13,5,4,10,15]
resu=[]
deb=[x for x in range(1,16)]
fin=[x for x in range(1,16)]
for i in deb:
for j in fin:
tot=i+j
tot1=[i,j]
tot1.sort()
if tot1 not in resu and i!=j and tot**.5==int(tot**.5):
resu.append(tot1)
Je ne suis pas sÍ»r d'être parti dans la bonne direction. Ensuite, si
oui, quelle indication me donneriez-vous pour répondre Í la question ?
Si non, quelle piste me faudrait-il explorer ?
Je précise que le livre donne la solution, mais je préfère un peu
chercher par moi-même, mais lÍ ... :)
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 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
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 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
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
===============================================================
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 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
Alain Ketterlin
Olivier Miakinen <om+ writes:
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".
================================================================ > 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 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}) ================================================================
Détail cosmétique : tu peux commencer cherche par if len (sequence) == 0: for x in restant: cherche ([x], restant - {x}) else if not restant: ... ça permet d'appeler cherche ([], valeurs). Vraiment un détail. Détail algorithmique : au lieu de tester si la somme est un carré pour tous les restant, tu peux tester si il y a un restant pour tous les carrés : for c in carres: candidat = c - sequence[-1] if candidat in restant: cherche (sequence + [candidat], restant - {candidat}) o͹ carres est un paramètre additionnel (constant), qu'on calcule avant d'appeler cherche, par racine = 2 carres = [] while racine ** 2 < 2*MAX: carres.append (racine ** 2) racine = racine + 1 L'idée c'est qu'au début il y aura moins de carrés que de nombres restant, et qu'il y a beaucoup de sequences abandonnées rapidement. (Et accessoirement, pas besoin de isqrt.)
MAX = 1 [1]
Ouch, un artefact. Cela dit, il n'y a pas de somme de nombres successifs qui ne soit un carré. Plus, tous les nombres sont aussi des carrés :-) -- Alain.
Olivier Miakinen <om+news@miakinen.net> writes:
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".
================================================================ > import math
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
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})
================================================================
Détail cosmétique : tu peux commencer cherche par
if len (sequence) == 0:
for x in restant:
cherche ([x], restant - {x})
else if not restant:
...
ça permet d'appeler cherche ([], valeurs). Vraiment un détail.
Détail algorithmique : au lieu de tester si la somme est un carré pour
tous les restant, tu peux tester si il y a un restant pour tous les
carrés :
for c in carres:
candidat = c - sequence[-1]
if candidat in restant:
cherche (sequence + [candidat], restant - {candidat})
o͹ carres est un paramètre additionnel (constant), qu'on calcule avant
d'appeler cherche, par
L'idée c'est qu'au début il y aura moins de carrés que de nombres
restant, et qu'il y a beaucoup de sequences abandonnées rapidement. (Et
accessoirement, pas besoin de isqrt.)
MAX = 1
[1]
Ouch, un artefact. Cela dit, il n'y a pas de somme de nombres successifs
qui ne soit un carré. Plus, tous les nombres sont aussi des carrés :-)
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".
================================================================ > 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 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}) ================================================================
Détail cosmétique : tu peux commencer cherche par if len (sequence) == 0: for x in restant: cherche ([x], restant - {x}) else if not restant: ... ça permet d'appeler cherche ([], valeurs). Vraiment un détail. Détail algorithmique : au lieu de tester si la somme est un carré pour tous les restant, tu peux tester si il y a un restant pour tous les carrés : for c in carres: candidat = c - sequence[-1] if candidat in restant: cherche (sequence + [candidat], restant - {candidat}) o͹ carres est un paramètre additionnel (constant), qu'on calcule avant d'appeler cherche, par racine = 2 carres = [] while racine ** 2 < 2*MAX: carres.append (racine ** 2) racine = racine + 1 L'idée c'est qu'au début il y aura moins de carrés que de nombres restant, et qu'il y a beaucoup de sequences abandonnées rapidement. (Et accessoirement, pas besoin de isqrt.)
MAX = 1 [1]
Ouch, un artefact. Cela dit, il n'y a pas de somme de nombres successifs qui ne soit un carré. Plus, tous les nombres sont aussi des carrés :-) -- Alain.
