High-Tech Santé Médecine Droit-Finances

Test

Netbook HP mini 110

Rechercher : dans
Par :

Tri

Dernière réponse le 4 nov 2009 à 22:30:17 LisaH, le 4 nov 2009 à 17:39:16 
 Signaler ce message aux modérateurs

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,

Configuration: Windows Vista
Firefox 3.5.4

Meilleures réponses pour « tri » dans :
SQL - Tri Voir Tri des résultats Il est possible en SQL d'organiser les résultats grâce à la clause ORDER BY. La clause ORDER BY est suivie des mots clés ASC ou DESC, qui précisent respectivement si le tri se fait de manière croissante (par défaut) ou...
Tri par fusion - récursivité- Voir Voici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par fusion : Procedure Tri_Fusion (Var t : TAB; g, d : integer); Var m, i, j, k : integer; s : TAB; Begin If d > g Then ...
Tri à bulles -récursivité- Voir Voici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri à bulles : Procedure Tri_bulles (var t : TAB; n : integer); Var i, aux : integer; Function Trier (t : TAB; n : integer) : Boolean; ...
Pascal - Tri par insertion - Récursivité- VoirVoici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par insertion : Procedure Tri_Ins (Var t: TAB; n: integer); Var aux,i : integer; begin If n > 1 Then begin ...
Tri Shell -Recursive- VoirVoici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri Shell : Procedure Tri_Shell_Rec (Var t: TAB; n,h : integer); Var aux,i : integer; begin If h > 0 Then Begin If n > h...
[Excel] Trier sur les lignes (horizontalement), non les colonnes VoirMicrosoft Excel est configuré par défaut pour réaliser un tri sur les colonnes (Données / Trier). Pour trier les données horizontalement, il suffit de sélectionner les données à trier, puis de cliquer sur le bouton Options et, dans le panneau...
Posez votre question Répondre

1

loupius, le 4 nov 2009 à 18:38:59

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.

   
Répondre à loupius

2

LisaH, le 4 nov 2009 à 19:40:56

:)

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

   
Répondre à LisaH

3

loupius, le 4 nov 2009 à 20:53:07

Cela ne m'éclaire pas plus; je n'ai pas d'idée et je passe la main.
Bonne soirée.

   
Répondre à loupius

4

 Pacorabanix, le 4 nov 2009 à 22:30:17

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 !

   
Répondre à Pacorabanix
Posez votre question Répondre
Ils ont besoin de votre aide
Collection CommentÇaMarche.net