[algo] duplicats dans un tableau

duplicats dans un tableau [algo] - Algo - Programmation

Marsh Posté le 15-03-2005 à 19:48:47    

Hello,
 
Encore un exo d'algo :)
 
Etant donné un tabelau de N entiers, entre 1 et N.
Comment determiner si ce tableau possède des duplicats.
 
 
Sylvain

Reply

Marsh Posté le 15-03-2005 à 19:48:47   

Reply

Marsh Posté le 15-03-2005 à 20:07:07    

on est pas mardi ?

Reply

Marsh Posté le 15-03-2005 à 20:08:22    

Ca sent le partiel à plein nez :)


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 20:27:46    

non non, pas de partiels en vue :)
 
en fait pu de partiels car j'ai fini mes etudes,  
mais je fais quelques revisions d'algo :/


Message édité par slvn le 15-03-2005 à 20:28:24
Reply

Marsh Posté le 15-03-2005 à 21:11:04    

slvn a écrit :


Etant donné un tableau de N entiers, entre 1 et N.
Comment determiner si ce tableau possède des duplicats.


 
Fais la somme du tableau et si elle est differente de N*(N+1)/2 y a un duplicat :whistle:


Message édité par Joel F le 15-03-2005 à 21:11:32
Reply

Marsh Posté le 15-03-2005 à 21:42:15    

slvn a écrit :


Etant donné un tabelau de N entiers, entre 1 et N.
Comment determiner si ce tableau possède des duplicats.


 
:D

Reply

Marsh Posté le 15-03-2005 à 22:00:03    

oui et ?  
 
le tableau 1 5 3 2 4 a pour somme 15
le tableau  1 1 3 4 4 a pour somme 13 != 15 duplicat
etc ... ca me parait trivial.
 
apres pour TROUVER les duplicats ben parcours avec double pointeur du tableau. Tu part de l'indice i que tu compare avec la valeur a l'indice j tant que t[i] != t[j], si tu arrive au bout du tableau, i++ et on repart de i à fin ...
 

Reply

Marsh Posté le 15-03-2005 à 22:09:43    

bah si tu prend pas un bon exemple ca peut pas marcher :D
 
1 2 3 4 5 => somme == 15
1 1 4 4 5 => somme == 15

Reply

Marsh Posté le 15-03-2005 à 22:13:12    

je précise que j'ai trouvé l'exo sous cette forme (avec un S). Ca parait pas simple s'il y a en effet plusieurs duplicats.
 
Peut etre qu'il y aurait en tout 1 duplicat, au quel cas, faire la somme est ok.

Reply

Marsh Posté le 15-03-2005 à 22:26:01    

Je suppose qu'on a pas droit à une méthode brute force ?

Reply

Marsh Posté le 15-03-2005 à 22:26:01   

Reply

Marsh Posté le 15-03-2005 à 22:35:42    

On trie le tableau et on fait un parcours du tableau en verifiant que l'indice est egal à Tab[indice]-1 (en supposant que c'est indicé à partir de 0) et dés que c'est pas le cas on est sur un doublet.
 
Sachant qu'on peut trier un tableau en O(n*log(n)), c'est donc la complexité de cet algo dans le pire des cas.


Message édité par Chronoklazm le 15-03-2005 à 22:40:37

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 22:35:51    

bah la methode force brute est pas tres tres compliqué :)
 
un tri par heapsort: O(n*log(n))
puis trouver les duplicats: O(n)
 
Enfin peut etre que y a pas mieux :/

Reply

Marsh Posté le 15-03-2005 à 22:36:17    

arf grillé :)

Reply

Marsh Posté le 15-03-2005 à 22:41:13    

On peut surement descendre a O(n).


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 23:01:02    

oui,  
Pour O(n), on peut utiliser un tableau a coté pour comptabiliser chaque valeur, et afficher des que l'on repete une de ces valeurs.
 
il y a donc O(n) pour l'algo, et O(n) d'espace :/

Reply

Marsh Posté le 15-03-2005 à 23:41:19    

On peut rester constant en espace. On pas vraiement besoin de trier je pense.
En supposant qu'on indice à partir de 0, on boucle en permutant Tab[Tab[i]-1] et Tab[i], ca prend O(n) dans le pire des cas, puis on a plus qu'a faire une recherche de doublons en O(n).
 
Donc le tout est en O(n)  :pt1cable:
 
PS: ca marche pas trop mais l'idée est là, j'en suis sur!


Message édité par Chronoklazm le 15-03-2005 à 23:42:48

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 00:03:55    

si ouais ca marche mais ca utilise o(n) espace:D
 
Je l'ai pas precisé, mais il y avait trois contraintes dans l'énoncé:
O(n) algo, O(1) espace, ne pas détruire le tableau initial?
(modifier/démodifier le tableau, est-ce le detruire :??:)
 
(remarque, la question était: existe-il un algo O(n), O(1) espace et ne détruisant pas le tableau initial)

Reply

Marsh Posté le 16-03-2005 à 00:06:12    

ca doit etre faisable, en modifiant le tableau, et puis en le demodifiant je pense :/
 
->O(n) pour le modifier, trouver les duplicats, O(n) pour le demodifier

Reply

Marsh Posté le 16-03-2005 à 00:09:16    

Pkoi O(n) en espace, je pige pas ?
 
A mon avis "ne pas detruire le tableau initial" veut dire qu'on doit pouvoir retrouver les memes elements du tableau de depart à chaque instant de l'algo (pas de incr ou de decr).
Si on ne peut pas faire de permutations le O(1) en espace on peut l'oblier.


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 00:11:03    

Ca veut dire quoi "demodifier" ? :)


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 00:21:30    

C'est pas vraiment O(n) d'espace que tu demandes qu'on t'alloue. Mais quand tu utilises le tableau lui-meme pour reperer tes eventuels doublons, ca veut dire que tu utilise cet espace ...
 
quand tu permutes Tab[Tab[i]-1] et Tab[i] tu modifies le tableau...le dé-modifier ca serait le faire revenir dans son état initial :)
 
 
En fait, voula une idee que tu viens de me donner en modifiant/demodifiant le tableau:

Code :
  1. for(i=0;i<N;i++){
  2.   tab[tab[i]] += N+1
  3. }
  4. for(i=0;i<N;i++){
  5. if( tab[i] > 2*N +1 ) 
  6.     printf("%d est un duplicat\n",tab[i]);
  7.   tab[i] %= (N+1); //clean up :)
  8. }


Message édité par slvn le 16-03-2005 à 00:22:09
Reply

Marsh Posté le 16-03-2005 à 00:37:17    

slvn a écrit :

C'est pas vraiment O(n) d'espace que tu demandes qu'on t'alloue. Mais quand tu utilises le tableau lui-meme pour reperer tes eventuels doublons, ca veut dire que tu utilise cet espace ...


 
Mais il faut bien un espace non ?  :??:  


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 00:39:26    

Et puis pour retrouver le tableau de depart on peut faire une fonction et utiliser l'appel par copie par defaut :D


Message édité par Chronoklazm le 16-03-2005 à 00:39:45

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 00:40:41    

Dans l'enonce ils disaient O(n) pour l'algo.
O(1) pour l'espace (ie constant par rapport a n).
et ne pas detruire le tableau.
 
Ambigu -> on peut ne pas detruire le tableau si on le modifie et puis si on le de-modifie.  
 
Je trouve que ca ressemble un peu a O(n) en espace, mais pas tout a fait car on a pas fait de "memory allocation"

Reply

Marsh Posté le 16-03-2005 à 00:41:09    

arf :D

Reply

Marsh Posté le 16-03-2005 à 00:43:20    

Tu fait une incrementation sur un element du tableau, donc tu le detruit ... je sais pas si on peut appeler ca un effet de bord sur le tableau.
 
C'est quoi pour toi O(1) en espace ? :)


Message édité par Chronoklazm le 16-03-2005 à 00:44:24

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-03-2005 à 01:24:54    

ouais il peut y avoir un effet de bord, s'il y a overflow :/
remarque qu'on ne detruit pas le tableau si on l'enleve apres..
 
De maniere reccursive il y a surement un moyen simplement de proceder avec des permutations tab[i] / tab[tab[i]] de trouver le premier des duplicats. (mais bon utilisations de la stack a fond :/).
 
O(1) en espace, ca veut dire constant par rapport a N.
c'est a dire une allocation constante sur la pile(pas de reccursion), ou bien une allocation constante sur le tas(malloc qui ne depend pas de N).
 

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed