Bonjour,
Je voudrais savoir comment vous procéderiez pour savoir combien de nombres différents il y a dans un tableau d'entier, un tableau de 100 chiffres dans mon cas ?
Merci.
Version imprimable
Bonjour,
Je voudrais savoir comment vous procéderiez pour savoir combien de nombres différents il y a dans un tableau d'entier, un tableau de 100 chiffres dans mon cas ?
Merci.
Tu n'as même pas une petite approche du problème à proposer ?
Genre :
Bon, reste à définir les bornes, l'indice de démarrage, etc.Code:
1
2
3
4 Trier le tableau Parcourir le tableau : compteur à 1 Avancer d une case Si le nombre est différent du précédent, alors incrémenter compteur
Je ne prétendrai pas te donner la correction en C, mais déjà commence avec un algorithme, et pose tes données. Tu verras que tu as besoin d'un tableau, donc de ce qui le définit, de ce qui permet de le parcourir, d'un compteur pour le nombre de nombres différents, etc. Pose ta méthode de résolution, et ce qu'elle induit comme données / structures de données, c'est la base.
Bonjour
Sans trier le tableau (ce qui peut déjà poser un problème pour qui n'est pas habitué), c'est aussi faisable mais le temps de traitement devient alors exponentiel (ceci dit, le temps du tri peut aussi être exponentiel donc à voir ce qui est mieux au cas par cas...)
Pour chaque nombre placé dans une case "i" de ton tableau, tu regardes s'il se trouve dans une des cases précédentes (de 0 à "i-1")
S'il n'y est pas, tu incrémentes ton compteur.
J'avais déjà une approche mais je cherche toujours à faire trop compliqué, je n'avais pas penser à trier le tableau avant de faire les comparaisons, ça devient évident quand on me le dit.
Merci pour vos réponses.
Tu as une solution plus technique avec une "table de hashage" (comme la collection map de la stl) avec un couple (clef: nombre, valeur: compteur) :mrgreen:
L'algo devient simple :mrgreen:: tu parcours tout ton tableau, tu récupères le compteur associé (*) et tu l'incrémentes
* -> il faut faire attention à la première insertion: si elle est automatique ou pas et, dans ce cas, la valeur du compteur.
Cela se complique effectivement: le tri sur place est une bonne solution alors :mrgreen:
Alors un set, et on prend son nombre d'éléments. Mais pas en C :aie:
Ou alors passer par un arbre binaire équilibré: la recherche d'un nombre est en log de 2.
Non le tri sur place est plus simple :mrgreen:
Ce n'est pas parce que tu es en C que tu ne peux pas en faire autant.
Prends deux tableaux de la taille de ta donnée. ajoute un marqueur de taille.
Voila deux "vectors" (en beaucoup moins sécurisé)
dans le premier, tu mets les nombres rencontré, dans le second la quantité.
A chaque nombre de la donnée, tu le cherche dans les rencontres, et tu incrémente la quantité correspondante.
à peine mieux, tu prévois une struct groupant le nombre et sa quantité.
Mieux, peut-être une liste chainée de ces structs.
Partant de cette liste, tu peux faire un arbre de recherche.
Ca peut-être très simple d'avoir un arbre raisonnablement équilibré si tu as une vague idée des nombres de la donnée: min, max et estimation du milieu.
Il y a une solution en O(n) (une simple boucle) si le domaine de tes valeurs est petit, c'est à dire si toutes valeurs dans ton tableau est compris entre 0 et N. Tu fais un tableau inside[N], et tu passes une première boucle en faisant inside[tableau[i]] = 1. Tu fais une deuxième boucle qui compte combien de cases de "inside" sont à 1 et voilà. C'est un exemple d'algo où tu utilises la mémoire pour gagner en vitesse.
J'aime bien ta solution Trademark.
Pour ajouter un point sur une réponse précédente il est tout à fait possible d'utiliser une table de hash en C (et heureusement d'ailleurs ;)). http://man.developpez.com/man3/hsearch/
J'y avais songé aussi mais elle est basée sur l'hypothèse que chaque nombre du tableau initial est compris entre 0 et 100 et j'ai jugé cette hypothèse trop incertaine...
Oui je me suis mal exprimé. Je ne voulais pas dire que ce n'était pas faisable en C, je voulais dire que les hashtables n'existent pas en natif en C et donc que celui qui veut les utiliser devra soit commencer par les créer, soit intégrer dans son code une librairie déjà créée pour ça...
Il est d'ailleurs bien entendu que les hashtables dans les autres langages (C#, Python) sont elles-mêmes faites à partir d'outils de base tels que ceux qu'on a dans le C...
Une méthode avec un très bon rendement est d'utilisé l'ajout de node dans un arbre binaire de recherche.
Si la valeur est déjà dans l'arbre tu passe à la suivante sinon tu ajoute un node.
http://chgi.developpez.com/arbre/binaire/
Dans le cas général la solution du tri est à mon avis à la fois la plus performante et la plus simple à coder puisqu'en C standard on a déjà qsort().