Path: ...!news.mixmin.net!aioe.org!K7PIs9tCGQ+WHJa7e6BylQ.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: Panne en Python...
Date: Wed, 28 Sep 2022 16:11:13 +0200
Organization: =?utf-8?Q?Universit=C3=A9?= de Strasbourg
Message-ID: <87zgejwpvi.fsf@universite-de-strasbourg.fr.invalid>
References: <th0qot$afg6$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Injection-Info: gioia.aioe.org; logging-data="52869"; posting-host="K7PIs9tCGQ+WHJa7e6BylQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
Cancel-Lock: sha1:i6A7eEufzhJ0bRauNZhV0OwuDZk=
X-Notice: Filtered by postfilter v. 0.9.2
Bytes: 6831
Lines: 166

Dominique <zzz@aol.com> writes:

[...]
> Il m'est demand=C3=A9 "d'arranger la liste en 15 nombres entiers de 1 =C3=
=A0 15
> de telle sorte que la somme de 2 nombres voisins soit toujours un
> carr=C3=A9 parfait".
>
> J'ai cr=C3=A9=C3=A9 une liste (resu) avec chaque couple susceptible de me=
 donner
> un carr=C3=A9 parfait :
>
> liste=3D[2,14,11,5,8,12,6,3,1,9,7,13,5,4,10,15]
> resu=3D[]
> deb=3D[x for x in range(1,16)]
> fin=3D[x for x in range(1,16)]
> for i in deb:
>     for j in fin:
>         tot=3Di+j
>         tot1=3D[i,j]
>         tot1.sort()
>         if tot1 not in resu and i!=3Dj and tot**.5=3D=3Dint(tot**.5):
>             resu.append(tot1)
>
> Je ne suis pas s=C3=BBr d'=C3=AAtre parti dans la bonne direction.

En fait, pas vraiment. L=C3=A0 tu cherches les couples de nombres formant un
carr=C3=A9, mais le probl=C3=A8me principal dans cet exercice c'est d'encha=
=C3=AEner
les couples...

Au passage : tu n'as pas vraiment besoin de deb et fin, qui ne servent
qu'aux boucles, donc :

for i in range (1, 16):
    for j in range (1, 16):
        ...

Ensuite, tu tries les deux =C3=A9l=C3=A9ments et tu v=C3=A9rifies qu'ils so=
nt
diff=C3=A9rents, parce que tu veux des couples (i,j) avec i<j. Autant g=C3=
=A9n=C3=A9rer
tout de suite les couples pertinents :

for i in range (1, 16):
    for j in range (i+1, 16):
        ...

> Ensuite, si oui, quelle indication me donneriez-vous pour r=C3=A9pondre =
=C3=A0
> la question ? Si non, quelle piste me faudrait-il explorer ?

Je ne vois pas de raison de penser que 1) il y a forc=C3=A9ment une solutio=
n,
et 2) on peut directement d=C3=A9terminer la solution (si elle existe donc).
J'en conclue qu'il faudra chercher, c'est-=C3=A0-dire essayer d'encha=C3=AE=
ner les
nombres, de toutes les fa=C3=A7ons possibles, et de voir si on trouve une
solution. C'est donc un probl=C3=A8me combinatoire.

(Note que si il y a une solution, alors il y en a au moins une
deuxi=C3=A8me -- qui est la liste invers=C3=A9e.)

Ensuite, remarque qu'avec des nombres entre 1 et 15, la somme est au
plus 29. Les seuls carr=C3=A9s qui peuvent appara=C3=AEtre sont donc 4, 9, =
16 et
25. (Ca simplifie un peu la recherche.)

Quand on cherche comme cela parmi plein de possibilit=C3=A9s, il faut
s'imaginer en plein milieu de la recherche : on a d=C3=A9j=C3=A0 encha=C3=
=AEn=C3=A9 quelques
nombres (on appelle cela sequence), qu'on ne peut donc plus utiliser :
on appelle restant l'ensemble des nombres encore utilisable (c'est
{1,2,...,15} moins les nombres de sequence, mais c'est pratique de lui
donner un nom).

Au d=C3=A9but s=C3=A9quence =3D [], et restant =3D {1,...,15}. On va essaye=
r toutes
les premi=C3=A8res =C3=A9tapes. Chaque fois qu'on a choisi un nombre x, on =
se
retrouve avec une nouvelle version : sequence + [x], restant - {x}. On a
donc une (potentiellement grande) hi=C3=A9rarchie de cas =C3=A0 essayer :

- on choisit 1 : sequence =3D [1], restant =3D {2,...,15}
  - on choisit 2, mais 1+2 n'est pas un carr=C3=A9 : perdu
  - on choisit 3 : sequence =3D [1,3], restant =3D {2,4,...,15}
    - on choisit 2 : perdu
    - on choisit 4 : perdu
    ... idem avec tous les autres
  - on choisit 4 : perdu
  ...
  - on choisit 8 : sequence =3D [1,8], restant =3D {2,...,7,9,...,15}
    - on choisit 2 : perdu
    ...
  ...
- on choisit 2 : sequence =3D [2], restant =3D {1,3,...,15}
  - on choisit 1 : perdu
  ...

Note que c'est vraiment une grande hi=C3=A9rachie, avec 15 cas au premier
niveau, ayant chacun 14 sous-cas, qui chacun a potentiellement 13
sous-sous-cas. Mais 1) il y plein de cas qu'on abandonne rapidement, et
2) si on trouve une solution, on sera dans un sous-sous-...-sous-cas
(avec 14 "sous").

Au fait : quand est-ce qu'on s'arr=C3=AAte ? D=C3=A9j=C3=A0, quand on est b=
loqu=C3=A9
(perdu). Et aussi quand on a tout essay=C3=A9. Quand est-ce qu'on a trouv=
=C3=A9
une solution : quand sequence est de longueur 15 (et restant est vide).

Ce qu'on voit avec la description ci-dessus, c'est qu'il ne suffit pas
de faire deux boucles imbriqu=C3=A9es, il faudrait en faire quinze (ou
quatorze), pour essayer tous les ordres des quinze nombres.

Mais on ne va pas faire cela, on va utiliser =C3=A0 la place une fonction
r=C3=A9cursive, qui va parcourir tout l'arbre des possibilit=C3=A9s. On tou=
s les
=C3=A9l=C3=A9ments :

def cherche (sequence, restant):
    if ... restant est vide ...:
        on a une solution dans sequence -> print
    else:
        for x in restant: # on essaie tout ce qu'on peut faire
            if ... sequence[-1] + x est un carr=C3=A9 ...:
                cherche (sequence+[x], restant-{x}) # sous-cas

Attention : cette fonction utilise le dernier =C3=A9l=C3=A9ment de sequence=
, il
faut donc l'appeler avec toutes les s=C3=A9quence de longueur 1 possibles

for i in range (1, 16):
    cherche ([i], {1,2,...,15} - {i})

Ou alors on int=C3=A8gre cela =C3=A0 la fonction, qui devient

def cherche (sequence, restant):
    if len (sequence) =3D=3D 0:
        for x in restant:
            cherche ([x], {1,...} - {x})
    elif ... restant est vide ...:
        ... comme ci-dessus ...

et on apelle simplement cherche ([], {1,...,15})

C'est l'id=C3=A9e. On peut faire des choses pour simplifier. Par exemple, le
test "sequence[-1]+x est un carr=C3=A9" est un peu compliqu=C3=A9. On peut =
=C3=A0 la
place tester les quatre carr=C3=A9s possibles. Au lieu de

    for x in restant:
        if ... sequence[-1]+x est un carr=C3=A9 ...:
            cherche (...)

on peut =C3=A9crire

    for carre in [4, 9, 16, 25]:
        candidat =3D carre - sequence[-1]
        if candidat in restant:
            cherche (...)

mais ce n'est pas tr=C3=A8s important pour l'algorithme.

-- Alain.

P/S: cela permet de trouver qu'il n'y a que deux solutions, sym=C3=A9triques