Re: [RESOLU] : Panne en Python...

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 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})
================================================================

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.