Python 3 débutant: Fusionner 2 tableaux déjà triés

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:

---

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.

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é,

Salut,

Citation:

---

Envoyé par Demky

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.

Citation:

---

Envoyé par Demky

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:

---

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

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:

---

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.

Salut,

Pourquoi écrire ce "while" en sortie:

Code:

---

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:

---

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:

---

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

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:

---

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.

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

Code:

---

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

Citation:

---

Envoyé par 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 :
....

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 :mrgreen:

Code:

---

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.

merci pour tout les avis;

oui le but est surtout d'essayer d'apprendre Python et surtout l’algorithmie ; j'ai l'impression que le plus compliqué c'est de réussir a penser de la bonne façon :calim2:

salut,

encore une façon de faire, sans import, sans récursion, mais les données de départ ne sont pas conservées (au pire on les copie au préalable donc) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

while True: if not tab1: tab3 += tab2 break # si tab1 est vide, on rajoute le reste de tab2 et on sort de la boucle if not tab2: tab3 += tab1 break # et réciproquement if tab1[0] < tab2[0]: tab3.append(tab1.pop(0)) # pop() récupère l'élément 0 et l'enlève de la liste dans la foulée else: tab3.append(tab2.pop(0))

---

Bonjour,

Citation:

---

Envoyé par Demky

merci pour tout les avis;

oui le but est surtout d'essayer d'apprendre Python et surtout l’algorithmie ; j'ai l'impression que le plus compliqué c'est de réussir a penser de la bonne façon :calim2:

---

Alors, on te dira que cela s'acquiert avec de la pratique et du temps, ce qui est vrai et un peu faux: aucun livre, cours, etc... ne pourra t'apprendre réellement l'algorithmie, tout au plus, on te donnera des méthodes pour effectuer telle ou telle opération mais ça n'ira guerre plus loin. C'est à toi, par la pratique, d'apprendre à décomposer les problèmes en sous problèmes élémentaires et à force, tu auras ce que l'on appelle le déclic.

Et c'est à partir de ce moment là, qu'il devient intéressant d'acquérir la connaissance des différents types d'algorithmes existant pour un problème donné.

Bon courage, mais ça en vaut la peine :ccool:

Citation:

---

Envoyé par disedorgue

tu auras ce que l'on appelle le déclic.

---

je comprend pas trop ce principe; tous le monde nous a parlé de ça: le formateur; les anciens stagiaires...

On a forcément le déclic un jour ? genre du jour au lendemain on se met a tout comprendre ?
Je n'ai jamais eu ce genre de problème dans aucun métiers mais en même temps, je n'avais jamais eu de job intellectuel avant :oops:

il y a des articles connu qui parle du "déclic" ? ce n'est pas que c'est long mais j'aimerai bien l'avoir avant de passer le diplôme car pour l'instant j'ai un peu peur de l'évolution des choses 8O

edit : j'étais content, j'ai commencé a lire un article sur le déclic, puis à la troisième ligne il y a eu ceci en gras :




Une première définition du déclic pourrait être : la prise de conscience que l'on a intérêt à arrêter sa consommation d'alcool. :weird:

En relisant la discussion, ton algorithme était bon, il y avait juste la sortie de boucle qui était fausse mais là c'est lié à une contrainte algorithmique du langage que tu utilises qui ici est python (là, je vais me faire flinguer par certain en disant ça :aie: ).
Ce que je veux dire c'est que tu as résolu la partie algorithme, tes erreurs semblent plus lié à ta méconnaissance et/ou du manque de pratique du langage.

D'ailleurs, si tu veux un bon entrainement, tu peux essayer de refaire l'exercice mais au lieu du while, essayes d'utiliser le for.

:salut:
Desole si c'est en retard mais tu peux gerer ca tout simplement avec des methodes de l'objet list

1- extend & copy:

Code:

---

1 2 3

tab3 = tab1.copy() # On fait un copie du tableau 1 tab3.extend(tab2) # on etend le tableau 3 a l'aide du tableau 2 tab3.sort()

---

ensuite tu fais

Code:

---

tab3 = list(set(tab3)) # Pour eliminer les doublons (en cas de doublons)

---

Salut,

Citation:

---

Envoyé par cervo

Desole si c'est en retard mais tu peux gerer ca tout simplement avec des methodes de l'objet list

---

Et si vous preniez le temps de lire l'énoncé du problème avant de répondre?

Citation:

---

Envoyé par Demky

On a forcément le déclic un jour ? genre du jour au lendemain on se met a tout comprendre ?

---

Le déclic, c'est quand des paquets de neurones se connectent entre eux pour matérialiser un concept. Çà peut se faire rapidement ou pas: chacun doit avoir une "stratégie d'apprentissage" adaptée. Et puisque, c'est une affaire de neurones, c'est pas en tapant sur son clavier qu'on aura le déclic mais plutôt dans son sommeil ou des phases où on se détend, i.e. on arrête d'y penser.

Citation:

---

Envoyé par Demky

Je n'ai jamais eu ce genre de problème dans aucun métiers mais en même temps, je n'avais jamais eu de job intellectuel avant :oops:

---

Dans les métiers manuels, il faut aussi connecter des neurones pour apprendre des gestes, prendre des repères,... Et si on se lance dans une activité "compliquée", il va aussi falloir apprendre à la décomposer en une séquences d'opérations et s'assurer avant de se lancer de la maîtrise des différentes techniques à utiliser.

- W

Citation:

---

Envoyé par wiztricks

Salut,



Et si vous preniez le temps de lire l'énoncé du problème avant de répondre?

---

Euh....Oooops... manque le petit passage qui demandait de le faire manuellement....

Citation:

---

Envoyé par cervo

Euh....Oooops... manque le petit passage qui demandait de le faire manuellement....

---

"manuellement" ? In fine, c'est toujours la machine qui bosse.

- W