distance euclidienne séparant deux points Une méthode deux points les plus proches dans un tableau t consiste cisse est comprise entre xmin et xmax
| Previous PDF | Next PDF |
[PDF] Les deux points les plus proches - Normale Sup
distance euclidienne séparant deux points Une méthode deux points les plus proches dans un tableau t consiste cisse est comprise entre xmin et xmax
[PDF] Les deux points les plus proches - Inria
distance euclidienne séparant deux points Une méthode deux points les plus proches dans un tableau t consiste cisse est comprise entre xmin et xmax
[PDF] 3. Dossier pédagogique 3.4. BAC Pro EIE
[PDF] 3. Élaboration et application en sûreté nucléaire de la base
[PDF] 3. Entwicklung der Rechtslage - Fachschaft Jura
[PDF] 3. ÉVALUATION DE LA DOULEUR CHEZ LA PERSONNE ÂGÉE - Santé Et Remise En Forme
[PDF] 3. Explorer le disque dur / Agir sur son contenu
permettant de d´eterminer les deux points les plus proches dans un tableautconsiste `a consid´erer successivement tous les couples de points possibles, ce qui peut se faire facilement `a l"aide de deux bouclesfor. IQuestion 7Adaptez les fonctionsselettride sorte qu"elle prennent ´egalement en argument une fonction implantant une relation d"ordre (commeordre xou ordre y). IQuestion 6 lettri t = letn = vect length tin fori = 0to(n-1)do letk = sel t i (n-1)in swap t i k done;
[PDF] 3. Élaboration et application en sûreté nucléaire de la base
[PDF] 3. Entwicklung der Rechtslage - Fachschaft Jura
[PDF] 3. ÉVALUATION DE LA DOULEUR CHEZ LA PERSONNE ÂGÉE - Santé Et Remise En Forme
[PDF] 3. Explorer le disque dur / Agir sur son contenu
IMPSI - Option Informatique
Ann´ee 2001, Deuxi`eme TP Caml
Vincent Simonet (http://cristal.inria.fr/~simonet/)Les deux points les plus proches
Lors de cette s´eance, nous allons nous int´eresser au probl`eme suivant : ´etant donn´e un ensemble de points du plan, indentifier le couple de points les plus proches au sens de la distance euclidienne. Ce type d"algorithme voit son utilit´e dans les transports a´eriens ou maritimes par exemple. Nous repr´esenterons un point en Caml par un couple de flottants(x,y)repr´esentant ses coordonn´ees dans un rep`ere orthonorm´e. L"ensemble des points consid´er´es sera quant `a lui stock´e dans un tableaut. Nous supposerons toujours que tous les couples stock´es danstsont distincts. OO _ __ x 01 Une premi`ere solution
Consid´erons deux pointspetp?de coordonn´ees res- pectives (x,y) et (x?,y?). Leur distance euclidienne est donn´ee par la formule?p-p??=p (x-x?)2+ (y-y?)2. IQuestion 1´Ecrivez une fonctiondistqui calcule la distance euclidienne s´eparant deux points. Une m´ethodeIQuestion 2´Ecrivez une fonctionplus
prochesqui prend pour argument un tableau de pointstet retourne un couple de points((x,y),(x?,y?))situ´es `a une distance minimale l"un de l"autre.Vous pourrez
- Commencer par cr´eer une r´ef´erenced(initialis´ee par exemple avecdist t .(0) t.(1)) qui contiendra tout au long du d´eroulement de l"algorithme la plus petite dis- tance trouv´ee; ainsi que deux r´ef´erencessietsjconte- nant les indices des points qui permettent d"atteindre cette distance. - Utiliser deux boucles imbriqu´ees pour consid´erer tous les couples de points communs.- Mettre `a jour les trois r´ef´erences `a chaque fois qu"un couple(i,j)tel que?t.(i)-t.(j)?2 Tri d"un tableau Soitt= [|x0;x1;...;xn-1|] un tableau. Triertconsiste `a permuter le contenu des cases du tableautde fa¸con `a ob- x L"algorithme detri par s´electionadopte le principe sui- vant : pourivariant de 0 `an-2, chercher l"indicek≥i de la case de la partie du tableau situ´ee `a droite de la caseicontenant le plus petit ´el´ement; puis permuter le contenu des casesketi. c ?Vincent Simonet 2001 Ce document est distribu´e selon les termes de la GNU Free Documentation License. Par exemple, pour trier le tableau [|4;3;1;2|], on passe par les ´etapes suivantes :[|4;3;1;2|]i= 0k= 2[|1;3;4;2|]i= 1k= 3 [|1;2;4;3|]i= 2k= 3 [|1;2;3;4|]IQuestion 4´Ecrivez une fonctionswapqui prend
pour argument un tableaut, deux entiersaetbet per- mute le contenu des cases d"indicesaetb. Votre fonction ne cr´eera pas un nouveau tableau, elle se contentera de modifiersur placele tableaut. Elle sera donc de type ?a vect→int→int→unit. IQuestion 5´Ecrivez une fonctionselqui prend pour argument un tableaut; deux entiersaetbet re- tourne l"indice de la case du sous-tableaut.(a)...t.(b) qui contient le plus petit ´el´ement pour l"ordre<. IQuestion 6D´eduisez-en une fonctiontriqui effec- tue le tri d"un tableau. La fonction que vous venez d"´ecrire vous permet de trier un tableau pour la relation d"ordre<. Sur les couples, cet ordre est enCamll"ordre lexicographique. On peut cependant imaginer d"autres relations d"ordre sur des couples, comme par exemple : letordre x (x , y) (x ' , y') = x3 Diviser pour r´egner
Nous revenons maintenant `a notre premier probl`eme, d´eterminer parmi un ensemble de points un couple de points situ´es `a une distance minimale. Nous supposons que nous disposons de deux copies de l"ensemble desn points : - un tableautx, tri´e par abscisses croissantes, - un tableauty, tri´e par ordonn´ees croissantes. On posek=n/2 et on consid`ere les deux sous-tableaux t1= [|t.(0);...;t.(k)|] ett2= [|t.(k+ 1);...;t.(k+ 2)|].
Soitx0un flottant plus grand que les abscisses des points det1et plus petit que les abscisses des points det2. Le plan est divis´e en deux parties : OO x0Notonsp1= (x1,y1) etp?1= (x?1,y?1) les deux points
quep2= (x2,y2) etp?2= (x?2,y?2) deux points les plus proches danst2. On noted= min(?p1-p?1?,?p2-p?2?). Si deux points du tableautsont `a une distance stricte- ment inf´erieure `adalors n´ecessairement l"un fait partie det1et l"autre det2et ils sont dans la bande d"abscisses [x0-d;x0+d]. OO p1•p?1•
p? 2 p2 x 0 ood// IQuestion 8´Ecrivez une fonction qui prend pour ar- gument un tableautyainsi que deux flottantsxmin,xmax et qui s´electionne dans ce tableau les points dont l"abs- cisse est comprise entrexminetxmax. Le r´esultat sera rendu dans un tableautz. Notonstzle tableau des points situ´e dans la bande, ob- tenu grˆace `a un appel `a la fonction pr´ec´edente. Dans chaque tranche de hauteurdde cette bande, il ne peut y avoir plus de 7 points. On en d´eduit que si deux points detzsont `a une distance inf´erieure ou ´egale `adalors ils sont situ´es `a au plus sept cases l"un de l"autre dans le tableautz. OO x 0²²dOO
IQuestion 9´Ecrivez une fonctionplus
proches centre qui prend pour argument le tableautzet retourne le couple de points les plus proches, tels que ces deux points soient situ´es `a au plus 7 cases l"un de l"autre dans le tableautz. Vous pourrez vous inspirer de la fonction plus prochespr´ec´edente. On d´eduit de ce qui pr´ec`ede un algorithme r´ecursif per- mettant de trouver les deux points les plus proches `a partir des deux tableauxtxetty:1. D´ecouper le tableautxen deux tableauxtx,1et
t x,2de longueur moiti´e.2. D´eterminerp1= (x1,y1),p?1= (x?1,y?1),p2=
(x2,y2) etp?2= (x?2,y?2) ainsi que la distanced.3. Calculertz. S"il contient au moins deux points, ap-
pliquer la fonctionplus proches centre`atzpour obtenirp= (x,y) etp?= (x?,y?). 24. Retourner le r´esultat, c"est `a dire la paire de points
`a distance minimale parmip1,p?1;p2,p?2etp,p?.IQuestion 10´Ecrivez en appliquant ce proc´ed´e une
nouvelle fonctionplusproches.´Evaluez sa complexit´e en fonction du nombre de points. 3IMPSI - Option Informatique
Ann´ee 2001, Deuxi`eme TP Caml
Vincent Simonet (http://cristal.inria.fr/~simonet/)Les deux points les plus proches
Un corrig´e
IQuestion 1On utilise la fonctionsqrtdeCamlquipermet de
IQuestion 2Notre fonction se contente d"envisager
`a l"aide de deux bouclesforimbriqu´ees. La r´ef´erenced contient `a chaque instant la plus petite distance trouv´ee et les r´ef´erencessietsjles indices des deux points la r´ealisant. letplus proches t = letn = vect length t andd = ref ( dist t .(0) t .(1)) andsi = ref 0 andsj = ref 1 in fori = 0to(n-1)do forj = i + 1to(n-1)do ifdist t .( i ) t .( j )IQuestion 4 letswap t a b = letx = t .(a)in t .(a)<-t .(b); t .(b)<-x;IQuestion 5La r´ef´erencercontient `a chaqueit´eration l"indice de la case contenant le plus petit