ÿþ<HTML> <HEAD><TITLE> Cours Langages Impératifs 2 (2011-2012) J-J Bourdin</TITLE> <!----<link rel="stylesheet" href="./global.css">----> <style type="text/css" media="screen">@import"proj.css";</style> </HEAD> <!---- <BODY leftmargin="5" topmargin="10" marginwidth="10" marginheight="10" background="images/fond_home.gif" bgColor="#FFFFFF"> ----> <A NAME=HAUT></A> <BODY BGCOLOR="#ffffff" LINK="#0000ff" VLINK="#ff0000" ALINK="#ff0000" TEXT="#000000"><P> <FONT FACE=verdana> <FONT SIZE=4> <b> Jean-Jacques BOURDIN</b></FONT> <FONT SIZE=3> <dl> <dt><A HREF="http://www.univ-paris8.fr"> Universit&eacute; Paris 8 </A> <dt> <A HREF="http://www.ai.univ-paris8.fr">Labo IA</A>, D&eacute;pt. Informatique <dt>2, rue de la Libert&eacute; <dt>93526 Saint-Denis Cedex <dt>FRANCE </dl> <P> <dl> <dt><b> T&eacute;l </b>: (+33/0) 1 49 40 64 03 <dt> <b> Fax </b>: (+33/0) 1 49 40 64 10 <dt> <b> E-mail </b> : Jean-Jacques.BourdinNOSPAM@ai.univ-paris8.fr (enlever le NO Spam) </dl> </FONT> <P> <HR SIZE=3 NOSHADE WIDTH="100%"> <P> <P> <H2> <CENTER> Langages Impératifs 2 </CENTER> <P> <CENTER> Octobre 2011 -- Janvier 2012 </CENTER> <P> </H2> <HR SIZE=2 COLOR="#ff005f" NOSHADE WIDTH="80%"> <B> Les résultats ne seront pas affichés avant vendredi 27/01, donc les oraux auront lieu lundi 30/01.<BR> Il y aura quatre groupes&nbsp;: <OL> <LI>Admis. <LI>Doit passer la deuxième session (avril ou début mai). <LI>Doit représenter un projet. <LI>Doit représenter un projet et passer la deuxième session. </OL> Pour repasser un projet il faudra&nbsp;: <BR> soit présenter le même sujet, mais repris sérieusement, le 13/02/12 à 12h.<BR> soit demander un nouvel énoncé, qu'il faudra faire en sept semaines. <BR> <FONT COLOR="#ff0030"> <B><P>La deuxième session d'examen aura lieu le vendredi 6 avril 2012 à 9h salle B134</P></B> </FONT> <TABLE BORDER=1> <T><TD>&nbsp;nom&nbsp;</TD><TD>&nbsp;groupe&nbsp;</TD></TR> <T><TD>&nbsp;Sacko&nbsp;</TD><TD>&nbsp;4&nbsp;</TD></TR> <T><TD>&nbsp;Batouche &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Sadji &nbsp;</TD><TD>&nbsp;2 &nbsp;</TD></TR> <T><TD>&nbsp;Abdes &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Bouzgaou &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Ayeb &nbsp;</TD><TD>&nbsp;3 &nbsp;</TD></TR> <T><TD>&nbsp;Samake &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Bouchentouf &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Hamitouche &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Laoudej &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Tezcan &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Mohandi &nbsp;</TD><TD>&nbsp;2 &nbsp;</TD></TR> <T><TD>&nbsp;Wang Bo &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Dong &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <T><TD>&nbsp;Kalsin &nbsp;</TD><TD>&nbsp;4 &nbsp;</TD></TR> <!---<T><TD>&nbsp; &nbsp;</TD><TD>&nbsp; &nbsp;</TD></TR> <T><TD>&nbsp; &nbsp;</TD><TD>&nbsp; &nbsp;</TD></TR>---> </TABLE> <P> <OL> <LI><A HREF="#presen">Présentation</A> <LI><A HREF="#make">Programmation structurée</A> <LI><A HREF="#ptr">Indirections et Fonctions</A> <LI><A HREF="#imag">Exemples&nbsp;: images</A> <!---<LI><A HREF="#partiel">Premier partiel</A> <LI><A HREF="#partiel2">Deuxième partiel</A> <LI><A HREF="#files">La gestion de fichiers</A>---> <LI><A HREF="LI2_P_11.html">Les énoncés de projets</A> <!---<LI><A HREF="#shell"></A> <LI><A HREF="#oral"></A>---> </OL> <OL> <LI><H3><A NAME="presen">Pr&eacute;sentation</A></H3> <UL> <LI><B>Objectifs</B><P> <LI><B>Pratique</B><P> </UL> <LI><H3><A NAME="make">Programmation strcuturée</A></H3> <OL> <LI><B>Un exemple</B><P> Voici un programme simple que nous voudrions structurer&nbsp;: <TABLE BORDER=1><TD> <PRE> #include &lt;stdio.h&gt; double puis (double x, int n) { double res = 1.0; while (n) { if (n & 0x01) res *= x; x *= x; n >>= 1; } return res; } main () { int n; double y; for (y=0.0; y < 3.1; y += 0.2) { for (n = 0; n < 10; n++) printf ("%3.5lf ^ %d == %6.8lf\n", y, n, puis(y,n)); } } </PRE> </TD></TABLE><BR> <LI><B>Spécification</B><P> D'abord, il faut spécifier pour la fonction <I>puis</I>. Elle renvoie un double et reçoit comme paramètre un double et un entier. <TABLE BORDER=1><TD> <PRE> double puis (double, int) ; </PRE> </TD></TABLE><BR> Nous nommerons ceci, la "spécification" de la fonction. Vous avez sans doute déjà remarqué que si la fonction <I>appelante</I> est placée avant la fonction appelée, par défaut, le compilateur applique un type entier comme type de la valeur retournée. Ceci est à la base de nombreuses erreurs. Pour éviter cela, commencez, en tête de fichier, par spécifier toutes vos fonctions. <BR> <LI><B>Sa séparation</B><P> Ensuite, séparez ce programme en trois parties&nbsp;: <UL><LI>l'entête, <TT>puis.h</TT>, <LI>le fichier contenant la fonction, <TT>puis.c</TT>, <LI>le fichier contenant la fonction main, <TT>main.c</TT>. </UL> Il suffit alors que les deux fichiers <TT>.c</TT> commencent par <TABLE BORDER=1><TD> <PRE> #include "puis.h" </PRE> </TD></TABLE><BR> pour que cet entête soit inclus automatiquement dans votre programme. Nous arrivons alors à avoir trois fichiers, qui accompagnent la compilation suivante&nbsp;: <TABLE BORDER=1><TD> <PRE> $gcc main.c puis.c -o puissances </PRE> </TD></TABLE><BR> Mais pour répartir le travail vaut mieux encore séparer aussi la compilation, en faisant faire d'abord le code objet (<TT>.o</TT>) de chaque fichier. L'utilisation d'un fichier <TT>Makefile</TT> de base fait ce travail. <TABLE BORDER=1><TD> <PRE> puissances: main.o puis.o puis.h $(CC) -o puissance main.o puis.o main.o: main.c puis.h $(CC) -c main.c puis.o: puis.c puis.h $(CC) -c puis.c clean: rm *.o *~ core </PRE> </TD></TABLE><BR> À l'usage, si on veut compiler le programme on fait simplement&nbsp;: <TABLE BORDER=1><TD> <PRE> $make </PRE> </TD></TABLE><BR> Toutes les compilations ont lieu alors avec vérification, par leur date, de l'antériorité des fichiers, de façon à ne compiler que ceux qui ont été modifiés depuis la dernière compilation.<BR> Premier fichier Makefile&nbsp;: <TABLE BORDER=1><TD> <PRE># Compilation generique par Bourdin CC=gcc SRC=puis.c main.c OBJ=puis.o main.o CFLAGS=-Wall fil: $(OBJ) puis.h $(CC) -o $@ $^ main.o: main.c $(CC) -c main.c $(CFLAGS) puis.o: puis.c $(CC) -c puis.c $(CFLAGS) </PRE> </TD></TABLE><BR> Mais on fera mieux ainsi&nbsp;: <TABLE BORDER=1><TD> <PRE> CC=gcc SRC=puis.c main.c OBJ=$(SRC:.c=.o) FLAGS=-Wall fil: $(OBJ) puis.h $(CC) -o $@ $^ %.o: %.c $(CC) -c $< $(CFLAGS) clean: rm *.o *~ core </PRE> </TD></TABLE><BR> <LI>Localité des variables<BR> On peut avoir une variable statique, globale, en registre. Voici un exemple de statique local à une fonction (dû à JP Braquelaire) <TABLE BORDER=1><TD> <PRE>#include <stdio.h> int nextval () { static int n = 0; return ++n; } main () { int n, i; n = 6; for (i= 0; i < n; i++) { printf("La %3d ieme demande obtient %d\n", i, nextval()); } } </PRE> </TD></TABLE><BR> Qui donne à l'usage&nbsp;:<BR> <TABLE BORDER=1><TD> <PRE>mu.ai.univ-paris8.fr: a.out La 0 ieme demande obtient 1 La 1 ieme demande obtient 2 La 2 ieme demande obtient 3 La 3 ieme demande obtient 4 La 4 ieme demande obtient 5 La 5 ieme demande obtient 6 mu.ai.univ-paris8.fr: </PRE> </TD></TABLE><BR> <!-- <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> </OL> ---> <LI><H3><A NAME="comp">Compilation</A></H3> <OL> <LI><B>Les quatre étapes</B><P> <OL> <LI>Précompilation (option -E)<P></P> On trouvera de la documentation précise sur les bibliothèques standard sur <A HREF="http://www.utas.edu.au/infosys/info/documentation/C/CStdLib.html"> le lien suivant</A>. Vous devriez en prendre connaissance.<P></P> Voici un exemple d'utilisation de la bibliothèque <TT>assert.h</TT> <TABLE BORDER=1><TD> <PRE>#include < assert.h> #include < stdio.h> /* Première version : main () { int i, j, n; n = 10; for (i=0, j=0; i <= n; i++){ j += 1 + (i << 1); assert(j==(i*i)); printf("%d carre == %d\n",i,j); } } Macintosh.local: gcc asser.c Macintosh.local: a.out Assertion failed: (j==(i*i)), function main, file asser.c, line 9. Abort trap */ /* Seconde version */ main () { int i, j, n; n = 10; for (i=0, j=0; i <= n; i++){ assert(j==(i*i)); printf("%d carre == %d\n",i,j); j += 1 + (i << 1); } } /* Macintosh.local: gcc asser.c Macintosh.local: a.out 0 carre == 0 1 carre == 1 2 carre == 4 3 carre == 9 4 carre == 16 5 carre == 25 6 carre == 36 7 carre == 49 8 carre == 64 9 carre == 81 10 carre == 100 */ </PRE> </TD></TABLE><BR> <LI>Code objet (option -c) <LI>Code assembleur (option -S)<P></P> Voici un exemple d'utilisation. D'abord, le programme<BR> <TABLE BORDER=1><TD> <PRE>#include &lt;stdio.h&gt; int fct (int n) { int i, v1, v2; v1 = 1; v2 = 1; i = 2; while (i <= n) { v2 += v1; v1 = v2 - v1; i++; } return v2; } int ftc (int n) { if (n < 2) return 1; return ftc(n-1) + ftc (n-2); } main () { int n = 0; while (n < 20) { printf("f(%3d)\t== %d\n",n, fct(n)); printf("\t== %d\n", ftc(n)); n++; } } </PRE> </TD></TABLE><BR> Une deuxième version, à peine différente&nbsp;: <TABLE BORDER=1><TD> <PRE>#include &lt;stdio.h&gt; int fct (int n) { int i, v1, v2; v1 = 1; v2 = 1; for (i = 2; i <= n; i++) { v2 += v1; v1 = v2 - v1; } return v2; } int ftc (int n) { if (n < 2) return 1; return ftc(n-1) + ftc (n-2); } main () { int n; for (n = 0; n < 20; n++) { printf("f(%3d)\t== %d\n",n, fct(n)); printf("\t== %d\n", ftc(n)); } } </PRE> </TD></TABLE><BR> Voici le code assembleur généré par ces deux programmes, il est identitque&nbsp;:<BR> <TABLE BORDER=1><TD> <PRE> .text .globl _fct _fct: LFB3: pushq %rbp LCFI0: movq %rsp, %rbp LCFI1: movl %edi, -20(%rbp) movl $1, -8(%rbp) movl $1, -12(%rbp) movl $2, -4(%rbp) jmp L2 L3: movl -8(%rbp), %eax addl %eax, -12(%rbp) movl -8(%rbp), %edx movl -12(%rbp), %eax subl %edx, %eax movl %eax, -8(%rbp) incl -4(%rbp) L2: movl -4(%rbp), %eax cmpl -20(%rbp), %eax jle L3 movl -12(%rbp), %eax leave ret LFE3: .globl _ftc _ftc: LFB4: pushq %rbp LCFI2: movq %rsp, %rbp LCFI3: pushq %rbx LCFI4: subq $24, %rsp LCFI5: movl %edi, -20(%rbp) cmpl $1, -20(%rbp) jg L7 movl $1, -24(%rbp) jmp L9 L7: movl -20(%rbp), %edi decl %edi call _ftc movl %eax, %ebx movl -20(%rbp), %edi subl $2, %edi call _ftc addl %eax, %ebx movl %ebx, -24(%rbp) L9: movl -24(%rbp), %eax addq $24, %rsp popq %rbx leave ret LFE4: .cstring LC0: .ascii "f(%3d)\11== %d\12\0" LC1: .ascii "\11== %d\12\0" .text .globl _main _main: LFB5: pushq %rbp LCFI6: movq %rsp, %rbp LCFI7: subq $16, %rsp LCFI8: movl $0, -4(%rbp) jmp L12 L13: movl -4(%rbp), %edi call _fct movl -4(%rbp), %esi movl %eax, %edx leaq LC0(%rip), %rdi movl $0, %eax call _printf movl -4(%rbp), %edi call _ftc movl %eax, %esi leaq LC1(%rip), %rdi movl $0, %eax call _printf incl -4(%rbp) L12: cmpl $19, -4(%rbp) jle L13 leave ret LFE5: .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support EH_frame1: .set L$set$0,LECIE1-LSCIE1 .long L$set$0 LSCIE1: .long 0x0 .byte 0x1 .ascii "zR\0" .byte 0x1 .byte 0x78 .byte 0x10 .byte 0x1 .byte 0x10 .byte 0xc .byte 0x7 .byte 0x8 .byte 0x90 .byte 0x1 .align 3 LECIE1: .globl _fct.eh _fct.eh: LSFDE1: .set L$set$1,LEFDE1-LASFDE1 .long L$set$1 LASFDE1: .long LASFDE1-EH_frame1 .quad LFB3-. .set L$set$2,LFE3-LFB3 .quad L$set$2 .byte 0x0 .byte 0x4 .set L$set$3,LCFI0-LFB3 .long L$set$3 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$4,LCFI1-LCFI0 .long L$set$4 .byte 0xd .byte 0x6 .align 3 LEFDE1: .globl _ftc.eh _ftc.eh: LSFDE3: .set L$set$5,LEFDE3-LASFDE3 .long L$set$5 LASFDE3: .long LASFDE3-EH_frame1 .quad LFB4-. .set L$set$6,LFE4-LFB4 .quad L$set$6 .byte 0x0 .byte 0x4 .set L$set$7,LCFI2-LFB4 .long L$set$7 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$8,LCFI3-LCFI2 .long L$set$8 .byte 0xd .byte 0x6 .byte 0x4 .set L$set$9,LCFI5-LCFI3 .long L$set$9 .byte 0x83 .byte 0x3 .align 3 LEFDE3: .globl _main.eh _main.eh: LSFDE5: .set L$set$10,LEFDE5-LASFDE5 .long L$set$10 LASFDE5: .long LASFDE5-EH_frame1 .quad LFB5-. .set L$set$11,LFE5-LFB5 .quad L$set$11 .byte 0x0 .byte 0x4 .set L$set$12,LCFI6-LFB5 .long L$set$12 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$13,LCFI7-LCFI6 .long L$set$13 .byte 0xd .byte 0x6 .align 3 LEFDE5: .subsections_via_symbols </PRE> </TD></TABLE><BR> </PRE> <!--- </TD></TABLE><BR> <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> </PRE> ---> <LI>Édition de liens (option -o) </OL> <LI>Écriture sur fichiers<P> Voici un programme qui permet de travailler. D'abord son Makefile&nbsp;: </TD></TABLE><BR> <TABLE BORDER=1><TD> <PRE># Compilation generique par Bourdin CC=gcc SRC=trc.c man.c SRCDIRECT=miam.c fibiter.c direct.c SRCDIRICT=miim.c fibiter.c dirict.c OBJ=$(SRC:.c=.o) OBJDIRECT=$(SRCDIRECT:.c=.o) OBJDIRICT=$(SRCDIRICT:.c=.o) FLAGS=-Wall fil: $(OBJ) mydef.h $(CC) -o $@ $^ rm nom.dat fool: $(OBJDIRECT) direct.h $(CC) -o $@ $^ rm fib.dat fiil: $(OBJDIRICT) dirict.h $(CC) -o $@ $^ rm fii.dat %.o: %.c $(CC) -o $@ -c $< $(CFLAGS) clean: rm *.o *~ core hop: for i in 0 1 2 3 4 5 6 7 8 9 do ./fil $i ; done </PRE> </TD></TABLE><BR> </PRE> Ensuite, pour s'y retrouver un peu, un fichier man.c. </TD></TABLE><BR> <TABLE BORDER=1><TD> <PRE>/*man.c*/ #include <stdio.h> #include "mydef.h" #define NOM "nom.dat" main (int argc, char * * argv) { FILE * fichier; int i, j, v, w; if (argc == 2) { i = atoi (argv [1]); if ((fichier = fopen(NOM,"r"))!= NULL) { // printf("On cherche fib(%d)\n",i); v = liren (fichier, i); printf("fib(%d) = %d\n",i,v); } else { if ((fichier = fopen(NOM,"w+"))== NULL) { printf(" Revenons a une fonction classique\n"); v = fib (i); printf("fib(%d) = %d\n",i,v); } else { v = remplirn (fichier, i); fseek (fichier, -10L, 2); fscanf(fichier,"%d",&w); printf("fib(%d) = %d ou %d\n",i,v, w); } } fclose(fichier); } else if (argc == 3) { i = atoi (argv [1]); j = atoi (argv [2]); // printf("les valeurs de %d a %d\n",i,j); if ((fichier = fopen(NOM,"r"))!= NULL) { for ( ; i <= j; i++) { v = liren (fichier, i); printf("fib(%3d) = %10d\n",i,v); } } else { if ((fichier = fopen(NOM,"w+"))== NULL) { printf("Revenons a une fonction classique\n"); for ( ; i <= j; i++) { v = fib (i); printf("fib(%d) = %d\n",i,v); } } else { v = remplirn (fichier, i); fseek (fichier, -10L, 2); fscanf(fichier,"%d",&w); printf("fib(%d) = %d ou %d\n",i,v, w); } } fclose(fichier); } else { /* Taille indefinie */ if ((fichier = fopen(NOM,"r"))== NULL) { printf("il faut creer ce fichier \n\n"); fichier = fopen(NOM,"w+"); remplir (fichier); lire (fichier); fclose (fichier); } else { lire (fichier); close(fichier); } } } </PRE> </TD></TABLE><BR> </PRE> Enssuite quelques pointeurs sur des fichiers utilisés pour la compilation. <UL> <LI><A HREF=mydef.h> le header</A> <LI><A HREF=trc.c> trc.c</A> <LI><A HREF=miam.c> miam.c</A> <LI><A HREF=miim.c> miim.c</A> <LI><A HREF=fibiter.c> fibiter.c</A> <LI><A HREF=dirict.c> dirict.c</A> <LI><A HREF=direct.c> direct.c</A> </UL> <LI>Temps<P> Pour faire le calcul du binôme, nous utiliserons le fichier <TT>types.h</TT> suivant&nbsp;: <TABLE BORDER=1><TD> <PRE>#include <time.h> #include <stdio.h> #define MAX 500 typedef int pascal [MAX] [MAX]; typedef unsigned int Uint; extern double bin (Uint, Uint, pascal); extern double bin_rec (Uint, Uint, pascal); extern double bin_aux (Uint, Uint); extern double bin_tab (Uint, Uint, pascal); extern double bin_fac (Uint, Uint, pascal); extern double fact (Uint); extern void controler (Uint *, Uint *); extern void inverser (Uint *, Uint *); </PRE> </TD></TABLE><BR> Voici un fichier de calcul du binôme. <TABLE BORDER=1><TD> <PRE> #include "types.h" double bin_rec (Uint n, Uint m, pascal t) { return bin_aux (n,m); } double bin_aux (Uint n, Uint m) { if (m == 0) return 1.0; if (n==0) return 0.0; if (n == m) return 1.0; return bin_aux (n-1,m) + bin_aux (n-1, m-1); } double bin_fac (Uint n, Uint m, pascal t) { return (fact(n)/(fact(n-m)*fact(m))); } double fact (Uint n) { if (n) { return (float) n * fact (n-1); } return 1.0; } </PRE> </TD></TABLE><BR> En voici un autre, peut-être plus rapide. <TABLE BORDER=1><TD> <PRE> #include "types.h" #include "types.h" double bin (Uint n, Uint m, pascal t) { int i, j; controler (&n, &m); t [0][0] = 1.0; for (j=1; j<=m ; j++ ) { t [0][j] = 0.0; } for (i=1; i<=n; i++) { t [i][0] = 1.0; for (j=1; j<=m; j++ ) { t[i][j] = t[i-1][j] + t [i-1][j-1]; } } return t[n][m]; } </PRE> </TD></TABLE><BR> Il vous faut aussi le fichier qui contient le <TT>main</TT>&nbsp;: <TABLE BORDER=1><TD> <PRE>#include "types.h" main (int argc, char * argv[]) { clock_t cp; int tps_init, tps_crt, dtps; Uint i, j; pascal mat; double val; if (argc != 3) { printf("Il me faut deux arguments pour calculler Pascal\n\n"); return 0; } i = atoi (argv [1]); j = atoi (argv [2]); printf("i %d et j %d\n",i,j); controler(&i,&j); printf("Trois methodes pour calculer le triangle de Pascal\n\n"); cp = clock () ; tps_init =(int)cp; val = bin (i, j, mat) ; tps_crt = (int) clock(); dtps = tps_crt - tps_init; printf("iteratif : %d, %d = \t\t%8.1f\n",i, j, val); printf ("de %d a %d soit : \t : %d \n", tps_init, tps_crt, dtps); tps_init =(int)clock(); val = bin_fac (i, j, mat) ; tps_crt = (int)clock(); dtps = tps_crt - tps_init; printf("avec factorielle %d, %d = \t%8.1f\n",i, j, val); printf ("de %d a %d soit : \t : %d \n", tps_init, tps_crt, dtps); tps_init =(int)clock(); val = bin_rec (i, j, mat) ; tps_crt = (int)clock(); dtps = tps_crt - tps_init; printf("recursif %d, %d = \t\t%8.1f\n",i, j, val); printf ("de %d a %d soit : \t : %d \n", tps_init, tps_crt, dtps); printf ("ou en kilo tops d'horloge \t : %d \n", (1000*dtps)/CLOCKS_PER_SEC); printf ("Par seconde il y a %d tops d'horloge \n", CLOCKS_PER_SEC); } </PRE> </TD></TABLE><BR> Voici ce qui se passe quand on l'utilise. <TABLE BORDER=1><TD> <PRE> mu.ai.univ-paris8.fr: binome 10 20 i 10 et j 20 Trois methodes pour calculer le triangle de Pascal iteratif : 20, 10 = 184756.0 de 2070 a 2133 soit : : 63 avec factorielle 20, 10 = 184756.0 de 2169 a 2173 soit : : 4 recursif 20, 10 = 184756.0 de 2182 a 5693 soit : : 3511 ou en kilo tops d'horloge : 3 Par seconde il y a 1000000 tops d'horloge </PRE> </TD></TABLE><BR> <!--- <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> ---> <LI><H3><A NAME="ptr">Indirections</A></H3> <OL> <LI><B>Un exemple de liste</B><P> D'abord un fichier <TT>ptr.h</TT> de définitions de types et de spécifications de fonctions&nbsp;: <TABLE BORDER=1><TD> <PRE>#include &lt;stdio.h> #include &lt;stdlib.h> struct binome { int a; int b; } ; typedef struct binome binome; struct cell { int v; struct cell * pred; } ; typedef struct cell cell; typedef struct cell * pcel; typedef void (* ptrfct) (); extern int calc (int) ; extern pcel couic (int) ; extern pcel cou (int) ; extern pcel rouci (pcel) ; extern void seeit (pcel) ; extern pcel ote (int, pcel) ; extern pcel cherche (int, pcel) ; extern int nbelel (pcel) ; extern pcel resni (pcel, pcel); extern pcel remy (pcel); extern binome newval (int); extern void fcta (); extern void fctb (); extern void g (void (*) ()); extern void fcttest (); extern int menu (); extern void faire (); /* Notez que toutes ces fonctions ne sont pas encore definies */ </PRE> </TD></TABLE><BR> Notez que pour les fonctions non encore définies, vous pouvez commencer par en écrire une version "vide" où le corps de la fonction ne contient rien, ça fait une alerte, un <I>warning</I>, mais ce n'est pas grave.<BR> Ensuite il faut un fichier qui crée la liste, en fonction d'une valeur donnée en argument. Ici le fichier sera nommé <TT>creation.c</TT>. <TABLE BORDER=1><TD> <PRE>#include "ptr.h" pcel couic (int n) { pcel un, crt, sui, apres; if (n < 2) return (pcel) 0; crt = (pcel) malloc (sizeof(cell)); crt->v = 1; crt->pred = (pcel) malloc (sizeof(cell)); sui = crt->pred ; sui->v = 1; sui->pred = (pcel) 0 ; un = crt; n -= 2; while (n--) { sui->pred = (pcel) malloc (sizeof(cell)); apres = sui->pred; apres->v = (sui->v + crt->v) % 13 ; apres->pred = (pcel) 0; crt = sui; sui = apres; } return un; } binome newval (int para) { static binome b; if (para == 1) { b.a = 1; b.b = 1; return b; } b.a += b.b; b.b = b.a - b.b; return b; } pcel cou (int n) { pcel un, crt, sui, apres; binome b; if (n < 2) return (pcel) 0; b = newval(1); crt = (pcel) malloc (sizeof(cell)); crt->v = b.b; crt->pred = (pcel) malloc (sizeof(cell)); sui = crt->pred ; sui->v = b.a; sui->pred = (pcel) 0 ; un = crt; n -= 2; while (n--) { sui->pred = (pcel) malloc (sizeof(cell)); apres = sui->pred; b = newval(0); apres->v = (b.a) ; apres->pred = (pcel) 0; crt = sui; sui = apres; } return un; } </PRE> </TD></TABLE><BR> Il faut, bien sûr, rajouter un fichier <TT>main.c</TT> et un fichier de manipulation de listes, comme ce que nous avons vu en cours (concaténation, inversion, insertion, tri). Faire aussi les fonctions qui&nbsp;: <UL><LI>compte ne nombre d'éléments de la liste <LI>cherche si une valeur appartient à la liste <LI>fabrique une liste formée des carrés de toutes les valeurs de la liste que nous avons créée. </UL> Quelques liens vers les fichiers utiles, mais pas tous&nbsp;! <UL><LI><A HREF=Ptr/ptr.h> fichier ptr.h </A> <LI><A HREF=Ptr/ptr.c> fichier ptr.c </A> <LI><A HREF=Ptr/main.c> fichier main.c </A> <LI><A HREF=Ptr/Makefile> fichier Makefile </A> </UL> Vous devez donc essayer tout cela et y rajouter les fonctions demandées par ailleurs. <BR><P> <LI><B>Arbres</B><P> Puisque nous devons travailler sur des arbres, il nous faut une structure&nbsp;: <TABLE BORDER=1><TD> <PRE>#define NBN 4 struct noeud { int nb; float val; struct noeud * fils [NBN]; } ; typedef struct noeud noeud; typedef struct noeud * arbre; typedef unsigned int uint; </PRE> </TD></TABLE><BR> Nous allons donc pouvoir utiliser les fonctions vues en cours, surtout si nous savons créer un tel arbre&nbsp;: <TABLE BORDER=1><TD> <PRE>float calcul (int i) { float x; x = 0.0; while (x * x < i) x += 0.1; return x; } arbre consarb (int n) { arbre racine, a; int i; if (!n) { return NULL; } racine = (arbre) malloc (sizeof(noeud)); racine->nb = n; racine->val = calcul(n); for (i=0; i < NBN; i++) racine->fils[i] = NULL; while (--n) { racine = addarb (n, racine); } return racine; } arbre addarb (int n, arbre a) { arbre crt; int i, j; for (i = 0; i < NBN; i++) { if (! a->fils[i]) { crt = (arbre) malloc (sizeof(noeud)); // crt = (noeud) malloc (sizeof(noeud)); a->fils[i] = crt; crt = a->fils[i]; crt->nb = n; crt->val = calcul (n); for (j = 0; j < NBN; j++) crt->fils[j] = NULL; return a; } } /* modifié pour mieux convenir, le 15/11/11 */ for (i = 0; i < NBN; i++) { if (n > a->fils[i]->nb) { a->fils[i] = addarbre(n, a->fils[i], prof); return a; } } i = n % NBN; a->fils[i] = addarbre(n, a->fils[i], prof); return a; } </PRE> </TD></TABLE><BR> Nous avons vu une fonction qui cherche si une valeur apparaît dans cet arbre&nbsp;: <TABLE BORDER=1><TD> <PRE> uint yest (int n, arbre a) { uint nbf, i, k; if (! a) return (uint) 0; if (n == a->nb) return (uint) 1; for (i = 0; i < NBN ; i++) if (yest (n, a->fils[i])) return (uint) 1; return (uint) 0; } </PRE> </TD></TABLE><BR> Il vous reste à écrire &nbsp;: <UL> <LI>Une fonction qui compte le nombre d'occrurences de la valeur dans l'arbre. <LI>Une fonction qui calcule le nombre de feuilles de l'arbre (ce sont les noeuds qui n'ont aucun descendant). <LI>Une fonction qui calcule la profondeur de l'arbre. <LI>Une fonction qui mémorise et renvoie, sous la forme d'un tableau, le chemin entre la racine et un somet que l'on a trouvé. <LI>Une fonction qui mémorise et renvoie, sous la forme d'un tableau, le chemin entre la racine et le somet de valeur <TT>n</TT> le plus proche. </UL> <!--- <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> ----> <LI><B>Pointeurs de fonctions</B><P> Puisque nous pouvons travailler avec des pointeurs que ne travaillons-nous avec des pointeurs de fonction&nbsp;?<P> Voici d'abord un exemple de définition&nbsp;: <TABLE BORDER=1><TD> <PRE>typedef void (* ptrfct) (); extern void fcta (); extern void fctb (); extern void g (void (*) ()); </PRE> </TD></TABLE><BR> Il est assez facile d'utiliser ces fonction, c'est fait dans le fichier <A HREF=Ptr/menu.c> <TT>menu.c</TT> </A> ci-joint. Voyons un peu le détail&nbsp;: <TABLE BORDER=1><TD> <PRE>#include "ptr.h" void fcta () { printf(" a "); } void fctb () { printf(" b "); } void g (void (* fct) ()) { printf("g appelle :"); fct(); printf("\n"); } void fcttest () { g(fcta); g(fctb); } int menu () { int n; n = 0; while (!n) { printf("Choisissez entre la fonction a (tapez 1)\n"); printf("et la fonction b (tapez 2) :\n"); scanf("%d",&n); if (n==1 || n==2) break; } return n-1; } void faire () { int n; ptrfct tf [] = {fcta, fctb}; n = menu(); tf[n](); } </PRE> </TD></TABLE><BR> Dans les deux cas vous voyez qu'un <I>pointeur de fonctions</I> n'est rien d'autre qu'un pointeur comme tous les autres, il contient simplement l'adresse du début de la fonction.<P> <A NAME=imag><LI><B>Pointeurs de fonctions, illustration</B><P></A> Sous OpenGL, on doit utiliser des pointeurs de fonctions. Par exemple la fonction définie par&nbsp;: <TABLE BORDER=1><TD> <PRE> void Mouse(int button, int state, int x, int y){ switch(button){ case GLUT_LEFT_BUTTON: break; case GLUT_MIDDLE_BUTTON: break; case GLUT_RIGHT_BUTTON: break; } glutPostRedisplay(); } </PRE> </TD></TABLE><BR> sera mémorisée dans le <TT>main</TT> comme fonction de gestion de souris. D'un côté c'est logique, de l'autre cette affectation n'est possible que parce que la fonction est correctement définie dans glut. <TABLE BORDER=1><TD> <PRE> int main(int argc, char **argv) { if (argc<2) { fprintf(stderr, "Usage : palette nom_de_fichier\n"); exit(0); } glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE); glutInitWindowSize(640,480); glutInitWindowPosition(0, 0); glutCreateWindow("VPUP8"); Init(argv[1]); glutCreateMenu(menuFunc); glutAddMenuEntry("Informations", 0); glutAddMenuEntry("Ouvrir", 3); glutAddMenuEntry("Sauver", 4); glutAddMenuEntry("Noir et Blanc", 6); glutAddMenuEntry("Quit", 5); glutAttachMenu(GLUT_LEFT_BUTTON); glutDisplayFunc(Display); glutReshapeFunc(Reshape); glutKeyboardFunc(Keyboard); glutMouseFunc(Mouse); glutMainLoop(); return 1; } </PRE> </TD></TABLE><BR> Voici donc les programmes présentés en cours du 15/11/2011. <UL> <LI><A HREF=SI11/makefile> le makefile pour tout compiler<BR>... qui a fonctionné sur Octopussy et sur Langoustine. Sur une autre machine il ne fonctionne peut-être pas, il faut alors le retravailler, vous-mêmes. </A> <LI><A HREF=SI11/main.c> main.c </A><BR> <LI><A HREF=SI11/bmp.c> bmp.c pour lire les bmp. </A> <LI><A HREF=SI11/bmp.h> bmp.h </A><BR> <LI><A HREF=SI11/modif.c> modif.c </A><BR> <LI><A HREF=SI11/rgb_hls.c> rgb_hls </A><BR> <LI><A HREF=SI11/grey.c> grey, pour faire des grisés, un peu plus complexes, avec changement de taille de l'image </A> <LI><A HREF=SI11/sci.c> pour les SCI </A> <LI><A HREF=SI11/ciel.bmp> une image de ciel </A> <LI><A HREF=SI11/dcp.bmp> une photo d'une peinture impressionniste </A> <LI><A HREF=SI11/ciel4noir.bmp> une image de ciel arrangé. </A> <LI><A HREF=SI11/image.bmp> une image. </A> <LI>une image <A HREF=IMG/Cordiliere2_V3.bmp> des Andes </A><BR> <LI>une image <A HREF=IMG/Daulagueri.bmp> du Daulagheri </A><BR> <LI>une image <A HREF=IMG/Kili_glacier.bmp> du Kilimanjaro </A><BR> <LI>une seconde image <A HREF=IMG/Kili_mais.bmp> du Kilimanjaro </A> (de loin)<BR> <LI>une image <A HREF=IMG/Refuges.bmp> d'altitude </A><BR> <LI>une image <A HREF=IMG/Stupa.bmp> de Stupa </A><BR> <LI>une image <A HREF=IMG/requin_leopard.bmp> de requin </A><BR> </UL> J'espère ne pas en avoir oublié, mais si c'est le cas, il faut me prévenir au plus tôt.<P> Une fois que tout ceci fonctionne, compilation et exécution comprises, il vous reste à écrire quelques fonctions comme&nbsp;: <OL> <LI>modifier la fonction gris pour qu'elle tienne davantage compte de la luminosité. On considère que l'oeil est surtout sensible au vert (coefficient 1.5), puis au rouge (coefficient 1) et enfin au bleu (coefficient 0.5). Modifier en conséquence le calcul du gris à afficher. <LI>modifier la fonction <TT>vert</TT> pour, à la fois, diminuer l'importance des nuances rouge et bleues et ajouter de l'intensité au vert. <LI>modifier la fonction <TT>vert</TT> pour faire un "négatif" de l'image, c'est-à-dire que chaque valeur prendra son complémentaire (sur 8 bits). <LI>modifier la fonction <TT>vert</TT> pour, cette fois, diminuer l'écart entre les trois valeurs de chaque pixel.<P> <LI>modifier les fonctions précédentes de façon à réduire la saturation (augmenter la composante la plus faible en direction de la seconde). </UL> <!--- <LI>tenir compte des valeurs des neuf pixels du voisinage de façon à <I>lisser</I> l'image.<P> <LI>Histogramme<BR> Pour chaque niveau de couleur, un histogramme sert à calculer combien de pixels ont cette couleur. Ici, il s'agira de trois tableaux (un pour chaque teinte R, G et B) de 256 cases (0, 1, ..., 255). Par exemple pour le rouge, tr[0] indique combien de pixels ont leur rouge à 0, tr[1] indique combien de pixels ont leur rouge à 1, tr[2] indique...<BR> Par mesure de régularité, on ramène cette valeur à 255 par une multiplication par 255 et une division par le nombre de pixels de l'image.<P> L'histogramme de masse est, pour chaque case, la somme des cases inférieures. Dans trm[2] il y a donc tr[0]+tr[1]+tr[2]. <UL><LI>Calculer l'histogramme des rouges, des verts et des bleus. <LI>Calculer l'histogramme de masse des rouges, des verts et des bleus. <LI>Remplacer, pour chaque pixel, sa valeur en rouge (r) par la valeur de trm correspondante (trm[r]). Normalement on assiste à une amélioration des contrastes. </UL> </OL> <A NAME=partiel><LI>Premier partiel<BR></A> Vous pouvez relire le <A HREF=li2_p_09.pdf> sujet du partiel</A> et le refaire, autant que nécessaire. <P> <A NAME=partiel2><LI>Deuxième partiel<BR></A> Vous pouvez relire le <A HREF=li2_pf_09.pdf> sujet du deuxième partiel</A> et le refaire, autant que nécessaire. <P> </OL> <LI>Fichiers<P> <OL> <LI>Bibliothèques standard<P> Vous devriez les connaître, regardez donc <A HREF="http://www.utas.edu.au/infosys/info/documentation/C/CStdLib.html"> ce site</A> pour en savoir plus.<P> <P><LI><A NAME=files>La gestion de fichiers<P> Voici quelques fonctions permettant d'ouvrir, d'écrire et de lire dans un fichier, de façon paramétrée.<BR> <UL><LI><A HREF=Makefile> le Makefile</A> <LI><A HREF=trc.c> le fichier trc.c </A> <LI><A HREF=truc.c>le fichier truc.c </A> <LI><A HREF=man.c>le fichier man.c </A> <LI><A HREF=main.c>le fichier main.c </A> </UL> Vous devrez écrire vous-mêmes le <TT>header</TT> correspondant. Il ne récèle pas de difficulté. <!--- <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> <!--- <TABLE BORDER=1><TD> <PRE> </PRE> </TD></TABLE><BR> <LI><B> </B><P> ---> </UL> </OL> <P>Dernière mise à jour&nbsp;: 28/03/12</P>