Path: ...!news.mixmin.net!aioe.org!No6DEx/YTI7k1hrrhSmZAA.user.46.165.242.75.POSTED!not-for-mail
From: Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid>
Newsgroups: fr.comp.lang.python
Subject: Re: [RESOLU] : Panne en Python...
Date: Sun, 02 Oct 2022 21:22:41 +0200
Organization: =?utf-8?Q?Universit=C3=A9?= de Strasbourg
Message-ID: <87ill2rpxa.fsf@universite-de-strasbourg.fr.invalid>
References: <th0qot$afg6$1@dont-email.me> <thccsb$1dd7$1@cabale.usenet-fr.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Injection-Info: gioia.aioe.org; logging-data="32285"; posting-host="No6DEx/YTI7k1hrrhSmZAA.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
X-Notice: Filtered by postfilter v. 0.9.2
Cancel-Lock: sha1:OBjGQlA8rlPNgDeTkqR3mylxRvw=
Bytes: 3415
Lines: 78

Olivier Miakinen <om+news@miakinen.net> writes:

>> Il m'est demand=C3=A9 "d'arranger la liste en 15 nombres entiers de 1 =
=C3=A0 15 de=20
>> telle sorte que la somme de 2 nombres voisins soit toujours un carr=C3=
=A9=20
>> parfait".

> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> import math
>
> def est_un_carre(n):
>     isqrt =3D math.isqrt(n)
>     return isqrt * isqrt =3D=3D 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=3D20
>
> for MAX in range(1, MAX_MAX+1):
>     print("MAX =3D", MAX)
>     valeurs =3D {n for n in range(1,MAX+1)}
>     for i in valeurs:
>         cherche([i], valeurs - {i})
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

D=C3=A9tail cosm=C3=A9tique : tu peux commencer cherche par

    if len (sequence) =3D=3D 0:
        for x in restant:
            cherche ([x], restant - {x})
    else if not restant:
       ...

=C3=A7a permet d'appeler cherche ([], valeurs). Vraiment un d=C3=A9tail.

D=C3=A9tail algorithmique : au lieu de tester si la somme est un carr=C3=A9=
 pour
tous les restant, tu peux tester si il y a un restant pour tous les
carr=C3=A9s :

        for c in carres:
            candidat =3D c - sequence[-1]
            if candidat in restant:
                cherche (sequence + [candidat], restant - {candidat})

o=C3=B9 carres est un param=C3=A8tre additionnel (constant), qu'on calcule =
avant
d'appeler cherche, par

    racine =3D 2
    carres =3D []
    while racine ** 2 < 2*MAX:
        carres.append (racine ** 2)
        racine =3D racine + 1

L'id=C3=A9e c'est qu'au d=C3=A9but il y aura moins de carr=C3=A9s que de no=
mbres
restant, et qu'il y a beaucoup de sequences abandonn=C3=A9es rapidement. (Et
accessoirement, pas besoin de isqrt.)

> MAX =3D 1
> [1]

Ouch, un artefact. Cela dit, il n'y a pas de somme de nombres successifs
qui ne soit un carr=C3=A9. Plus, tous les nombres sont aussi des carr=C3=A9=
s :-)

-- Alain.