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

From	Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid>
Newsgroups	fr.comp.lang.python
Subject	Re: [RESOLU] : Panne en Python...
Date	2022-10-02 21:22 +0200
Organization	Université de Strasbourg
Message-ID	<87ill2rpxa.fsf@universite-de-strasbourg.fr.invalid> (permalink)
References	<th0qot$afg6$1@dont-email.me> <thccsb$1dd7$1@cabale.usenet-fr.net>

Show all headers | View raw

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.

Back to fr.comp.lang.python | Previous | Next — Previous in thread | Find similar

Thread

Panne en Python... Dominique <zzz@aol.com> - 2022-09-28 08:49 +0200
  Re: Panne en Python... Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-09-28 16:11 +0200
  [NON RESOLU] : Panne en Python... AIEO <zzz@aol.com> - 2022-10-02 03:56 +0200
    Re: [NON RESOLU] : Panne en Python... Olivier Miakinen <om+news@miakinen.net> - 2022-10-02 13:03 +0200
    Re: [NON RESOLU] : Panne en Python... Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-10-02 13:35 +0200
      Re: [NON RESOLU] : Panne en Python... AIEO <zzz@aol.com> - 2022-10-02 14:58 +0200
        Re: [NON RESOLU] : Panne en Python... Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-10-02 15:58 +0200
          Re: [NON RESOLU] : Panne en Python... AIEO <zzz@aol.com> - 2022-10-02 16:32 +0200
            Re: [NON RESOLU] : Panne en Python... Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-10-02 17:51 +0200
  [RESOLU] : Panne en Python... Olivier Miakinen <om+news@miakinen.net> - 2022-10-02 18:05 +0200
    Re: [RESOLU] : Panne en Python... Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-10-02 21:22 +0200

csiph-web