### algoFusion - 21/04/2014 ### ## pileA != pileB != pileC != pileA def fusionne(pileA, nbElementsA, pileB, nbElementsB, pileC, ordreCroissant): while nbElementsA > 0: depile(pileA) continuer = True while nbElementsB > 0 and continuer: empile(pileB) if plus_grand(pileB) != ordreCroissant : depile(pileB) continuer = False else : depile(pileB) deplace_sommet(pileB, pileC) nbElementsB -= 1 empile(pileC) nbElementsA -= 1 while nbElementsB > 0: depile(pileB) empile(pileC) nbElementsB -= 1 def deplaceEtTrie(pileATriee, nbElements, pileCible, ordreCroissant): pileIntermediaire1 = 1 pileIntermediaire2 = 1 while pileIntermediaire1 == pileCible or pileIntermediaire1 == pileATriee: pileIntermediaire1 += 1 while pileIntermediaire2 == pileCible or pileIntermediaire2 == pileIntermediaire1: pileIntermediaire2 += 1 if nbElements == 1 and pileATriee != pileCible: depile(pileATriee) empile(pileCible) if nbElements == 2: if pileATriee == pileCible: if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) deplace_sommet(pileATriee, pileIntermediaire1) empile(pileATriee) depile(pileIntermediaire1) empile(pileATriee) else : if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) empile(pileCible) depile(pileATriee) empile(pileCible) else : depile(pileATriee) deplace_sommet(pileATriee, pileCible) empile(pileCible) if nbElements == 3: if pileATriee == pileCible: if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) deplace_sommet(pileATriee, pileIntermediaire1) empile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) deplace_sommet(pileATriee, pileIntermediaire1) empile(pileATriee) if plus_grand(pileIntermediaire1) != ordreCroissant: depile(pileIntermediaire1) empile(pileATriee) depile(pileIntermediaire1) empile(pileATriee) else : depile(pileIntermediaire1) deplace_sommet(pileIntermediaire1, pileATriee) empile(pileATriee) else: depile(pileIntermediaire1) empile(pileATriee) else : depile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: empile(pileIntermediaire1) depile(pileATriee) deplace_sommet(pileATriee, pileIntermediaire1) empile(pileATriee) if plus_grand(pileIntermediaire1) != ordreCroissant: depile(pileIntermediaire1) empile(pileATriee) depile(pileIntermediaire1) empile(pileATriee) else : depile(pileIntermediaire1) deplace_sommet(pileIntermediaire1, pileATriee) empile(pileATriee) else : empile(pileATriee) else : if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: empile(pileCible) depile(pileATriee) empile(pileCible) depile(pileATriee) empile(pileCible) else : deplace_sommet(pileATriee, pileIntermediaire1) empile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) empile(pileCible) depile(pileATriee) empile(pileCible) else : depile(pileATriee) deplace_sommet(pileATriee, pileCible) empile(pileCible) depile(pileIntermediaire1) empile(pileCible) else : depile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: deplace_sommet(pileATriee, pileCible) empile(pileATriee) if plus_grand(pileATriee) != ordreCroissant: depile(pileATriee) empile(pileCible) depile(pileATriee) empile(pileCible) else : depile(pileATriee) deplace_sommet(pileATriee, pileCible) empile(pileCible) else : empile(pileIntermediaire1) depile(pileATriee) deplace_sommet(pileATriee, pileCible) empile(pileCible) depile(pileIntermediaire1) empile(pileCible) if nbElements > 3: # on sépare en deux piles triées. deplaceEtTrie(pileATriee, nbElements // 2, pileIntermediaire1, not ordreCroissant) deplaceEtTrie(pileATriee, nbElements - nbElements // 2, pileIntermediaire2, not ordreCroissant) fusionne(pileIntermediaire1, nbElements // 2, pileIntermediaire2, nbElements - nbElements // 2, pileCible, ordreCroissant) def algoFusion(): #print (""**** LANCEMENT ****"") #affiche_piles() #print (""debut de l'algo"") nombreTotalElements = nombre_element(1) if nombreTotalElements == 2: if not plus_grand(1): echange_sommet(1) if nombreTotalElements == 3: if not plus_grand(1): echange_sommet(1) depile(1) plop = False if not plus_grand(1): echange_sommet(1) plop = True empile(1) if plop: if not plus_grand(1): echange_sommet(1) if nombreTotalElements > 3: cree_pile() cree_pile() deplaceEtTrie(1, nombreTotalElements, 1, True) #print (""fin de l'algo"") #affiche_piles() return ### programme principal ### affiche_piles() algoFusion() affiche_piles()