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

Liste des GroupesRevenir à fcl python 
Sujet : Re: [RESOLU] : Panne en Python...
De : alain (at) *nospam* universite-de-strasbourg.fr.invalid (Alain Ketterlin)
Groupes : fr.comp.lang.python
Date : 02. Oct 2022, 21:22:41
Autres entêtes
Organisation : Université de Strasbourg
Message-ID : <87ill2rpxa.fsf@universite-de-strasbourg.fr.invalid>
References : 1 2
User-Agent : Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
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.

Date Sujet#  Auteur
28 Sep 22 * Panne en Python...11Dominique
28 Sep 22 +- Re: Panne en Python...1Alain Ketterlin
2 Oct 22 +* [NON RESOLU] : Panne en Python...7AIEO
2 Oct 22 i+- Re: [NON RESOLU] : Panne en Python...1Olivier Miakinen
2 Oct 22 i`* Re: [NON RESOLU] : Panne en Python...5Alain Ketterlin
2 Oct 22 i `* Re: [NON RESOLU] : Panne en Python...4AIEO
2 Oct 22 i  `* Re: [NON RESOLU] : Panne en Python...3Alain Ketterlin
2 Oct 22 i   `* Re: [NON RESOLU] : Panne en Python...2AIEO
2 Oct 22 i    `- Re: [NON RESOLU] : Panne en Python...1Alain Ketterlin
2 Oct 22 `* [RESOLU] : Panne en Python...2Olivier Miakinen
2 Oct 22  `- Re: [RESOLU] : Panne en Python...1Alain Ketterlin

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal