ESSEC concours mathématiques III 1999 option économique

]pNp[p]+Nl[p[1]qJq2pF+FqNpn+:;qF1Np[1]q1+:lpk]]FiF[FFN1]NkFpNkNiN[k[2iFNp;q;k::;:[[1]kNNp[k+qq]i[ESSECCONCOURS D’ADMISSION DE 1999Option economique´Mathematiques´ IIIExercice I : Etude du tri dichotomique.Dans cet exercice, on consider` e un nombre entier naturel et le nombre entier=2 .Dans cases numer´ otees´ sont rangees´ fiches (a` raison d’une fiche par case) qui contiennentdes informations dont un nombre note´ pour la fiche rangee´ dans la case 1, pour la fiche rangee´dans la case 2, ... , pour la fiche rangee´ dans la case .Ces fiches peuvent repres´ enter les clients d’une entreprise et les nombres;F;:::;F les montantsdes commandes passees´ par ces clients, ou bien les candidats a` un concours et les nombres;F;::;Fles totaux des points obtenus par ces candidats, etc.L’objectif est ici de ”trier ces fiches”, autrement dit de les ranger dans les cases de fac¸on ac` equelesnombres;F;:: soient dans l’ordre croissant.Si par exemple les fiches consider´ ees´ sont celles des candidats a` un concours, on cherche donc al` esranger dans l’ordre croissant des totaux obtenus (de fac ¸on a` ce que la premier` e fiche soit donc celle d’uncandidat avec le plus faible total, la dernier` e celle d’un candidat avec le plus fort total).On et´ udie maintenant un algorithme tres` performant de tri (” tri dichotomique ” ) de ces fiches.1. Tri des fiches de deux tas ...