Jean-Jacques BOURDIN
- Université Paris 8
-
Département Programmation et Informatique Fondamentale.
- 2, rue de la Liberté
- 93526 Saint-Denis Cedex
- FRANCE
Summer 2024
Introduction
The C Language
Le Langage C
Organisation du Cours
About this course
Every morning Class + Lab == 3 hours
Every afternnon Class + Lab == 3 hours
Every evening == some exercices to do
Chaque matin 3 heures, Cours + TP
Chaque après-midi 3 heures, Cours + TP
Chaque soir, des exercices à faire
TP et exercices seront notés.
Vendredi 13/9/24, un partiel sera donné.
Bibliographie sommaire
- Le langage C - 2e éd - Norme ANSI, Kernighan et Ritchie (Dunod)
- Méthodologie de la programmation en C - 4ème édition, Jean-Pierre Braquelaire (dit Achille)
Some bindings will help you to use emacs. You'll find some at
this page , you can also type, within emacs,
Esc x and "describe-bindings".
Une série de raccourcis est
disponible dans ce fichier,
vous en trouverez d'autres en tapant
Esc x puis "describe-bindings" sous emacs.
- square
int square (int n) {
return n * n;
}
|
-
You can try cube, double, triple...
This function has to be linked to another one, the most important
one: the main function.
Cette fonction doit être accompagnée de celle qui la commande, la
grande fonction, la principale, main.
Both will be inside a simple file:
L'ensemble sera écrit et placé dans un
fichier :
cours24_01.c.
- A file
int square (int n) {
return n * n;
}
int main () {
printf("le carre de 3 est %d\n",square(2));
}
|
- to Compile
Then you have to translate this file to machine language. Our compiler is called gcc.
Il faut ensuite traduire ce texte en langage machine. Notre
traducteur (compilateur) se nomme gcc:
otake: cat cours24_01.c
#include <stdio.h>
int square (int n) {
return n * n;
}
int main () {
printf("le carre de 3 est %d\n",square(2));
}
otake: gcc cours24_01.c
otake: ls -l
-rw-r--r--@ 1 jj staff 119 29 aoû 16:07 cours24_01.c
drwxr-xr-x 225 jj staff 7200 29 aoû 16:07 .
-rwxr-xr-x 1 jj staff 33458 29 aoû 16:07 a.out
White.local: |
- and execute
otake: ./a.out
le carre de 3 est 4 |
You may correct a semantic error.
Vous pouvez corriger afin d'arriver à une phrase plus logique.
"S'il fait laid à droite, je prends à gauche" (Michel de Montaigne)
You might need to do something if a certain condition is met. For
example you don't take the road if there is a no entry sign.
Parfois il est nécessaire d'agir de façon différenciée, d'où
le if.
/* which one is bigger? */
int maxi2 (int a, int b) {
if ( a < b ) {
return b;
}
else {
return a;
}
}
|
Vous devez écrire :
- la fonction qui trouve le plus grand parmi trois nombres entiers ;
- la fonction qui trouve le plus grand parmi quatre nombres entiers ;
- la fonction qui trouve le plus petit parmi cinq nombres entiers ;
- la fonction qui trouve le second plus grand parmi trois nombres entiers ;
- la fonction qui trouve le second plus grand parmi quatre nombres entiers ;
sec4(7,3,2,9)==7
- la fonction qui trouve le second plus grand parmi cinq nombres entiers ;
Be careful
Every time one wants to use the recursivity, one has to follow the
following steps:
- Find an example with an easy to find result.
- Find a general rule, recursive.
- Verify that the general rule tends to the easy solution.
Attention :
Toute formulation récursive doit suivre les étapes suivantes :
- Trouver un cas particulier dont la valeur est donnée.
rouver une règle générale qui donne une solution à partir d'elle-même.
- Vérifier que cette règle générale rapproche du cas particulier.
Example: a function to compute the sum of the first numbers to n.
Une fonction qui calcule la somme des premiers entiers jusqu'à n :
som(n) = 0 + 1 + 2 + 3 + ... + (n-1) + n
At first we find a number n, with its result
Cherchons un n avec son résultat
som(0) = 0
Then we find a general formula:
Nous trouvons d'abord une formulation récursive de cette suite :
som(n) = 0 + 1 + 2 + 3 + ... + (n-1) + n
som(n-1) = 0 + 1 + 2 + 3 + ... + (n-1)
Therefore
som(n) = som (n-1) + n
The general term is closer to the individual than the previous one
(n-1 is closer to 0 than n, the convergence is proved as n is a natural).
We have now a general case and a singular case, the general case tends forward to the singular one.
Il y a bien un cas particulier et une règle générale. La règle générale rapproche du cas particulier.
int som (int n) {
if ( n < 1 ) {
return 0;
}
else {
return n + som (n-1);
}
}
|
La fonction main serait :
int main () {
printf("La somme des entiers jusqu'au rang %d est %d\n", 5, som(5));
printf("La somme des entiers jusqu'au rang %d est %d\n", 6, som(6));
printf("La somme des entiers jusqu'au rang %d est %d\n", 7, som(7));
}
|
Vous devez écrire :
- Somme des carrés des n premiers entiers
- Somme des cubes des n premiers entiers
- Somme des puissance quatre des n premiers entiers
- Produit des n premiers entiers
- Produit des carrés des n premiers entiers
- Produit des cubes des n premiers entiers
- Produit des puissances quatre des n premiers entiers
- Exponentiation (x puissance n)
- Somme des puissances p des n premiers entiers
sompn(2,4) = 0^4 + 1^4 + 2^4 = 17
- Additions par incrémentations successives
On suppose ne savoir faire des additions que de +1 ou -1.
L'addition de deux valeurs add(a+b) peut être ramenée à l'addition de a+1 et celle de b-1 n'est-ce pas ?
Écrivez la fonction récursive qui fait ainsi l'addition de deux valeurs.
- Soustractions de deux valeurs
Ici encore avec uniquement des +1 et -1.
- Multiplication russe
Il s'agit de faire la multiplication par additions successives.
- Division entière et récursive
- Reste de la Division entière
- Plus grand diviseur commun de deux entiers
- Plus petit multiple commun de deux entiers
- Pour trouver l'entier x supérieur ou égale à la racine
carrée d'un nombre a, il suffit de passer en revue tous les
entiers jusqu'à avoir dépassé la racine.
Faites la fonction C
correspondante.
- Vous venez de trouver un nombre x supérieur ou égal à la
racine carrée d'un autre nombre a. Vous savez donc que x et x-1
encadrent la racine. Faire une fonction qui renvoie celle de ces
deux valeurs qui est la plus proche de la racine.
Of course you'll need also the main function to test all these functions.
Avec, bien sûr, une fonction main qui appelle et affiche les résultats
des précédentes.
Note that you're not allowed to use not already presented functions or tools.
Attention, ce qui n'a pas encore été vu ne doit pas être utilisé.
Tout programme non testé est réputé faux.
If you didn't try it, it didn't work.
Si vous voulez d'autres exercices, il suffit de demander...
You should know about Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21...
A formulation can be given as:
La suite de Fibonacci est connue pour sa forte progression. Les
premières valeurs sont calculées par :
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2)
Just write the program and test it.
Vous pouvez maintenant tester cette suite célèbre.
Il faut la programmer et essayer différentes valeurs. On doit obtenir :
1 1 2 3 5 8 13 21 34 55 89 144
You always must verify the convergence of a recursive formula.
La question de la convergence d'une formule récursive doit toujours
être posée et résolue avant la programmation. Elle repose sur la
méthode vue ci-dessis :
- Find a boundary value.
- In the general term,
- verify that the argument of the call is
closer to the boundary value than the initial term. If it's in
discrete maths, then the convergence is met.
- vérifier l'existence d'une borne, c'est-à-dire d'une situation de fin,
- dans la formule récursive, vérifier que le nouvel appel est plus
près de la fin que la formule précédente
- vérifier que ce rapprochement est discret (si on avance de 1 en 1
vers 0, à partir d'une valeur entière, on va, certainement y
arriver).
Example Fibonacci.
Two boundaries are given, f(0) and f(1).
In the general term, to compute f(n) one needs to compute f(n-1) and
f(n-2). These values are closer to 0 and 1 than n. n, n-1, n-2 are
integers therefore it converges.
Exemple, pour Fibonacci, il y a deux valeurs de fin, f(0) et f(1).
Dans la formule récursive, à partir d'un certain n, (on
cherche à calculer f(n)), on doit calculer f(n-1) et
f(n-2) donc le paramètre est plus près de 0 ou 1 que le
n initial. Comme ces valeurs sont discrètes, on arrive
forcément à l'une des bornes.
A function is tail recursive is the recursive call is the last
thing to be evaluated by the function.
On parle de récursivité terminale lorsque l'appel récursif est la
dernière action de la fonction, c'est-à-dire lorsque le résultat
obtenu par cet appel est le résultat de la fonction appelante.
Exemple :
som (int n) {
if (n == 0) {
return 0;
}
else {
return n + som (n-1);
}
}
|
This function is clearly not tail-recursive as when som(n-1) will be
known, an addition will be computed.
n'est pas récursif terminal : après l'obtention du résultat de
som(n-1) il faut encore faire une addition avec ce résultat.
Par contre,
int somrec (int n) {
return somrec_aux (n,0);
}
int somrec_aux (int n, int s) {
if (n <= 0) {
return s;
}
else {
return somrec_aux (n-1, s+n);
}
}
|
est récursif terminal. Il faut, le plus souvent, transmettre non
seulement le paramètre, mais aussi un accumulateur (ici
s), à chaque appel de fonction.
To obtain a tail-recursive function, one has to add an accumulator
argument which store the computation and tends to the solution.
Voici un exemple de fonction main pour tester somrec :
int main () {
printf("som(%d)==\t%d\n",4,somrec(4));
printf("som(%d)==\t%d\n",5,somrec(5));
printf("som(%d)==\t%d\n",6,somrec(6));
}
|
We'll try now with the multiplcation.
Essayons avec autre chose. Par exemple la multiplication par additions
successives. La formule globale est :
m(a,0) = 0
m(a,b) = b + m(a-1,b)
This expression is an addition so the neutral element is 0. The
accumulator starts then at 0.
L'opération principale est ici une addition. Son élément neutre
est 0. L'accumulateur commencera à 0.
The general term is :
Si on veut faire, au fur et à mesure, ces additions, il
faut, à chaque étape, ajouter b.
M(a,b,som) = M(a-1,b,som+b)
One can see that the third argument starts with 0 than 0+b, then 0+b+b
and so on.
Dans ce cas, petit à petit, on va se diriger vers a valant 0 et
le troisième argument valant b+b+b+...+b (en tout, a(initial) fois).
Comme ce troisième argument reçoit des valeurs en les ajoutant, il
convient de lui donner une valeur initiale nulle.
int mulrecter (int a, int b) {
return mulrecter_aux (a, b, 0);
}
int mulrecter_aux (int a, int b, int som) {
if (a == 0) {
return som;
}
else {
return mulrecter_aux (a-1, b, som + b);
}
}
|
Exercices
You have to write every recursive function done earlier in a tail
recursive form. The Fibonacci sequence has to be done also as tail recursive.
Reprendre les fonctions précédentes (somme, produit, puissance,
Fibonacci...) et les programmer en utilisant la récusivité terminale.
Dernière mise à jour le 7/9/2024 10h00