Algo du trisfusion

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

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

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?
 
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;

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

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

<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), ...
 

farid_h

<defunct>
Contributeur
Merci Farid_h, je vais m'entrainer durant le week-end concernant les tableaux à deux dimensions.
Bon courage.

Il n'y a pas de difference fondamentale au tri 1-dimensionnel. Concentres toi plutot a bien comprendre les algos 1-dimensionnels

- Bubblesort (pour debutants)
- Insertsort
- Mergesort
- Quicksort (important en pratique)

et leurs caracteristiques en notation Big-Oh.
 
J'aimerais pouvoir additionner deux tableaux (score et scores2) le hic c'est que ça ne fonctionne pas.
J'ai crée un nouveau tableau vide qui porte le nom de result[]
La fonction que je viens de créer s'appelle printScore je ne parviens pas à comprendre pourquoi les deux tableaux ne s'additionnent pas?

Merci pour votre aide.

PHP:
name = []
goal = []
point = [2,4,6]
score = []
goal2 = []
score2 = []
result = []
 
def demand(nb):
  for i in range(nb):
    name.append(str(input("Enter name n° " + str(i+1) +  " please : ")))
    while True:
      var = int(input("Enter the number of goal (10-100) for " + name[i] +  ": "));
      if var >=10 and var <=100: break
      print(var, " error ! ")
    goal.append(var)
     
  return name, goal;
 
 
def tri1(name, goal):
  for i in range(len(name)-1,0,-1):
    for j in range(i):
      if name[j+1] < name[j]:
        temponame = name[j]
        tempogoal = goal[j]
        name[j] = name[j+1]
        goal[j] = goal[j+1]
        name[j+1] = temponame;
        goal[j+1] = tempogoal
       
  return name, goal
 

def printTri1(name, goal):
  for i in range(len(name)):
    print(name[i] + " \t " + str(goal[i]));
   

def printPoint1(name, point, score):
  for i in range(len(name)):
    print("Name : " + name[i] + " Your score is of " + str(point[i]) + " : " + str(goal[i]) + " goals. ")
  score.append(point[i])
 
 
def demand2(nb):
  for i in range(nb):
    print("Name " + name[i] + " - : ");
    while True:
      var = int(input("Enter the number of goal (10-100) for " + name[i] +  ": "));
      if var >=10 and var <=100: break
      print(var, " error ! ")
    goal2.append(var)
   
  return name, goal, goal2
 
def Tris2(name, goal, goal2):
    for i in range(len(name)-1,0,-1):
      for j in range(i):
        for k in range(j):
           if name[k+1] < name[k]:
             temponame = name[k]
             tempogoal = goal[k]
             tempogoal2 = goal2[k]
             name[k] = name[k+1]
             goal[k] = goal[k+1]
             goal2[k] = goal2[k+1]
             name[k+1] = temponame;
             goal[k+1] = tempogoal;
             goal2[k+1] = tempogoal2;
 
 
def printTri2(name, goal, goal2):
  for i in range(len(name)):
    print(name[i] + " \t " + str(goal[i]) + str(goal2[i]) );
   
   
 
def printPoint2(name, point, score2):
  for i in range(len(name)):
    print("Name : " + name[i] + " Your score is of  " + str(point[i]) + " : " + str(goal2[i]) + " goals. ")
  score2.append(point[i])
 

def printScore(name, score, score2):
  for i in range(len(name)):
    result.append(name[i] + " " + str(score[i] + score2[i]));
  print(result)

 
 
name, goal = demand(3);
tri1(goal, name);
printTri1(name, goal)
printPoint1(name, point, score)


name, goal, goal2 = demand2(3)
Tris2(goal2, name, goal)
printPoint2(name, point, score2)
printScore(name, score, score2)
 
Dernière édition:
Haut