1. En poursuivant votre navigation sur ce site, vous acceptez l’utilisation de cookies de suivi et de préférences
    Rejeter la notice

Algo du trisfusion

Discussion dans 'Informatique - Mobile - Jeux' créé par tadawit, 3 Juillet 2017.

Bonjour, Je rencontre des difficultés concernant la compréhension d'un algorithme qui permet de fusionner deux tableaux. Voici l'algo: def...

  1. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Bonjour,

    Je rencontre des difficultés concernant la compréhension d'un algorithme qui permet de fusionner deux tableaux.

    Voici l'algo:
    PHP:
    def fusionTrie(t1t2):
        
    tfinal = []
        
    pos2 0
      
        
    for pos1 in rangelen(t1) ):
            while 
    pos2 <= len(t2) -and t2[pos2] < t1[pos1]:
                
    tfinal.appendt2pos2 ] )
                
    pos2 pos2 1
            tfinal
    .appendt1pos1 ] )
        if 
    pos2 lent2):
            for 
    i in range(pos2len(t2) ) :
                 
    tfinal.appendt2] )
                      
        return 
    tfinal

    tableau1 
    = [161618203529]
    tableau2 = [351217232899]

    print( 
    fusionTrie(tableau1tableau2) )
    Voici comment j’interprète le code:

    1) On définit la fonction en ajoutant deux paramètres (qui sont les deux tableaux)
    2) tfinal = [] , est un tableau qui fusionnera les éléments des deux tableaux
    3) pos2 , représente la position 2 elle est initialisée à 0
    -----

    4) Ensuit on parcours la première position dans l'ensemble du premier tableau
    5) Tant que la position 2 est plus petit que les éléments du deuxième tableau et que la position2 du tableau2 est plus petite que la position1 du tableau1:

    que signifie le -1 ???

    6) alors on ajoute dans le tableau final l'élément du tableau2)
    7) on incrémente
    8) dans le cas contraire on ajoute la position 1 du tableau 1 au tableau final

    ---

    9) si la position2 est plus petite que les éléments du tableau 2
    10) on parcours le tableau et ???? Je ne comprends pas pos2, len(t2)

    Merci d'avance :)
     
    Dernière édition: 3 Juillet 2017
  2. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    Le -1, c'est facile. Regardes:

    Code:
    $ python
    Python 2.7.13 (default, Jan  7 2017, 01:23:40) 
    [GCC 4.2.1 Compatible FreeBSD Clang 3.8.0 (tags/RELEASE_380/final 262564)] on freebsd11
    Type "help", "copyright", "credits" or "license" for more information.
    >>> t1 = [111,222,333]
    >>> t1
    [111, 222, 333]
    >>> len(t1) 
    3
    >>> t1[0]
    111
    >>> t1[1]  
    222
    >>> t1[2]
    333
    >>> t1[3]
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    IndexError: list index out of range
    >>> t1[len(t1)]
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    IndexError: list index out of range
    >>> t1[len(t1)-1]
    333
    >>> len(t1)-1
    2
    
    Tu vois?

    Comme l'array commence a partir de l'index 0, l'index du dernier element est len(t1)-1, en non len(t1).
     
    Septime et tadawit aiment ça.
  3. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Ah j'ai compris merci ! C'est simple effectivement.

    Par contre je n'ai pas compris pos2 dans la dernière itération ??? A quoi sert cette dernière boucle ?

    PHP:
    for i in range(pos2len(t2) ) :
    Merci
     
  4. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    Essayes d'abord ce que range(3,7) donne...
     
    tadawit apprécie ceci.
  5. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Ceci donne:
    [1, 3, 5, 6, 12, 16, 17, 18, 20, 23, 28, 35, 29, 17, 23, 28, 99]
    Visiblement il trie quelques éléments mais pas tous.
     
  6. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    Je voulais dire, demarres python, et dis lui: range(3,7), et regardesce qu'il te repond. C'est pour comprendre la fonction range().
     
    Septime apprécie ceci.
  7. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Ah ok j'avais pas compris lol , j'ai déjà travaillé quelques fois avec la function range()
    => [3, 4, 5, 6]

    Donc la variable pos2 va boucler sur le deuxième tableau ?
     
  8. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    L'index pos2 a deja ete avance jusqu'a une certaine position. Cette boucle ne fait que copier le reste des elements de t2 a partir de pos2 vers tfinal. L'algorithme semble assumer que le slice t2[pos2:] est deja trie?
     
    tadawit apprécie ceci.
  9. nwidiya

    nwidiya Super Modératrice

    Inscrit:
    25 Décembre 2002
    Messages:
    115 552
    Likes:
    95 861
    Je vous admire :D
    Déjà j'ai lu le titre "algo" je croyais que c'était un truc en espagnol genre "quelque chose"...


    bravo! Je ne comprends rien à tout ça mais j'admire LOL
     
    Shahzadeh, tadawit et farid_h aiment ça.
  10. Zayynaab

    Zayynaab VIB

    Inscrit:
    13 Janvier 2014
    Messages:
    7 139
    Likes:
    11 315
    c'est simple pourtant , il faut juste une peu de rationalisme et considérer que 1 + 1 = A2
    le reste coule de source ;)




























    pschkkhhhhhh:desole: :pxD
    je ne suis plus là
     
    nwidiya apprécie ceci.
  11. nwidiya

    nwidiya Super Modératrice

    Inscrit:
    25 Décembre 2002
    Messages:
    115 552
    Likes:
    95 861
    Je t'ai crue al masskhota :D
     
    Zayynaab apprécie ceci.
  12. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Merci pour tes explications maintenant je comprends mieux pour cette partie.
    Il y a en fait une fonction qui va fusionner les deux tableaux et une autre qui va les trier.
    Je te montrerais si tu veux bien l’algo pour le triage ce soir en rentrant du boulot il y a aussi deux, trois petits éléments qui m’échappent.
     
    farid_h apprécie ceci.
  13. Zayynaab

    Zayynaab VIB

    Inscrit:
    13 Janvier 2014
    Messages:
    7 139
    Likes:
    11 315
    wayylii ? :D toi t as fait littéraire non ? :p
     
    nwidiya apprécie ceci.
  14. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    Alors, @tadawit, tu fais des progres avec Mergesort?
     
    tadawit apprécie ceci.
  15. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    @farid_h;

    Je ne comprends pas entièrement l'algo pour le triage.

    PHP:
    def trie(t):
        for 
    i  in rangelen(t)-10, -):
            for 
    j in range(i):
                if 
    t[j+1] < t]:
                    
    tempo t]
                    
    t] = ]
                    
    t[1] = tempo
        
    return t
    Je pense que la première itération permet de parcourir le tableau1 précédemment ?
    Je ne comprends pas le -1,0,-1

    Ensuite on parcours le second tableau:
    Après je ne comprends pas la condition qui est donné j+1 est l'élément du premier tableau ou du deuxième ?

    Merci d'avance
     
  16. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    La boucle exterieure (i) traverse t a l'envers du dernier element jusqu'au premier.

    La boucle interieure (j) traverse t du debut jusqu'a l'element qui precede t(i).

    Si les elements adjacents t(j) et t(j+1) sont dans le mauvais ordre, ils seront echanges.

    (J'ai du remplacer [ par ( et ] par ), car sinon ca aurait donne des italiques...)
     
    tadawit apprécie ceci.
  17. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    range(begin, end, increment) donne une liste [begin, begin+increment, begin+2*increment, ..., end).

    Par exemple, range(5, 2, -1) donne [5, 4, 3]; range(5, 10, 2) donne [5, 7, 9].
     
    tadawit apprécie ceci.
  18. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Merci pour tes explications, je vais les noter dans ma doc.
    Par contre je suppose que pour les tableaux à deux dimensions c'est presque pareille?

    Comment tu fais pour arriver à [5,4,3] ??? :bizarre:
     
  19. farid_h

    farid_h Contributeur

    Inscrit:
    23 Juillet 2006
    Messages:
    34 294
    Likes:
    27 941
    1/ meme quand t'as plusieurs dimensions, tu faits toujours des comparaisons sur une dimension, et tu echanges des rows.

    2/ 5=5+0*(-1), 4=5+1*(-1), 3=5+2*(-1), ...
     
    tadawit apprécie ceci.
  20. tadawit

    tadawit VIB

    Inscrit:
    13 Avril 2014
    Messages:
    6 474
    Likes:
    2 532
    Merci Farid_h, je vais m'entrainer durant le week-end concernant les tableaux à deux dimensions.
     
    farid_h apprécie ceci.