• En poursuivant votre navigation sur ce site, vous acceptez l’utilisation de cookies de suivi et de préférences

Algo du trisfusion

  • Initiateur de la discussion tadawit
  • Date de début
tadawit

tadawit

VIB
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(t1, t2):
    tfinal = []
    pos2 = 0
  
    for pos1 in range( len(t1) ):
        while pos2 <= len(t2) -1 and t2[pos2] < t1[pos1]:
            tfinal.append( t2[ pos2 ] )
            pos2 = pos2 + 1
        tfinal.append( t1[ pos1 ] )
    if pos2 < len( t2):
        for i in range(pos2, len(t2) ) :
             tfinal.append( t2[ i ] )
                  
    return tfinal

tableau1 = [1, 6, 16, 18, 20, 35, 29]
tableau2 = [3, 5, 12, 17, 23, 28, 99]

print( fusionTrie(tableau1, tableau2) )
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:
farid_h

farid_h

<defunct>
Contributeur
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).
 
tadawit

tadawit

VIB
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).
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(pos2, len(t2) ) :
Merci
 
farid_h

farid_h

<defunct>
Contributeur
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(pos2, len(t2) ) :
Merci
Essayes d'abord ce que range(3,7) donne...
 
tadawit

tadawit

VIB
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.
 
farid_h

farid_h

<defunct>
Contributeur
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.
Je voulais dire, demarres python, et dis lui: range(3,7), et regardesce qu'il te repond. C'est pour comprendre la fonction range().
 
tadawit

tadawit

VIB
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 ?
 
farid_h

farid_h

<defunct>
Contributeur
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?
 
nwidiya

nwidiya

Un Haut Rispansable!
Super Modératrice
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
 
Zayynaab

Zayynaab

VIB
Je vous admire
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
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à
 
tadawit

tadawit

VIB
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.
 
tadawit

tadawit

VIB
@farid_h;

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

PHP:
def trie(t):
    for i  in range( len(t)-1, 0, -1 ):
        for j in range(i):
            if t[j+1] < t[ j ]:
                tempo = t[ j ]
                t[ j ] = t [ j + 1 ]
                t[j + 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
 
farid_h

farid_h

<defunct>
Contributeur
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...)
 
farid_h

farid_h

<defunct>
Contributeur
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

tadawit

VIB
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...)
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?

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].
Comment tu fais pour arriver à [5,4,3] ??? :bizarre:
 
farid_h

farid_h

<defunct>
Contributeur
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:
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

tadawit

VIB
Merci Farid_h, je vais m'entrainer durant le week-end concernant les tableaux à deux dimensions.
 
Haut