INFO719 : rappels d'algorithmique et programmation C

2008-10-02T15:32:37Z

Le touzé.florian : /* Question 4 : palindromes */

Ce wiki est un complément de cours pour le cours "info-719 : rappels d'algorithmique et programmation C". La participation au wiki n'est pas obligatoire mais fortement encouragée. Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Vous pouvez aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

<u>Exercice :</u> si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

=Détails techniques=

==Nouvelles==

Les nouvelles récentes sont en haut de la liste...

* [[Utilisateur:Hyvernat|Hyvernat]] 12 septembre 2008 à 15:43 (CEST) : création du wiki

==Organisation des séances==

Comme vous n'êtes pas nombreux, le cours sera entièrement en mode ''cours / TD''.

* première séance (12/09/2008) : introduction, calcul du maximum,
* deuxième séance (16/09/2008) : introduction au C (partie I), début du TD1,
* troisième séance (23/09/2008) : TP0 (reprise du TD1 en salle machines),

==Les support de TD et TP==

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/td1.pdf TD1]

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/tp0.pdf TP0]

* Compléments pour le TP 0 :
** Pour compiler un programme, allez voir la page [[Comment compiler le C ?]]
** Pour faire du C chez vous, vous pouvez :
*** soit installer linux (je vous conseille [http://www.ubuntu-fr.org/ Ubuntu])
*** soit installer une "émulation Unix" pour Windows ([http://www.cygwin.com/ Cygwin], en précisant à l'installation que vous voulez installer au moins <tt>gcc</tt>, <tt>gdb</tt> et <tt>make</tt> dans la partie <tt>Devel</tt>)
*** soit installer un environnement de programmation C pour Windows (par exemple, [http://www.bloodshed.net/dev/devcpp.html Dev-C++])

==Correction TDP0==

=== Question 1 : sur les minimums et maximums===

#include <stdio.h>

#define N 10 /* la taille de mes tableaux */

/* la fonction qui échange le minimum et le maximum dans un tableau */
void change (int T[N]) {

int i=0;
int max=0; /* indice du maximum */
int min=0; /* indice du minimum */

for(i=0;i<N;i=i+1) {
if (T[i] < T[min]) { min=i; }
if (T[i] > T[max]) { max=i; }
}

i=T[min];
T[min] = T[max];
T[max] = i;

}

/* recherche et affichage des deux valeurs maximales dans un tableau */
void deux_max (int T[N]) {
int i;
int max,maxbis;

if (T[0] < T[1]) { max=1 ; maxbis=0; }
else { max=0 ; maxbis=1; }

for(i=2;i<N;i=i+1) {
if (T[i] > T[max]) { maxbis=max; max=i; }
else { if (T[i] > T[maxbis]) { maxbis=i; } }
}

printf("Le grand maximum se trouve à l'indice %i et vaut %i ; ", max, T[max]);
printf("le petit maximum se trouve à l'indice %i et vaut %i.\n", maxbis, T[maxbis]);

}

/* recherche et affichage des deux valeurs maximales distinctes dans un tableau */
void deux_max_bis (int T[N]) {
int i;
int max,maxbis;

max=0;
maxbis=0;

for(i=1;i<N;i=i+1) {
if (max==maxbis && T[i]<T[max]) { maxbis=i; }
else {if (T[i] > T[max]) { maxbis=max; max=i; }
else {if (T[i] < T[max] && T[i] > T[maxbis]) { maxbis=i; }}}
}

if (max != maxbis) {
printf("Le grand maximum se trouve à l'indice %i et vaut %i ; ", max, T[max]);
printf("le petit maximum se trouve à l'indice %i et vaut %i.\n", maxbis, T[maxbis]);
}
else {
printf("!!! Le tableau ne contient qu'une seule valeur : %i !\n",T[max]);
}
}

int main () {
int T[N] = { 0 , 1 , 2 , 3 , 4 , 55 , 666 , 42 , 0 , -7 };
int i ;

/* affichage du tableau */
for (i=0;i<N;i=i+1) printf("T[%i] = %i\n",i,T[i]);
printf("\n\n");

change(T) ;

for (i=0;i<N;i=i+1) printf("T[%i] = %i\n",i,T[i]);

return(1);

}

===Question 3 : renverser un tableau===

(Merci à Diane et Florian... Leur solution était correcte, j'ai juste modifié un ou deux trucs sans grande importance.)

#include <stdio.h>
#define N 10

/* Fonction renverse */
void renverse (int T[N]) {
int tmp;
int i;
for (i=0;i<N/2;i=i+1){
tmp=T[i];
T[i]=T[N-i-1];
T[N-i-1]=tmp;
}
}

/* permet d'afficher les valeurs du tableau dans le terminal */
void affiche_tableau(int T[N]) {
int i;
for (i = 0; i < N; i=i+1) {
printf("T[%d]=%d\n",i,T[i]);
}
}

/* Programme principal */
int main () {
int T[N]={0,1,2,3,4,5,6,7,8,9};

affiche_tableau(T);
printf("Son tableau renversé est: \n");

renverse(T);
affiche_tableau(T);

return 0;
}

=== Question 4 : palindromes===

Écrire un test pour vérifier si un tableau est un ''palindrome''. Si c'est le cas, il devra renvoyer la valeur -1; sinon, il devra renvoyer la plus grande valeur longueur du préfixe qu'on retrouve inversé en suffixe du tableau.

(Merci à Diane et Florian... Leur solution était correcte, j'ai par contre modifié la question pour renvoyer -1 dans le cas des palindromes. C'est plus logique.)

#include <stdio.h>
#define N 10

/* Fonction palindrome*/
int palindrome (int T[N]){
int i;
for (i=0;i<N/2;i=i+1){
if (T[i] != T[N-i-1]) {return i;}
}
return -1;
}

/* permet de taper les 10 valeurs dans le terminal et de les afficher */
int lire_tableau(int T[N]) {
int i;
for (i = 0; i < N; i=i+1) {
printf("T[%d]= ",i);
scanf("%d",&(T[i]));
}
return 0;
}

/* Programme principal*/
int main () {
int T[N];
int x;
lire_tableau(T);
x=palindrome(T);
if (x==-1)
{printf("Le tableau est un palindrome. \n");}
else
{printf("La plus grande longueur d'u prefixe que l'on retrouve inversé en suffixe est %i. \n",x);}
return 1;
}

=== Question 5 : recherche dans un tableau trié===

On suppose que T est un tableau de taille N contenant des entiers triés par ordre croissant. Ecrivez une fonction qui va vérifier si un entier n aopparaît dans le tableau.

*Première méthode: recherche séquentielle

#include <stdio.h>

/*fonction qui cherche un élément dans un tableau trié*/
int recherche_trier (int T[10],int cherche){
int i=0;
int trouve=0;

if (cherche== T[0]){trouve=1;}
else{
while ((!trouve) && (i<10) && (cherche >= T[i])){
i=i+1;
if (cherche==T[i]){trouve=1;}
}
}

if (trouve==1){
printf("L' entier %i a été trouvé à la case %i du tableau \n",cherche,i);
}
else {
printf("L' entier %i n'a pas été trouvé dans le tableau \n",cherche);
}
return 1;
}

/*Programme principal*/
int main(){
int T[10]={1,2,3,4,5,9,10,15,24,42};
int cherche;

/*permet à l'utilisateur de rentrer un entier a chercher*/
printf("Rentrez un entier \n");
scanf("%i",&cherche);

/*Appel de la fonction qui permet de rechercher l'entier*/
recherche_trier (T,cherche);

return 1;
}

*Deuxième méthode: recherche dichotomique

#include <stdio.h>

/*Recherche dichotomique*/
int recherche_dicho(int T[10], int cherche){
int trouve, indice, inf , sup, milieu;

trouve=0;
if (cherche==T[0]){ /* on vérifie si l'élément est a la case 0 du tableau*/
trouve=1;
indice=0;
}
else{
if (cherche==T[9]){ /* on vérifie si l'élément est a la case 9 du tableau*/
trouve=1;
indice=9;
}
else{
inf=0;
sup=9;

while ((!trouve) && (inf<=sup)){
milieu=(inf+sup)/2; /*calcul du milieu du tableau*/
if (cherche==T[milieu]) { /* on vérifie si l'élément du milieu est celui recherché*/
trouve=1;
indice=milieu;
}
else {
if (cherche<T[milieu]){
sup=milieu-1;
}
else{
inf=milieu+1;
}
}
}/*fermeture du while*/
}
}

if (trouve==1){
printf("L' entier %i a été trouvé à la case %i du tableau \n",cherche,indice);
}
else {
printf("L' entier %i n'a pas été trouvé dans le tableau \n",cherche);
}

return 0;
}

/*Programme principal*/
int main(){
int T[10]={1,4,14,18,24,42,100,104,118,124};
int cherche;

/*permet à l'utilisateur de rentrer un entier a chercher*/
printf("Rentrez un entier \n");
scanf("%i",&cherche);

/*appel de la fonction qui permet de recherche l'élément*/
recherche_dicho (T,cherche);

return 1;
}
----
----

=Introduction=

==Objectifs==

* mettre tout le monde à niveau sur les compétences de base en algorithmique
* donner des notions de base sur l'informatique concrète
* Étudier quelques techniques importantes d'algorithmique
* apprendre les bases du langage C

==Plan==

* intro, étude d'un exemple
* rappel d'algorithmique (probablement faits en TD)
* rappel mathématiques, complexité
* quelques techniques d'algorithmique
* notions de complexité

* le langage C

==Rappels historiques==
Vous pouvez partir de [http://fr.wikipedia.org/wiki/Chronologie_informatique cette page] pour avoir un peu plus de détails...

===La préhistoire : le calcul===

* le boulier chinois
* la [http://fr.wikipedia.org/wiki/Pascaline pascaline] de Pascal, inventée en 1641/42 : elle ne permet de faire que des additions (et des soustractions
* Leibniz rajoute la multiplication à la pascaline (1673)
* les "moulins à chiffres" de [http://fr.wikipedia.org/wiki/Babbage Charles Babbage] (1834-36), malheureusement jamais construits...
* la "tabulating business machine" de Hollerith permet d'automatiser les calculs pour le recensement de la population américaine. Ceci donnera ensuite la société "international business machine" (IBM).
* l'apparition du relais électromécanique (1900) d'une fréquence de 100 Hz, permet la construction du [http://fr.wikipedia.org/wiki/Harvard_Mark_I Harvard Mark I] en 1944

===Les programmes et instructions===

* les [http://fr.wikipedia.org/wiki/Orgue_de_Barbarie orgues de Barbarie]
* les métiers à tisser de Vaucanson et [http://fr.wikipedia.org/wiki/M%C3%A9tier_Jacquard Jacquard] (1801)

===Les ordinateurs "modernes"===

* l'invention du tube à vide permet le développements d'ordinateurs entièrement électroniques : l'[http://fr.wikipedia.org/wiki/ENIAC ENIAC] en est le premier exemplaire (1946) ; il pèse environ 30 tonnes...
* la machine de Turing (ordinateur théorique)
* le Manchester Mark I (1948) et l'[http://fr.wikipedia.org/wiki/EDVAC EDVAC] (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
* l'[http://fr.wikipedia.org/wiki/UNIVAC_I UNIVAC I] est le premier ordinateur commercialisé, en 1951.

=Rappels d'algorithmique=

==Un exemple==

'''<u>Exercice :</u> écrivez un programme qui fait la chose suivante :
on dispose d'un tableau d'entier <tt>T</tt> de taille <tt>n</tt>. L'élément <tt>i</tt> du tableau est
noté <tt>T[i]</tt>. On veut modifier <tt>T</tt> en interchangeant le plus petit et le plus grand
élément.'''

''Solution possible''

int i=0
int max=0 /* indice du maximum */
int min=0 /* indice du minimum */

if (n==0) then exit /* est-ce que le tableau est vide ? */

for i:=0 to n-1 /* j'ai pris la convention du C : les tableaux commencent à l'indice 0 */
if T[i] < T[min] then min:=i
if T[i] > T[max] then max:=i
end

i:=T[min]
T[min] := T[max]
T[max] := i

exit

==Le langage C, partie 1==

Un exemple caractéristique :

/* « ouverture » des bibliothèques utilisées */
#include <stdio.h>

/* première fonction : elle prend deux entiers en argument et renvoie un entier */
int minimum (int n, int m) {
if (n<m) { return(n); }
else { return(m); }
}

/* la fonction principale */
int main () {
int i=42,x; /* i et x sont deux variables entières */
int j;
j=24;
x=minimum(i,j*2);
printf("Le minimum de %i et %i est %i.\n", i, j*2, x);
return(1);
}

Quelques points importants :
* il faut explicitement déclarer les bibliothèques utilisées,
* on n'est pas obligé d'avoir des fonctions autre que la fonction <tt>main</tt>, mais les fonctions doivent être déclarées dans l'ordre
* la fonction <tt>main</tt> est obligatoire, et il est conseillé de lui donné le type de retour <tt>int</tt>.

* une variable ne « vit » qu'à l'intérieur du bloc <tt>{ ... }</tt> dans lequel elle est déclarée
* les variables ne sont pas initialisées automatiquement à 0

Pour la syntaxe de base et des exemples concernant les conditions et les boucles, reportez-vous au chapitre [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node9.html « les bases »] et [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node31.html « les tableaux »] du polycopié de Bernard Cassagne.

=Références=

* "The C programming language", de Kernighan et Ritchie,
* « Le langage C », version française du précédent,
* le polycopié de Bernard Cassagne, disponible [http://www-clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C.html ici], au format [http://www-clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C.html html] (en ligne) ou [ftp://ftp.imag.fr/pub/labo-CLIPS/commun/C/Introduction_ANSI_C.pdf pdf],
* « Programmation C », un livre collaboratif sur le mode Wikipedia, disponible [http://fr.wikibooks.org/wiki/Programmation_C ici].

Wiki du LAMA (UMR 5127) - Contributions [fr]

INFO719 : rappels d'algorithmique et programmation C