|
TOI
|
1ère Olympiade Tunisienne d'Informatique Ariana, 19 avril 2003 |
|||||||||||||||||||||||||||||||||
NB. : La sauvegarde de votre travail devra se faire dans le dossier C:/TOI. Les programmes à écrire doivent porter les noms indiqués entre parenthèses dans la première ligne de chaque problème.Problème 1 (W_ORDERED)Un entier de n chiffres (1<n<9) est dit bien ordonné si ses chiffres forment, de gauche à droite, une suite strictement croissante. Exemple : L'entier de trois chiffres, 147 est bien ordonné car 1<4<7. L'entier de 4 chiffres, 1265 n'est pas bien ordonné car 6>5. Écrire un programme qui saisit un entier n (1<n<9) et fait sortir tous les entiers bien ordonnés de n chiffres et le nombre total de ces entiers. Problème 2 (CODES)Une manière de coder un texte consiste en l'opération suivante. On se fixe un entier n donné. On considère que le texte à coder est une chaîne de caractères. En commençant à partir du premier caractère, on divise le texte en blocs de longueur n2 (nxn) caractères consécutifs. Si la longueur du texte n'est pas un multiple de n2, on lui ajoute autant d'espaces qu'il en faut pour que sa longueur devienne un multiple de n2. Chaque bloc est divisé à son tour en n sous-blocs de longueur n caractères. En disposant ces sous-blocs l'un en dessous de l'autre, on obtient alors n colonnes. Chaque colonne, lue du haut vers le bas, va donner une chaîne de n caractères. En rassemblant dans l'ordre toutes ces chaînes, on obtient une nouvelle chaîne qui sera le texte codé. Exemple : Pour n = 3 et le texte à coder ="Je vais à Tunis pour l'OTI" La longueur de ce texte est égale à 26. On lui ajoute 1 espace pour que sa longueur devienne multiple de 9. La chaîne devient "Je vais à Tunis pour l'OTI " Sa longueur devient donc 27. En appliquant les étapes ci-dessus évoquées, on obtient :
La chaîne codée sera : "Jvsea ià n TipusoulTr'I O " Écrire un programme qui saisit un entier naturel n tel que 2<n<9 et le texte à coder (une chaîne de caractères). Il fait sortir ensuite le texte codé. Problème 3 (VIRUS)Une population de virus évolue dans un lieu assimilé à un tableau carré nxn. Un virus occupe une seule case et une case contient au plus un virus. Deux cases sont dites voisines si elles ont un sommet ou un côté communs. Deux virus sont dits voisins s'ils occupent deux cellules voisines. On appelle génération toute répartition d'un nombre de virus dans ce tableau. L'évolution d'une génération à une autre se fait selon les règles suivantes : 1 – un virus qui a au plus deux voisins (inférieur ou égal à 2), meurt de solitude. 2 – un virus qui a au moins 5 voisins (supérieur ou égal à 5), meurt asphyxié. 3 – une cellule vide ayant exactement trois cellules voisines occupées par des virus donne naissance à un nouveau virus. On se propose d'écrire un programme qui saisit un entier n (5<n<20). Cet entier sera le côté du tableau carré où va évoluer la population des virus. Ensuite, il saisit une génération initiale de la population de ces virus. Cette entrée est composée d'une suite de couples (i, j) où 1£i£n et 1£j£n représentant les coordonnées des cellules qui vont contenir des virus. Le programme demande ensuite l'ordre m (1<m) de la génération qu'on voudra trouver en partant de la génération initiale. On pourra envisager la saisie à partir d'un fichier de données (GEN_INIT.TXT) organisé ainsi : · 1ère ligne contient n. · 2ème ligne contient m. · une suite de lignes comportant chacune un couple d'entiers séparés par un espace. Chaque couple d'entiers représente les deux coordonnées de la cellule où il y aura un virus.
La génération cherchée sera affichée à l'écran sous forme d'un tableau où un virus est représenté par une étoile.
|
||||||||||||||||||||||||||||||||||