Olympiade d'Informatique de Madagascar

DEMI-FINALE - OI-MADA 2007

Entrainement > Demi-finale 2007

Exo1: Palindrome
Une chaîne de caractères est un palindrome si la succession des caractères qui la composent est la même quand on la parcourt de gauche à droite ou de droite à gauche. Un palindrome peut se composer d'un seul mot, comme "non" ou "ressasser" ou ce peut être une phrase, comme "engage le jeu que je le gagne" (il faut alors ignorer le caractère espace).
Dans notre cas, on se limite au cas d’un mot qui ne comporte pas plus de 20 caractères.

Ecrivez un programme qui accepte un mot et indique si c’est un palindrome ou non.
On peut déclarer un tableau de chaîne de caractères comme suit :
palindr[10] : caractère

C’est un tableau nommé « palindr » pouvant contenir 10 caractères

Exo2: Triangle de Pascal

On rappelle la définition des coefficients binomiaux :
$\begin{displaymath} C^{p}_{n}=\frac{n!}{p!(n-p)!} \end{displaymath}$
Ils vérifient la propriété suivante $\begin{displaymath} C^{p}_n = C^{p-1}_{n-1} + C^{p}_{n-1} \end{displaymath}$
Vous devez tous connaître le triangle de Pascal qui énumère ces coefficients. C'est la propriété 2 ci-dessus qui permet d'écrire un algorithme de construction de ce triangle.

1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

L'objectif est d'afficher les coefficients pour un nombre X donné
Notez que pour le calcul de chaque nouvelle ligne, vous n'avez besoin que de la ligne précédente.
Ex : Pour X=3
1 3 3 1

Ecrivez un algorithme permettant d’afficher ces coefficients pour une valeur de X donnée. L’utilisateur n’entrera pas une valeur de X qui est supérieure à 20.

Exo3: Labyrinthe

Objectif :
Le programme sert à commander un robot à parcourir un labyrinthe en utilisant un satellite.
Voici le principe :
-le robot reçoit une photo satellite du labyrinthe
-il le transforme ensuite en une matrice de 0 et 1
-1 et 0 représentent respectivement les voies et les murs

Voici le schéma du traitement des informations

Adobe Systems

Zone de Texte: 000000000000000 111001111110000 001001000010000 001001100011100 001000100000100 001110100011100 000010100010000 000010100010000 000011100011110 000000000000010

Afin de vous faciliter le travail, on ne considère que des labyrinthes à chemin unique et sans impasse et la dimension de la matrice associée est toujours [20][20]

Convention :
-Coordonnées : ([colonne],[ligne]) ; ex. : (6,8) (on commence à partir de 0)
-L’entrée est toujours à la colonne 0, ligne 1
-La sortie à l’avant dernière colonne, dernière ligne

On vous épargne la phase de conversion de l’image en une matrice (20 x 20). Ecrivez un programme qui permet d’analyser le fichier « labyrinthe.txt » et affiche les coordonnées du chemin que le robot doit suivre.

Ex. de résultat :
(0,1)
(1,1)
(2,1)
(2,2)
(2,3)
...
(13,8)
(13,9)
On testera votre programme avec d’autres fichiers de même taille.
Et encore !
Pour vous faciliter les choses, on vous donne directement le code pour la lecture d’un fichier.
Lecture d’un fichier

#include<stdio.h>
#include<fcntl.h>
#include<stdlib.h>
int main()
{
char c;
int fd;
fd=open("c:\fichier.txt",O_RDONLY);
while(read(fd,&c,1)>0)
{
printf("%c",c);
}
close(fd);
system("PAUSE");
return 0;
}

Le code ci-dessous permet d’afficher tout le contenu d’un fichier nommé « fichier.txt »

A vous de l’adapter à vos besoins.

Exo4: Conjugaison
Objectif : Le programme demande un verbe du premier groupe se terminant en « er », et le conjugue au présent de l’indicatif. Une fonction de contrôle du verbe entré est nécésaire.
Exemple :

Verbe : chanter
Je chante
Tu chantes
Il chante
Elle chante
Nous chantons
Vous chantez
Ils chantent
Elles chantent

On est sûr que l’utilisateur n’entrera pas un verbe comme « manger » qui se conjugue « nous mangeons » pour la première personne du pluriel.