Sujet Précédent Sujet Suivant

Tri

Fermé
LisaH - 4 nov. 2009 à 17:39
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 - 4 nov. 2009 à 22:30
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,

2 réponses

Réponse 1 / 2
loupius Messages postés 697 Date d'inscription dimanche 1 novembre 2009 Statut Membre Dernière intervention 31 décembre 2017 148
4 nov. 2009 à 18:38
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.
0
Réponse 2 / 2
LisaH
4 nov. 2009 à 19:40
:)

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
0
loupius Messages postés 697 Date d'inscription dimanche 1 novembre 2009 Statut Membre Dernière intervention 31 décembre 2017 148
4 nov. 2009 à 20:53
Cela ne m'éclaire pas plus; je n'ai pas d'idée et je passe la main.
Bonne soirée.
0
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 660 > loupius Messages postés 697 Date d'inscription dimanche 1 novembre 2009 Statut Membre Dernière intervention 31 décembre 2017
4 nov. 2009 à 22:30
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 !
0

Discussions similaires

Automatisation du tri google sheet
el -
eloklm75 -

10 réponses
Est-ce que je peux aller chercher un colis à l'agence Chronopost
xXJOSSXx -
MPMP10 -

8 réponses
Que signifie ''Votre colis est arrivé sur son site de distribution'' ?
jouhry113 -
Chanchan -

25 réponses
tri automatque sur excel sans créer de macro
hugofauch -
hugofauch -

2 réponses
Colis aliexpress bloqué "arrivé au centre de distribution"
Lucas909 -
fabul -

3 réponses