Polytechnique Informatique Commune MP PC 2005

CONCOURS 2005
filière MP - option physique et sciences de lingénieur filière PC

(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. On précisera en tête de copie le langage de programmation utilisé.

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 :

On cherche à calculer la ligne d'horizon engendrée par beaux bâtiments modernes ( ), assimilés à des parallépipèdes verticaux. Pour simplifier, on se place dans l'espace à deux dimensions; nos bâtiments sont de simples rectangles verticaux; la ligne d'horizon est représentée par une suite de segments horizontaux, comme indiqué sur la figure suivante :

Dans trois tableaux globaux à valeurs entières et de longueur , on range respectivement l'abscisse de gauche, l'abcisse de droite et la hauteur du bâtiment vérifiant et pour tout où et sont deux constantes globales (comme d'habitude, les abcisses croissent de la gauche vers la droite, et les ordonnées du bas vers le haut).

Dans l'exemple ci-dessus, les tableaux et valent respectivement , et .

On définit une matrice de pixels (picture elements) dans laquelle on dessine les bâtiments; chaque élément vaut 0 ou 1 ; plus exactement et seulement si le point de coordonnées réelles ( ) est à l'intérieur d'un bâtiment.

Question 1. Écrire une fonction remplir() qui initialise la matrice .

La ligne d'horizon est représentée par un tableau hor de longueur contenant une succession d'abcisses et de hauteurs : hor et hor déterminent les abcisses de début et de fin d'un bout de ligne d'horizon à hauteur hor . Ainsi, dans l'exemple ci-dessus, la ligne d'horizon peut être représentée par le tableau . La «sentinelle » pourra ne pas être le dernier élément du tableau hor ; on autorisera donc les lignes d'horizon contenues dans les seuls premiers éléments d'un tableau.

Dans un premier temps (questions 2 et 3 ), on se contente d'une ligne d'horizon où tous les segments horizontaux sont de longueur 1. Avec cette convention, on prend, pour représenter la ligne d'horizon correspondant à la figure donnée en exemple, , . Alors la longueur du tableau vérifie et, pour , hor .

Question 2. Écrire une fonction horizon1() qui calcule, à partir de la matrice , la ligne d'horizon en temps linéaire par rapport au produit .

On peut réduire le temps d'exécution de cette fonction en écrivant une fonction qui longe la ligne d'horizon dans la matrice . Le contour de l'horizon est la ligne continue formée d'une succession de lignes horizontales et de verticales qui borde l'ensemble supérieur des bâtiments. La longueur de ce contour est la somme des longueurs des segments verticaux et horizontaux qui le composent.

Question 3. Écrire une fonction horizon2() qui calcule, à partir de la matrice , la ligne d'horizon en temps linéaire par rapport à la longueur du contour de l'horizon.

Un tableau hor, de longueur , représentant une ligne d'horizon, est en forme canonique si, pour tout , elle vérifie

Question 4. Écrire une fonction canonique(hor) qui retourne un tableau représentant hor en forme canonique, en temps linéaire par rapport à la longueur de hor.

On veut à présent fusionner deux lignes d'horizon comme indiqué sur la figure suivante :

fusion( )

Les deux lignes d'horizon sont représentées par les tableaux et de longueurs et . On peut effectuer cette fusion très facilement en examinant les deux tableaux de la gauche vers la droite, en maintenant la hauteur du dernier bâtiment rencontré dans et la hauteur du dernier bâtiment rencontré dans , comme indiqué sur la figure suivante :

Question 5. Écrire la fonction fusion qui retourne, en temps linéaire par rapport à , une ligne d'horizon fusionnant les lignes d'horizon et de longueur et .