INFO517-cours2
Rappels et précisions; fonctions; tableaux.
Les exemples vus en cours
puissance-v1.c <source lang="c">
- include<stdio.h>
- define MAXEXP 16
/* Fonction puissance(a: int, b: int) : int
* renvoie a à la puissance b, si b positif, 1 sinon */
int puissance (int a, int b) { int i, ret ; ret = 1 ; for (i=0; i<b; ++i) /* ++i incrémente i */ ret = a * ret ; return ret ; }
/* Procédure affiche(a: int, b: int)
* formatte le résultat de puissance(a,b) */
void affiche(int a, int b) { printf("%2d^%2d = %10d\n",a,b,puissance(a,b)) ; }
/* Fonction principale: affiche les puissances de 2, de 1 à 2^MAXEXP */ void main () { int i ; for (i=0; i<=MAXEXP; ++i) affiche(2,i) ; } </source>
puissance-v2.c
<source lang="c">
- include<stdio.h>
- define MAXEXP 16
/* Prototype de la fonction puissance(a: int, b: int) : int
*/
int puissance (int a, int b) ;
/* Procédure affiche(a: int, b: int)
* formatte le résultat de puissance(a,b) */
void affiche(int a, int b) { printf("%2d^%2d = %10d\n",a,b,puissance(a,b)) ; }
/* Fonction principale: affiche les puissances de 2, de 1 à 2^MAXEXP */ void main () { int i ; for (i=0; i<=MAXEXP; ++i) affiche(2,i) ; }
/* Code de la fonction puissance :
* puissance(a,b) renvoie a à la puissance b, si b positif, 1 sinon */
int puissance (int a, int b) { int ret ; ret = 1 ; /* On utilise l'argument b comme une variable locale */ for (/* pas d'initialisation nécessaire */; b>0; --b) ret = a * ret ; return ret ; } </source>
fibonacci.c
<source lang="c">
- include<stdio.h>
- define MAX 30
/* calcule u[n], où u[0]=u[1]=1 et u[n+2]=u[n+1]+u[n] */ int fibo (int n, int rec) { if (n<=1) return 1 ; else return (fibo(n-1,rec+1)+fibo(n-2,rec+1)) ; }
/* affiche fibo(n) pour n de 0 à MAX */ int main () { int i ; for (i=0;i<=MAX;++i) printf("fibo(%2d)=%8d\n",i,fibo(i,0)) ; return 0 ; } </source>
tracerec.c
<source lang="c">
- include<stdio.h>
- define N 15
/* Procédure blanks(n: int)
* insère n espaces. */
void blanks (int n) {
for(;n>0;--n) putchar(' ') ;
}
/* Calcule fibo(n) (voir fibo.c) et affiche le résultat.
* Cet affichage dans la fonction permet de tracer le * flot de récursion (l'ordre dans lequel les appels se font). * * On représente la profondeur de récursion par l'indentation, * au moyen du second argument : tous les affichages sont décalés * de rec espaces. L'entier rec est incrémenté dans l'appel récursif, * et on démarre avec rec=0 dans main() * */
int fibo_rec (int n, int rec) {
blanks(rec) ; printf("fibo(%2d)=?\n",n) ;
if (n<=1) {
blanks(rec) ; printf("fibo(%2d)=1\n",n) ;
return 1 ;
} else {
/* On peut déclarer des variables locales à un bloc */
int ret=fibo_rec(n-1,rec+1)+fibo_rec(n-2,rec+1) ;
blanks(rec) ; printf("fibo(%2d)=%d\n",n,ret) ;
return ret ;
}
}
/* Calcule fibo(N) avec affichage des étapes de récursion */
int main () {
fibo_rec(N,0) ;
return 0 ;
} </source>
segfault.c
<source lang="c">
/* CE CODE EST VOLONTAIREMENT FAUTIF ! */
/* Notre première erreur de segmentation:
* les appels récursifs s'empilent sans limite et on sort de la mémoire * disponible. */
- include<stdio.h>
- define MAX 30
/* calcule u[n], où u[0]=u[1]=1 et u[n+2]=u[n+1]+u[n] */ int fibo (int n, int rec) { return (fibo(n-1,rec+1)+fibo(n-2,rec+1)) ; }
/* affiche fibo(n) pour n de 0 à MAX */ int main () { int i ; for (i=0;i<=MAX;++i) printf("fibo(%2d)=%8d\n",i,fibo(i,0)) ; return 0 ; } </source>
textstat.c
<source lang="c">
- include<stdio.h>
/* En théorie, les valeurs entières des caractères
* sont dans un intervalle non précisé par la norme. * * Dans cet exemple, on considère que les caractères sont des entiers sur 8 * bits non signés (cf. CHAR_MIN, CHAR_MAX). * * Ceci était passé sous silence lors du cours. * */
- define CHAR_MIN 0
- define CHAR_MAX 255
/* CHAR_NUM = CHAR_MAX - CHAR_MIN + 1 */
- define CHAR_NUM 256
/* Une macro évidente */ void aff (char c, int n) { printf("%c:%2d ",c,n) ; }
/* Compte le nombre d'occurrences de chaque caractère
* et affiche certains résultats */
int main() { int c, i ; int nb [CHAR_NUM] ;
/* Mise à zéro */ for (i=0;i<CHAR_NUM;++i) nb[i]=0 ;
/* Calcul */ while((c=getchar()) != EOF) ++nb[CHAR_MIN+c] ;
/* Affichage */
/* Les lettres minuscules sont consécutives de 'a' à 'z'. */
printf("Minuscules:\n") ; for (c='a'; c<='z' ; ++c) aff(c,nb[CHAR_MIN+c]) ;
/* De même pour les majuscules de 'A' à 'Z'. */
printf("\nMajuscules:\n") ; for (c='A'; c<='Z' ; ++c) aff(c,nb[CHAR_MIN+c]) ;
/* Et les chiffres de '0' à '9'. */
printf("\nChiffres:\n") ; for (c='0'; c<='9' ; ++c) aff(c,nb[CHAR_MIN+c]) ;
printf("\nSauts de lignes: %d\n",nb[CHAR_MIN+'\n']) ;
return 0 ; }
</source>
Exercices pour le 6 octobre
Sur les fonctions
- Réécrire le programme conversion.c en utilisant une fonction pour l'affichage. Rendre ce programme plus modulaire en écrivant une procédure avec le prototype void francs_euros (int min, int max, int pas) qui afffiche la conversion de n francs en euros pour n variant de min à max par pas de pas et une procédure void euros_francs (int min, int max, int pas) qui affiche la même chose mais dans l'autre sens de conversion.
- Écrire une fonction int fact (int n) qui calcule la factorielle de n de deux manières différentes: une par récursion, une en utilisant une boucle. Essayer ces fonctions sur des valeurs pas trop petites et détecter quand ça dégénère.
Sur les tableaux et les chaînes
- Écrire une procédure void aff (int t[], int n) qui affiche les n premiers éléments du tableau t.
- On donne le programme:
<source lang="c">
- include <stdio.h>
void incr (int n) { ++n ; }
void incr_t0 (int t[]) { ++t[0] ; }
int main () { int n = 0 ; int t[1] = { 0 } ; incr(n) ; incr_t0(t) ; printf("n: %d\n",n) ; printf("t[0]: %d\n",t[0]) ; return 0 ; } </source> Compiler et exécuter ce programme. Que remarque-t-on ? Qu'en déduire sur les tableaux comme arguments de fonctions.
- Que fait le programme fin_chaine.c suivant ? Expliquer.
<source lang="c">
- include <stdio.h>
int main () { printf("Bateau.\n\0Et puis aussi...") ; return 0 ; } </source>
- Écrire un programme qui affiche les lignes données en entrée seulement si elles comportent plus de 20 caractères. Penser à structurer intelligemment.
- Écrire une fonction void pal(char s[]) qui renvoie 1 si la chaîne s est un palindrome et 0 sinon.
- Écrire une procédure void renverse(char s[]) qui renverse la chaîne s.
Solutions possibles
Un exemple complet de programme utilisant les fonctions (on n'hésite pas à en rajouter):
#include <stdio.h>
#define UN_EURO 6.55957 /* un euro en francs */
void aff_col (int a, float b)
{
printf(" %3d\t\t %6.2f\n", a, b ) ;
}
void aff_en_tete (const char a[], const char b[])
{
printf("%s\t\t%s\n", a, b ) ;
}
void table_conv (float taux, int min, int max, int pas)
{
int i ;
if (pas > 0)
/* si le pas est positif on va du min au max */
for (i=min; i<=max; i=i+pas)
aff_col(i,taux*i) ;
else if (pas < 0)
/* si le pas est négatif on va du max au min */
for (i=max; i>=min; i=i+pas)
aff_col(i,taux*i) ;
}
void francs_euros (int min, int max, int pas)
{
aff_en_tete("Francs","Euros") ;
table_conv (1/UN_EURO,min,max,pas) ;
}
void euros_francs (int min, int max, int pas)
{
aff_en_tete("Euros","Francs") ;
table_conv (UN_EURO,min,max,pas) ;
}
int main()
{
francs_euros(10,100,10) ;
euros_francs(1,10,-1) ;
return 0 ;
}
Sur les factorielles:
#include <stdio.h>
#define MAX 30
/* calcule n! par récurrence sur n */
unsigned long int fact_rec (unsigned int n) {
if (n<=1) return 1 ;
else return n*fact_rec(n-1) ;
}
/* calcule n! par comme un produit itéré */
unsigned long int fact_it (unsigned int n) {
unsigned int i ;
unsigned long int acc = 1;
for (i=2;i<=n;++i)
acc=i*acc ;
return acc ;
}
/* fonctions d'affichage */
void aff (unsigned int n, unsigned long int res, const char nom[]) {
printf("On calcule %u!=%lu par %s\n", n, res, nom) ;
}
void aff_fact_rec (unsigned int n) {
aff(n,fact_rec(n),"fact_rec") ;
}
void aff_fact_it (unsigned int n) {
aff(n,fact_it(n),"fact_it") ;
}
/* affiche fact_rec(n) et fact_it(n) pour n de 0 à MAX */
/* noter que malgré toutes nos précautions, ça dégénère vite,
* car n! croit vite */
int main () {
unsigned int i ;
for (i=1; i<MAX; ++i) {
aff_fact_rec(i) ;
aff_fact_it(i) ;
}
return 0 ;
}
Afficher un tableau d'entiers:
/* Affiche les n premiers éléments du tableau t sous la forme
* {t[0],t[1],...,t[n-1]}
* */
void aff (int t[], int n) {
int i ;
putchar('{') ;
for (i=0;i<n;++i) {
printf("%d",t[i]) ;
if (i!=n-1)
putchar(',') ;
}
putchar('}') ;
putchar('\n') ;
}
Afficher uniquement les lignes avec au moins 20 caractères (ici, une version plus générique):
void ligne_au_moins (int n) {
char s[n] ;
int c = getchar() ;
while (c != EOF) {
// Dans cette boucle, on traite une ligne, qui commence par c.
int i = 0 ;
// On commence par essayer de stocker les n premiers caractères :
while (c != '\n' && c != EOF && i<n) {
s[i] = c ;
++ i ;
c = getchar() ;
}
// Si on a lu n caractères sans rencontrer de retour à la ligne
// ni de fin de fichier, on recopie et on vide la ligne.
if (i==n) {
// On recopie s
for (i=0; i<n; ++i)
putchar(s[i]) ;
// On recopie la fin de la ligne
while (c != '\n' && c != EOF) {
putchar(c) ;
c = getchar() ;
}
// Retour à la ligne, si besoin
if (c == '\n') {
putchar(c) ;
c = getchar () ;
}
} else if (c == '\n') {
// Si la ligne se termine avant le n-ième caractère,
// on passe à la suivante.
c = getchar() ;
}
}
}
Pour le test de palindrome et le renversement, on a d'abord besoin de connaître la longueur de la chaîne:
unsigned int longueur (char s[]) {
unsigned int l ;
for (l=0; s[l]!='\0'; ++l) ;
return l ;
}
int pal (char s[]) {
unsigned int l = longueur(s) ;
int i ;
int ret = 1 ;
// On parcourt la moitié du tableau (au plus) et on s'arrête si jamais
// on trouve des valeurs différentes dans des cases symétriques.
for (i=0; i<l/2 && ret ; ++i)
ret = (s[i]==s[l-i-1]) ;
return ret ;
}
void renverse (char s[]) {
unsigned int l = longueur(s) ;
int i ;
char c ;
// On parcourt la moitié du tableau (au plus).
for (i=0; i<l/2 ; ++i) {
c = s[i] ;
s[i] = s[l-i-1] ;
s[l-i-1] = c ;
}
}