|
|
Bonjour,  
S'il vous plait j'ai quelques question en algorithmique hyper interessantes pour moi pourriez vous me repondre un peux en detail:
Etant donné T(1), t(2),..., T(n) un tableau de n entier, on veut résoudre le problème suivant:
(P) Existe-t-il i et j dans {1,2,...n} tels que T(i)=T(j) ?
1)Ecrire (avec justification) un algo resolvant (P) en O(n^2) et donnant une solution s'il en existe
2) Montrer (principe, preuve, ecriture de l'algo) que l'on peut resoudre (P) en O(nlogn) et obtenir uen solution, s'il en existe (ainsi que le nombre de paires de solutions).
3) Soit N un entier positif fixé. Montrer que si T(1), t(2),...,T(n) sont des entiers positifs au plus egaux à N, on peut resoudre (P) en O(n+N)
4) Soit S un entier, considerons le probleme:
(P1) Existe-t-il i et j dans {1,2,...n} tels que T(i)+T(j)=S ?
Montrer que toute méthode de résolution de (P) permet de résoudre (P1) via une petite adaptation
Je vous remercie infiniment. 
|
1
![[:jandre:1]](/data/globaldata/usmilies/jandre-1.gif "[:jandre:1]")
Il faut mieux en mettre plus que moins ![[:KiWin:1]](/data/globaldata/usmilies/kiwin-1.gif "[:KiWin:1]")
