Discussion :

[Vulvulune]

Bonjour,

Pourriez vous me donner une piste pour résoudre le problème suivant:

J'ai une liste (sous forme de pile) de nombres constituées de n éléments dans un ordre aléatoire, que je dois dispatcher dans m autres piles (m < n).

Le but est de trouver un algorithme qui permet de dépiler les éléments de la pile principal pour mettre dans les m autres piles, en faisant en sorte que les nombres se retrouvent dans l'ordre décroissant de leur valeur dans chacune des m piles.

Je sais que suivant les cas, il est impossible d'avoir les valeurs dans l'ordre dans toutes les m piles, mais qu'il y ait le minimum d'"erreurs"... et sans utiliser une pile "poubelle" dans la quelle il y a toutes les erreurs et dans les autres elle soit triée correctement. J'aimerais que le nombre d'erreur soit plus ou moins égal dans chacune.

Pour être clair, une erreur est lorsque la valeur précédente dans la pile m est plus petite que la valeur empilée. (on désire que ce soit dans l'ordre décroissant)

Merci

Valentin

[Trap D]

si je ne me trompe pas, mon algo est O(n ^2), n étant le nombre d'éléments de la pile initiale

Code :

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

1
2
3
4
5
6
7
8
9
 
tant que pile_init est non vide faire
  val <- depiler()
  rechercher dans la liste des piles déjà créées la pile dont le dernier est la plus petite valeur plus grande que val
   si la recherche échoue alors
      creer une nouvelle pile 
   fin si
   empiler val dans la pile trouvée
fin tant que

[Vulvulune]

Merci pour cet algo, je l'ai déjà implémenté mais n'est pas très efficace...

J'ai oublilé de préciser que la pile principal était en fait implémenté sous forme de liste, il est donc possible de prédire les prochaines valeurs pour optimiser les déplacements dans les autres piles...

[Trap D]

J'ai oublilé de préciser que la pile principal était en fait implémenté sous forme de liste, il est donc possible de prédire les prochaines valeurs pour optimiser les déplacements dans les autres piles...

Dans ce cas là, ce n'est plus une pile
Comment est organisé exactement cet "objet" ?

[Vulvulune]

Vi effectivement, mais je parlais de pile car il faut l'utiliser comme tel car l'on dépile les valeurs pour les mettres dans les m autres piles...

Par contre il est implémenté comme un bête tableau, donc on peut le parcourir pour savoir les prochaines valeurs... mais il faut le dépiler dans l'ordre...

Et dans ton algo proposé tu as mis:
si la recherche échoue alors
creer une nouvelle pile
fin si


Mais ça ne joue pas, car je suis limité à un nombre limité de piles, mais pour le début effectivement tant qu'il reste des piles vides c'est utilisable.

Merci

[pseudocode]

J'aimerais que le nombre d'erreur soit plus ou moins égal dans chacune.

On peut maintenir pour chaque pile un "compteur" d'erreurs, et si on ne peut pas mettre un element correctement dans une pile, alors on le met dans la pile qui compte le moins d'erreur.

Par contre il est implémenté comme un bête tableau, donc on peut le parcourir pour savoir les prochaines valeurs...

Pas sûr qu'on puisse trouver une solution optimale sans faire une énumération complète des possibilités. Par contre on doit pouvoir construire une heuristique (par exemple en calculant la probabilité qu'un élément cause une erreur dans une pile)