Path: ...!news.mixmin.net!aioe.org!K7PIs9tCGQ+WHJa7e6BylQ.user.46.165.242.75.POSTED!not-for-mail From: Alain Ketterlin 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: 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 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 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