Tri
LisaH
-
Pacorabanix Messages postés 3248 Date d'inscription Statut Membre Dernière intervention -
Pacorabanix Messages postés 3248 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
J'ai un petit souci par rapport aux algorithmes de tri.
En effet, il faudrait trouver un algorithme qui tri un tableau T de taille n et qui contient des 0 et des 1 dans un ordre quelconque et retourner le nombre des 0 et 1 sans les compter explicitement.
Sauf que cet algo doit être linéaire et de complexité spatiale O(1).
J'ai regardé les algo linéaires counting sort, radix sort, bucket sort mais tous ces tris utlisent un 2e tableau et donc de complexité spatiale sup a O(1).
Avez vous une idée de comment je pourrais procéder?
Merci,
J'ai un petit souci par rapport aux algorithmes de tri.
En effet, il faudrait trouver un algorithme qui tri un tableau T de taille n et qui contient des 0 et des 1 dans un ordre quelconque et retourner le nombre des 0 et 1 sans les compter explicitement.
Sauf que cet algo doit être linéaire et de complexité spatiale O(1).
J'ai regardé les algo linéaires counting sort, radix sort, bucket sort mais tous ces tris utlisent un 2e tableau et donc de complexité spatiale sup a O(1).
Avez vous une idée de comment je pourrais procéder?
Merci,
A voir également:
- Tri
- Comment faire un tri personnalisé sur excel - Guide
- Logiciel tri photo - Guide
- Tri turf - Télécharger - Sport
- Votre colis est retenu au centre de tri - Accueil - Arnaque
- En cours de traitement sur le site de tri local ✓ - Forum Consommation & Internet
2 réponses
Ce n'est pas la peine de reposter exactement le même texte que ce matin. Si tu n'as pas eu de réponse, c'est parce que ta question nous laisse perplexe: en effet, comment obtenir le nombre de '0' et de '1' sans les compter explicitement ? Est-on autorisé à les compter implicitement ;-) ?
Bonne continuation.
Bonne continuation.
:)
C'est a dire qu'on peut pas utiliser de compteur pour déterminer les nombre des 0 et 1.
Il s'agit d'utiliser la taille et les indices du tableau
Merci
C'est a dire qu'on peut pas utiliser de compteur pour déterminer les nombre des 0 et 1.
Il s'agit d'utiliser la taille et les indices du tableau
Merci
faire la somme des éléments du tableau ? :)
D'un coté on les compte, mais on ne fait pas un compteur qui s'incrémente lorsqu'un test dit que c'est la chose à compter (différent donc d'un algorithme qui compterait le nombre de "f" dans une chaine de caractère)
Ceci exploite bien le fait qu'il n'y a que des 0 et des 1. La somme donne évidemment le nombre de 1, ensuite pour le nombre de zéros... je te laisse deviner !
D'un coté on les compte, mais on ne fait pas un compteur qui s'incrémente lorsqu'un test dit que c'est la chose à compter (différent donc d'un algorithme qui compterait le nombre de "f" dans une chaine de caractère)
Ceci exploite bien le fait qu'il n'y a que des 0 et des 1. La somme donne évidemment le nombre de 1, ensuite pour le nombre de zéros... je te laisse deviner !