Discussion :

[Demky]

Bonjour;

Cela fait plus++ d'une heure que j'essaye de réfléchir sur ça en vain; j'ai 2 tableaux déjà fusionné et je dois les réunir dans un troisième tableau avec en contrainte le fait que :
"On présume que les deux tableaux de départ sont préalablement triés : il est donc irrationnel de faire une simple concaténation des deux tableaux de départ, puis d'opérer un tri"

J'ai tout essayé avec des -1 / +1 et je tombe tout le temps sur le out of range, j'ai compris que c'est du au fait qu'a un moment l'une de mes liste est terminé et que donc la comparaison ne peut plus avoir lieu mais je n'ai aucune idée de comment dire a python que dans ce cas il faut arrêter et ajouter toutes les valeurs de la liste restante.

j'ai essayer de rajouter une deuxième boucle while mais en vain.

Voici le code que j'ai écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11]
tab3 = []
 
tailleTab3 = len(tab1) + len(tab2)
i, j = 0, 0
 
while len(tab3) < tailleTab3 :
    if tab1[i] < tab2[j] :
        tab3.append(tab1[i])
        i += 1
    else:
        tab3.append(tab2[j])
        j += 1
 
print(tab3)

Depuis 5 semaines que je suis en formation j'ai souvent l'impression que je reste bloqué devant des exercices pendant des heures sans pouvoir avancer; comment vous faites pour vous sortir d'une impasse ?
Je commence a me demander si ce n'est pas moi qui suis juste pas fait pour ce travail; a chaque fois qu'on m'explique une solution je la comprend aisément mais pour créer quelque chose à partir de rien je bloque pendant des heures.

merci pour l'aide.

[fred1599]

On pourrait utiliser la méthode insert des listes.

il suffirait d'itérer sur ta liste fusionnée, et de vérifier si l'élément est supérieur ou inférieur selon l'ordre (croissant ou décroissant) à un des éléments de la 3ème liste.

EDIT: Oups, j'avais pas compris l'énoncé,

[wiztricks]

Salut,

comment vous faites pour vous sortir d'une impasse ?

Personnellement, quand c'est comme çà, j'oublie le code et je repars avec papier crayon pour essayer d'imaginer un algorithme qui me semble répondre au problème.
Après, j'essaie de le coder et je teste.

Je commence a me demander si ce n'est pas moi qui suis juste pas fait pour ce travail; a chaque fois qu'on m'explique une solution je la comprend aisément mais pour créer quelque chose à partir de rien je bloque pendant des heures.

Il faut apprendre à chercher sans se précipiter sur le clavier.
Intuitivement, si on part de:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
tab1 = [1, 3, 7]
tab2 = [4, 5 ]
tab3 = []

on voit bien qu'il va falloir parcourir tab1 et tab2 indépendamment donc un faudra deux index i et j.
Donc sur la feuille de papier vous écrivez: i = j = 0
Et il va falloir comparer tab1[0]=1 avec tab2[0]=4.
tab1[0] étant plus petit que tab2[0], on va ajouter tab1[0] à tab3 et incrémenter i.
2ème itération:
On se retrouve à comparer tab1[1]=3 avec tab2[0]=4
Même punition: on ajouter tab1[1] à tab3 et on incrémente i.
3ème itération:
On se retrouve à comparer tab1[2]=7 avec tab2[0]=4
Cette fois c'est tab2[0] qui est plus grand donc on l'ajoute à tab3 et on incrémente j.
4ème itération:
On se retrouve à comparer tab1[2]=7 avec tab2[1]=5
C'est encore tab2[2] qui est plus grand donc on l'ajoute à tab3 et on incrémente j.

Si on continue bourrin, on va s'amuser à comparer un tab1[3] qui n'existe pas, alors qu'en fait, puisque toute la liste tab2 a été consommée, il suffit d'ajouter les éléments restants de tab1 à tab3 et on a fini.

Après on essaie de coder çà. On a bien un while mais la condition de sortie de la boucle sera i < len(tab1) and j < len(tab2). Puis après la boucle on traite les éléments restants.

- W

[Demky]

Merci; j'ai modifier le code grâce a vos instructions et en écrivant ceci :

J'ai mis un deuxième while pour traiter les valeurs du tableau restante car d'après ce que j'ai compris, les deux seule manière de parcourir un tableau sont for et while

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
tab1 = [1, 2, 3, 6, 7, 15]
tab2 = [4, 5, 8, 11, 12, 22, 30]
tab3 = []
 
tailleTab3 = len(tab1) + len(tab2)
i, j = 0, 0
 
while i < len(tab1) and j < len(tab2):
    if tab1[i] < tab2[j] :
        tab3.append(tab1[i])
        i += 1
    else:
        tab3.append(tab2[j])
        j += 1
while len(tab3) < tailleTab3 :
    if i == len(tab1):
        tab3.append(tab2[j])
        j += 1
    elif j == len(tab2):
        tab3.append(tab1[i])
        i += 1

Tout semble fonctionner! J'imagine qu'on doit pouvoir améliorer le code car beaucoup de lignes sont écrites en double.

[wiztricks]

Salut,

Pourquoi écrire ce "while" en sortie:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
while len(tab3) < tailleTab3 :
    if i == len(tab1):
        tab3.append(tab2[j])
        j += 1
    elif j == len(tab2):
        tab3.append(tab1[i])
        i += 1

vous savez que vous êtes sorti du while précedent parce que i == len(tab1) ou que j == len(tab2) et donc qu'il faut ajouter les éléments restants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if i == len(tab1):
    for x in range(j, len(tab2)):
        tab3.append(tab2[x])
elif j == len(tab2):
    for x in range(i, len(tab1)):
        tab3.append(tab1[x])

Si vous savez découper vos listes, çà peut se faire plus simplement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
if i == len(tab1):
    tab3 += tab2[j:]
elif j == len(tab2):
    tab3 += tab1[i:]

L'idée étant que plutôt que d'avoir un block d'itérations while len(tab3) < tailleTab3 plein d'instructions qui ne servent à rien, on pousse les itérations le plus bas possible.
Pour te former, les cours et tutoriels Python : https://python.developpez.com/cours/

- W

[nicolas581]

Bonsoir,

Le but de l'exercice est sans doute d'itérer sur les tableaux mais il y a tout ce qu'il faut dans la bibliothèque standard :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import bisect
import heapq
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11, 12]
tab3 = tab1[:]
 
#solution1
for elem in tab2:
    bisect.insort(tab3, elem)
 
#solution2
tab4 = list(heapq.merge(tab1, tab2))
 
print(tab3)
print(tab4)

Les deux solutions respectent l'énoncé.
La solution1 serait à utiliser pour insérer des éléments d'une structure non triée dans une structure triée, la solution 2 ayant comme pré-requis que les deux structures soient triées.

[oudjira]

dans le cas de deux tableaux triés pour fusionner tu peut faire une fonction récursif comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 
def fusion(tab1, tab2):
	if tab1 ==[] : return tab2
	if tab2 ==[] : return tab1
	if tab1[0]<tab2[0] :
		return [tab1[0]]+fusion(tab1[1 :],tab2)
	else :
		return [tab2[0]]+fusion(tab1,tab2[1 :])
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11, 12]
print("Resultat: fusion(tab1, tab2))
Resultat : [1, 2, 3, 4, 5, 6, 7, 8, 11, 12]

et je crois que à partir de là tu peu faire le reste

[bistouille]

Bonsoir,

Le but de l'exercice est sans doute d'itérer sur les tableaux mais il y a tout ce qu'il faut dans la bibliothèque standard :
....

Les deux solutions respectent l'énoncé.
La solution1 serait à utiliser pour insérer des éléments d'une structure non triée dans une structure triée, la solution 2 ayant comme pré-requis que les deux structures soient triées.

Et surtout inutile d'importer quoi que ce soit, puisqu'on peut nativement combiner 2 listes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab3 = sorted(tab1 + tab2)

Mais j'imagine que le but de Demky était d'écrire un algorithme faisant cela non pas pour réinventer la roue, mais pour s'exercer.