I. 95. Un réseau informatique est composé de nœuds et de câbles reliant des paires de nœuds. Nous voudrions sécuriser ce réseau de telle façon que si un des câbles ( mais seulement un ) se casse, l'intégrité du réseau ne soit pas perturbée. Donner le nombre minimal de paires de nœuds lesquels doivent être reliés pour que le réseau soit sécurisé.

A chaque nœud, on attribue un nombre entier positif. Le programme doit lire en entrée les paires de nombres désignant les paires de nœuds, deux nombres entiers par ligne, séparés par un espace. La fin de la saisie est signalée par deux zéros, séparés aussi par un espace. Les paires de nœuds désignant les câbles nécessaires doivent être affichées au même format.

Important ! Nous allons contrôler la solution par un programme, donc, il ne doit écrire rien d'autre à l'écran et l'affichage doit être réalisé sans pagination. (pour le test, stdin peut être redirigé). Envoyer le programme (i95.pas).

(10 points)

I. 96. Les n premiers termes d'une suite ne déterminent pas les autres termes de la suite : nous pouvons continuer l'énumération des termes d'une manière quelconque.

On donne maintenant la procédure suivante pour déterminer le (n+1)-ième terme ( soit n 2 un nombre entier positif ) : Prenons la différence des termes voisins, en soustrayant celui d'indice inférieur à celui d'indice supérieur. Exécutons ensuite cette même procédure avec la suite ainsi obtenue. Après quelques étapes, nous obtenons une suite constante dans laquelle il n'y a plus de termes différents. Cela arrive au plus tard à l'étape (n-1), puisque cette suite n'a plus qu'un terme. Par exemple (pour l'instant, on ne regarde que les nombres en gras et de plus grande taille !):

Nous voulons déterminer le (n+1)-ième terme de telle façon que, en exécutant de nouveau la procédure ci-dessus, la suite constante reste toujours constante. De cette constante, en revenant en arrière, calculer le (n+1)-ième terme. (Ceci est indiqué par les nombres clairs et de taille plus petite.)

Créer un tableau (i96.xls), qui cherche, pour les n premiers termes d'une suite, le (n+1)-ième terme correspondant, selon la procédure ci dessus. Envoyer le tableau (i96.xls). Dans le champ (A1), vous pouvez inscrire le mode d'emploi.

(10 points)

S. 5. Ecrire un programme pour créer des pavages hyperboliques Escher. Le programme doit réaliser le pavage, avec des triangles, du modèle circulaire; il doit dessiner, dans chaque pavé, un motif que nous donnons dans un fichier à part.

L'entrée du programme est constituée des éléments suivants :

· Les angles du triangle de pavage. Les angles sont donnés sous la forme , , , où p, q, r sont des nombres entiers positifs et

Le triangle de départ ABC doit être positionné de telle façon que son sommet A soit au centre du modèle, le sommet B doit se situer horizontalement à droite (voire la figure).

· Le motif de pavage. Le motif est donné dans un fichier d'image couleur, de format PPM. Les sommets du pavé sont décrits par trois paires de coordonnées.

· La taille de l'image à réaliser et le nom du fichier en sortie. L'image sera toujours de forme carrée, la taille est donc donnée par un seul nombre entier positif m, au maximum 2048.

Le programme doit lire les données en entrée dans l'ordre suivant :

(nomprogramme) p q r motifpavage.ppm a1 a2 b1 b2 c1 c2 output.ppm m (motifpavage.ppm et output.ppm seront naturellement remplacés par d'autres noms de fichiers.)

Le programme doit créer, en utilisant les données en entrée, l'image de type PPM. Au cours du dessin du motif, il doit travailler avec la méthode de coordonnées de centre de masse.

(10 points)

Ce qu'il faut savoir du format PPM

L'entrée et la sortie du programme est un fichier couleur, binaire, de type PPM, sa taille est au maximum 2048×2048.

Entête (header)

Le fichier commence par l'entête. Elle est composée de 4 données :

· Le mot "P6" , situé au deux premiers bytes du fichier;

· La largeur et la hauteur de l'image;

· La valeur maximale des valeurs des couleurs (1--255).

Ces 4 données se suivent dans cet ordre, séparées par des caractères espaces, saut de ligne (CR, LF) et TAB. L'entête peut contenir aussi des remarques. La remarque peut débuter n'importe où, son premier caractère est toujours # et sa fin est la fin de la ligne. La fin de l'entête est le premier caractère LF situé après la dernière donnée de l'entête.

Donnée binaire

L'entête est suivie par les données des pixels. Les pixels se suivent par ligne, de haut en bas et de gauche à droite. Chaque pixel est composé de 3 bytes, contenant les valeurs rouge (R), vert (G), et bleu (B).

Les solutions des exercices d'Informatique doivent être adressées à :

ou par mail : mathspci@free.fr ( lire les questions/réponses )

Date limite d'envoi : 28 février 2009