[PDF] Les deux points les plus proches





Previous PDF Next PDF



Chapitre 3 Etude de la liaison entre deux variables Analyse

La loi du couple n'est pas binormale : test non paramétrique basé sur le coefficient de corré- lation empirique de Spearman. b ) Test paramétrique sur le coe 



Chapitre 1 Etude de la liaison entre deux variables. Analyse

la loi du couple n'est pas binormale : test non paramétrique basé sur le coefficient de corrélation empirique de Spearman. b ) Test paramétrique sur le coe 



Ecricome

Cette épreuve comporte deux ou trois textes. Chaque texte est suivi d'une série faire jouer comme un outil critique de la condition de l'homme moderne.



Méthodologie Statistique Document de travail

Essai de comparaison de deux enquêtes peu comparables. choisi de faire figurer dans leur questionnaire le terme « couples d'amis » auquel faisaient.



METHODE DES COUPLES ou SERIES APPARIEES

9 févr. 2000 Par exemple on pose une question préliminaire du genre : Pour chaque cheval



Les deux points les plus proches

Nous représenterons un point en Caml par un couple de possibles ce qui peut se faire facilement `a l'aide de deux boucles for. ? Question 2 ´Ecrivez ...





Conditions de passation et biais occasionnés par la présence dun

Afin de limiter les biais les enquêteurs ont pour consigne de faire deux membres du couple)



LISTE DES TESTS DISPONIBLES

MOS SF 36 - Questionnaire généraliste de qualité de vie . nombres de 3 à 12 chiffres



compréhension orale - le couple en question

et on est davantage prêts à faire des efforts de couple alors que les couples Hélène Jouan : - L'union de deux de ces êtres si imparfaits et si affreux ...



Searches related to questionnaire couple a faire a deux PDF

Ce sont des questions qui abordent tous les moments de votre vie : avant votre rencontre pendant votre rencontre et après Il existe différent types de questions : • des questions faciles • des questions sans réponse pour le moment • des questions qui demandent réflexion

Pourquoi faire un questionnaire pour couple ?

Si vous avez l'impression que vos discussions tournent toujours autour des mêmes sujets de conversation, comme le travail par exemple, ce questionnaire pour couple est l'occasion d'aapprofondir vos échanges. N'hésitez pas à rebondir sur les questions de ce quiz pour couple et donc d'aborder de nombreux sujets de discussion.

Quel est le prix d'un questionnaire couple ?

LIVRAISON OFFERTE DÈS 39,80€ D'ACHAT. Questionnaire couple : Connaissez-vous votre partenaire ? La complicité et l'écoute sont les piliers d'une belle et longue relation. Entre stress quotidien et routine, on ne profite pas assez de moments à deux.

Comment faire un jeu de couple ?

Vous pouvez les envisager comme un jeu de couple, en vous posant les questions à tour de rôle et en ajoutant vos propres questions pour pimenter le tout. Nous vous souhaitons un bon moment de partage à tou.te.s les deux ! Les questions pour une faire une rétrospective des moments marquants de votre couple.

Comment tester votre couple ?

On commence doucement avec ce questionnaire qui va tester votre couple. Les questions basiques et générales sur la personne que vous aimez sont essentielles, vous allez forcément obtenir un bon résultat pour cette partie du quiz. Généralement, on connait déjà les réponses avant même d’être en couple ! 1. Quelle est ma date de naissance ? 2.

Les deux points les plus proches

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 0

1 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´ethodepermettant 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 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') = xIQuestion 7Adaptez les fonctionsselettride sorte qu"elle prennent ´egalement en argument une fonction implantant une relation d"ordre (commeordre xou ordre y).

3 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 t

1= [|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 x

0Notonsp1= (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?). 2

4. 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. 3

IMPSI - 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 dela racine carr´ee d"un flottant etl"op´erateur??.d"exponentiation.

letdist (x , y) (x " , y") = sqrt ((x-. x")??. 2.0 +. (y-. y")??. 2.0)

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

´el´ement parmit.(a)...t.(i).

letsel t a b = letr = ref ain fori = a + 1tobdo ift .( i )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;

IQuestion 7

letsel comp t a b = letr = ref ain fori = a + 1tobdo ifcomp t .( i ) t .(! r )thenr := i done; ! r lettri comp t = letn = vect length tin fori = 0to(n-1)do letk = sel comp t i (n-1)in swap t i k done;

IQuestion 8

letselectionne ty x min x max = letn = vect length tyin letresultat = ref [ ]in fori = n-1downto0do ifx min<= fst ty .( i ) && fst ty .( i)<= x max thenresultat := ty .( i ) : : ( ! resultat ) done; vect of list (! resultat )

IQuestion 9Notre fonctionplusprochescentreest

tr`es semblable `a la fonctionplusproches. La seule diff´erence r´eside dans la borne sup´erieure de la boucle index´ee parj: il n"est plus n´ecessaire de poursuivre jusqu"`aj=n-1 mais on peut se limiter `aj= min(n-1,i+ 7). letplus proches centre t = letn = vect length t andd = ref ( dist t .(0) t .(1)) andsolution i = ref 0 andsolution j = ref 1 in fori = 0to(n-1)do forj = i + 1tomin (n-1) ( i + 7)do ifdist t .( i ) t .( j )IQuestion 10 let recplus proches ' tx ty = letn = vect length txin ifn<= 3then( plus proches tx) else begin lettx1 = sub vect tx 0 (n/2) andtx2 = sub vect tx (n/2) (n-n/2) andx0 = fst tx .(n/2-1)in letp1 , p1" = plus proches ' tx1 ty andp2 , p2" = plus proches ' tx2 tyin letp12 , p12" = if( dist p1 p1")<( dist p2 p2") then(p1 , p1") else(p2 , p2") in letd = dist p12 p12 "in lettz = selectionne ty (max (x0-. d) ( fst tx .(0))) (min (x0 +. d) ( fst tx .(n-1))) inquotesdbs_dbs31.pdfusesText_37
[PDF] jeu pour faire connaissance soirée

[PDF] question de couple a poser

[PDF] quel question poser lors dun stage en creche

[PDF] questions a poser a un peintre

[PDF] questions pour interviewer un chanteur

[PDF] interview entre journaliste et chanteur

[PDF] parc ? conteneurs de viroinval viroinval

[PDF] soit f et g les fonctions définies sur r par

[PDF] soit f et g deux fonctions définies sur r par

[PDF] on considere les fonctions f et g

[PDF] calcul charge maximale dutilisation

[PDF] tutoriel mblock pdf

[PDF] mblock programme

[PDF] mblock francais

[PDF] questionnaire de préparation au mariage