(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.

Après un grand chamboulement, une administration défaillante tente de reconstituer l'ordre de voisinage dans une rue de maisons ( ). Pour simplifier, on suppose la rue occupée sur un seul de ses deux cotés. Chaque propriétaire a un identifiant qui est un nombre entier le désignant sans ambiguïté. Chaque maison a deux maisons voisines (à sa gauche et à sa droite). On demande à chaque propriétaire de maison d'écrire son identifiant et l'identifiant de son voisin de droite sur une fiche ( ). Par convention, l'identifiant du voisin de droite de la maison située à l'extrémité droite de la rue est -1 . On collecte les fiches et on veut reconstituer le plan de la rue dans l'ordre initial.

On représente les fiches par deux tableaux globaux et de longueur , contenant des entiers naturels et , sauf pour une valeur de l'indice où on a .

On suppose, dans les deux premières parties (questions 1 à 4), que chaque propriétaire ne possède qu'une seule maison. Donc, tout entier naturel apparait au plus une fois dans chaque tableau.

Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute :

Question 1 Écrire une fonction plusadroite() qui retourne, en temps linéaire en , l'indice (dans le tableau ) de la maison la plus à droite dans la rue.

Question 2 Écrire une fonction calculerG() qui calcule, en temps quadratique en , les valeurs du tableau tel que est l'indice du voisin de gauche de la maison d'indice . (On supposera que est un tableau global de éléments; et on posera quand est l'indice de la maison la plus à gauche dans la rue).

Question 3 En supposant le tableau global donné par la question précédente, en déduire la fonction imprimer() qui imprime en temps linéaire en tous les identifiants de propriétaires des maisons dans l'ordre initial de la rue de la gauche vers la droite. (On construira un tableau intermédiaire où on rangera les propriétaires dans l'ordre de la rue).

On suppose à présent les tableaux et agencés de telle sorte que le tableau est trié dans l'ordre croissant. On a donc toujours pour .

La fonction calculer peut maintenant utiliser une recherche dichotomique pour déterminer l'indice du voisin de gauche de toute maison . Pour trouver l'indice tel que , on compare la valeur à la valeur du milieu du tableau et on recommence, si nécessaire, sur la moitié haute ou basse du tableau en fonction de l'ordre relatif de et .

Question 4 Écrire une nouvelle version calculerG1() de la fonction calculerG() utilisant la recherche dichotomique. Donner un ordre de grandeur de son temps d'exécution en fonction de .

On se remet à nouveau dans les conditions de la première partie, en ne faisant aucune supposition sur l'ordre du tableau .

Un propriétaire peut maintenant avoir plusieurs maisons dans la rue et écrit autant de fiches, donnant son identifiant et celui de son voisin de droite, qu'il a de maisons. Chaque propriétaire connait l'ordre d'apparition de ses maisons dans la rue. Pour chaque maison , un tableau global donne l'indice de la maison suivante à gauche dans la rue appartenant à si elle existe. Sinon . On a donc quand .

A partir des tableaux et , l'Administration centrale a déjà pré-calculé le tableau global donnant l'indice du voisin de gauche dans la rue. Dans le cas où le voisin de gauche possède plusieurs maisons, la valeur indiquée par est toujours l'indice de la maison la plus à droite dans la rue appartenant à . Remarque : la maison indiquée par n'est pas forcément à la gauche de la maison . Dans le cas où est l'indice de la première maison à gauche, vaut -1 .

On dispose donc des quatre tableaux globaux suivants :

Pour retrouver l'ordre initial de la rue, on procède comme suit. On démarre avec la maison la plus à droite dans la rue en se servant du tableau . On avance dans le tableau grâce au tableau . Si on rencontre un propriétaire qui a plusieurs maisons, on continue avec un des voisins de gauche possibles dans la rue. L'ordre donné par le tableau permet de trouver le bon voisin de gauche, et on continue.

Question 5 Reconstruire l'ordre de la rue dans le cas où on a et les tableaux tels que et .

Question 6 En déduire la fonction imprimer2() qui imprime, en temps quadratique en , tous les identifiants des propriétaires des maisons dans l'ordre initial de la rue de la gauche vers la droite.

Question 7 Écrire une fonction imprimer3() qui fait la même impression en temps linéaire en .