Re: Panne en Python...

Liste des GroupesRevenir à fcl python 
Sujet : Re: Panne en Python...
De : alain (at) *nospam* universite-de-strasbourg.fr.invalid (Alain Ketterlin)
Groupes : fr.comp.lang.python
Date : 28. Sep 2022, 16:11:13
Autres entêtes
Organisation : Université de Strasbourg
Message-ID : <87zgejwpvi.fsf@universite-de-strasbourg.fr.invalid>
References : 1
User-Agent : Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
Dominique <zzz@aol.com> 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".
>
J'ai créé une liste (resu) avec chaque couple susceptible de me donner
un carré parfait :
>
liste=[2,14,11,5,8,12,6,3,1,9,7,13,5,4,10,15]
resu=[]
deb=[x for x in range(1,16)]
fin=[x for x in range(1,16)]
for i in deb:
    for j in fin:
        tot=i+j
        tot1=[i,j]
        tot1.sort()
        if tot1 not in resu and i!=j and tot**.5==int(tot**.5):
            resu.append(tot1)
>
Je ne suis pas sûr d'être parti dans la bonne direction.

En fait, pas vraiment. Là tu cherches les couples de nombres formant un
carré, mais le problème principal dans cet exercice c'est d'enchaîner
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 éléments et tu vérifies qu'ils sont
différents, parce que tu veux des couples (i,j) avec i<j. Autant générer
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épondre à
la question ? Si non, quelle piste me faudrait-il explorer ?

Je ne vois pas de raison de penser que 1) il y a forcément une solution,
et 2) on peut directement déterminer la solution (si elle existe donc).
J'en conclue qu'il faudra chercher, c'est-à-dire essayer d'enchaîner les
nombres, de toutes les façons possibles, et de voir si on trouve une
solution. C'est donc un problème combinatoire.

(Note que si il y a une solution, alors il y en a au moins une
deuxième -- qui est la liste inversée.)

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

Quand on cherche comme cela parmi plein de possibilités, il faut
s'imaginer en plein milieu de la recherche : on a déjà enchaîné 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ébut séquence = [], et restant = {1,...,15}. On va essayer toutes
les premières étapes. 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érarchie de cas à essayer :

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

Note que c'est vraiment une grande hiérachie, 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ête ? Déjà, quand on est bloqué
(perdu). Et aussi quand on a tout essayé. Quand est-ce qu'on a trouvé
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ées, 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 à la place une fonction
récursive, qui va parcourir tout l'arbre des possibilités. On tous les
éléments :

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é ...:
                cherche (sequence+[x], restant-{x}) # sous-cas

Attention : cette fonction utilise le dernier élément de sequence, il
faut donc l'appeler avec toutes les séquence de longueur 1 possibles

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

Ou alors on intègre cela à la fonction, qui devient

def cherche (sequence, restant):
    if len (sequence) == 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ée. On peut faire des choses pour simplifier. Par exemple, le
test "sequence[-1]+x est un carré" est un peu compliqué. On peut à la
place tester les quatre carrés possibles. Au lieu de

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

on peut écrire

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

mais ce n'est pas très important pour l'algorithme.

-- Alain.

P/S: cela permet de trouver qu'il n'y a que deux solutions, symétriques

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