[PDF] Algorithmique & programmation en langage C - vol.1 - Archive





Previous PDF Next PDF



Chapitre 2 Exemples dalgorithmes itératifs et récursifs

Algorithme 1: Euclide forme récursive. Entrée: Deux entiers relatifs : a



Algorithmique et programmation avancée

définition par récurrence 3) Récursivité et itération. Tout algorithme récursif peut être ... Choisir entre itératif et récursif. Version récursive.



LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE

Algorithme itératif / récursif L'exécution d'un algorithme ne doit pas impliquer ... comparaison entre le premier élément de la liste (ici 3).



Algorithmique Trier et Trouver

Entrée : un tableau tab de taille taille et un élément e. Algorithme (RechDichoIt recherche dichotomique itérative) ... différence et différence.



Algorithmique Récursivité

On appelle récursive toute fonction ou procédure qui s'appelle elle même. Algorithme Fact. Entrée : un entier positif N. Sortie : factorielle de N si N = 0 



Trois algorithmes de calcul des nombres de Fibonacci

Exercice 1 (Algorithme récursif) Soit l'algorithme suivant : si n = 0 ou n = 1 alors Exercice 2 (Algorithme itératif) Soit l'algorithme suivant :.



livre-algorithmes EXo7.pdf

Arithmétique – Algorithmes récursifs . ci-dessus) avec par définition tan?i = 10?i. ... Écrire une version itérative de l'algorithme d'Euclide.



Algorithmes récursifs: une introduction pragmatique pour un

27 oct. 2019 retourner fact. Algorithme 1 : FactorielleItérative : calcule itérativement la valeur de n!. Essayons-nous à la même démarche avec l'équation (2) ...



Algorithmique & programmation en langage C - vol.1 - Archive

1 févr. 2019 COMPARAISON ITÉRATIF/RÉCURSIF . ... d'ores et déjà d'établir l'indépendance entre un algorithme et sa mise en œuvre c'est à dire.



Première partie : Algorithmique avancée pour les graphes

Algorithme 5 : Parcours en profondeur récursif d'un graphe La différence entre les trois algorithmes réside dans la stratégie utilisée pour décider de ...



[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE

Algorithme itératif / récursif Langage commun entre la machine et nous : comparaison entre le premier élément de la liste (ici 3) et min (ici -2)



[PDF] Spécificités des algorithmes itératifs et récursifs - CNRS

4 oct 2022 · Complexité des algorithmes itératifs : – Utilisation des règles révisées dans les slides 103 et 104 • Complexité des algorithmes récursifs 



[PDF] Chapitre 2 Exemples dalgorithmes itératifs et récursifs

Algorithme 1: Euclide forme récursive Entrée: Deux entiers relatifs : a b; Sortie: Un entier pgcd de a et b; Fonction PGCD(a b);



[PDF] Algorithmique et programmation avancée

Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation La méthode à suivre dépend du type de récursivité 



[PDF] Algorithmique Récursivité

Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact



[PDF] cours 2:Complexité des algorithmes récursifs - Esentn

Algorithmes récursifs Définition La récursivité est le fait pour une méthode de s'appeler elle même On parle alors de méthode récursive



[PDF] Récursivité

3 fév 2020 · Une procédure (ou une fonction) est dite récursive si elle contient au moins un énoncé d'appel direct ou non à elle-même dans son corps



Différence entre récursivité et itération - WayToLearnX

14 juil 2018 · La principale différence entre récursion et itération est que la récursivité est un processus toujours appliqué à une fonction



[PDF] ALGORITHMIQUE II

Un algorithme (ou fonction) est dit récursif s'il est défini en fonction de lui-même ? Exemples ? Fonction puissance(x : réel n : entier) : réel



[PDF] Récursivité - LACL

- ´Ecrire deux fonctions C l'une utilisant un algorithme itératif l'autre un algorithme récursif permettant de calculer l'entier naturel n étant donné en 

Algorithme itératif / récursif Langage commun entre la machine et nous : comparaison entre le premier élément de la liste (ici 3) et min (ici -2).

  • Quelle est la différence entre un programme itératif et un programme récursif ?

    Un programme est dit récursif lorsqu'une entité s'appelle elle-même. Un programme est appelé itératif lorsqu'il y a une boucle (ou répétition).

  • Comment transformer un algorithme récursif en itératif ?

    Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation. La méthode à suivre dépend du type de récursivité de l'algorithme. Un algorithme est dit récursif terminal s'il ne contient aucun traitement après un appel récursif.

  • Quand Dit-on qu'un algorithme est récursif ?

    L'algorithme est récursif parce qu'il s'invoque lui-même. En effet, pour construire toutes les permutations de belle Marquise -- vos beaux yeux -- me font mourir -- d'amour, il faut construire toutes les permutations de vos beaux yeux -- me font mourir -- d'amour.
  • En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
>G A/, +2H@yRRdeRRN ?iiTb,ff?HXb+B2M+2f+2H@yRRdeRRNpk am#KBii2/ QM R 62# kyRN

Bb KmHiB@/Bb+BTHBM`v QT2M ++2bb

`+?Bp2 7Q` i?2 /2TQbBi M/ /Bbb2KBMiBQM Q7 b+B@

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

i2+?BM; M/ `2b2`+? BMbiBimiBQMb BM 6`M+2 Q` #`Q/- Q` 7`QK Tm#HB+ Q` T`Bpi2 `2b2`+? +2Mi2`bX /2biBMû2 m /ûT¬i 2i ¨ H /BzmbBQM /2 /Q+mK2Mib b+B2MiB}[m2b /2 MBp2m `2+?2`+?2- Tm#HBûb Qm MQM-

Tm#HB+b Qm T`BpûbX

.Bbi`B#mi2/ mM/2` *`2iBp2 *QKKQMbii`B#miBQM @ LQM*QKK2`+BH @ a?`2HBF2% 9Xy

AMi2`MiBQMH GB+2Mb2

H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR

hQ +Bi2 i?Bb p2`bBQM, .KB2M "2`i?2i- oBM+2Mi G#imiX H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR, amTTQ`ib /2 +Qm`b oQHmK2 R Sû`BQ/2 kyy8@kyR9X GB+2M+2X H;Q`Bi?KB[m2 2i S`Q;`KKiBQM- AbiM#mH- hm`[mB2X kyR9- TTXkjkX +2H@yRRdeRRNpk

Université Galatasaray

Algorithmique &

programmation en langage C

Damien Berthet & Vincent Labatut

Notes de cours

Supports de cours Volume 1

Période 2005-2014

Damien Berthet & Vincent Labatut 2005-2014

Ce document est sous licence Creative Commons Attribution - - Partage

dans les Mêmes Conditions 4.0 International. Pour accéder à une copie de cette licence, merci de vous

rendre à l'adresse suivante : http://creativecommons.org/licenses/by-nc-sa/4.0/Galatasaray Üniversitesi

Mühendislik ve Teknoloji Fakültesi

version 0.9Turquie 1/0/201 Supports de cours vol.1 Période 2005-2014 3/232

SOMMAIRE ................................................................................................................................................ 3

CONVENTIONS ........................................................................................................................................... 8

1 INTRODUCTION .................................................................................................................................. 9

1.1 DÉFINITIONS ........................................................................................................................................ 9

1.2 PRÉSENTATION DU LANGAGE C ............................................................................................................. 14

2 TYPES DE DONNÉES .......................................................................................................................... 23

2.1 REPRÉSENTATION DE L'INFORMATION ..................................................................................................... 23

2.2 NOMBRES ENTIERS ............................................................................................................................. 25

2.3 NOMBRES RÉELS ................................................................................................................................ 31

2.4 CARACTÈRES ...................................................................................................................................... 37

2.5 IMAGES ............................................................................................................................................ 39

3 VARIABLES ET CONSTANTES LITTÉRALES........................................................................................... 44

3.1 CONSTANTES LITTÉRALES...................................................................................................................... 44

3.2 VARIABLES ........................................................................................................................................ 46

4 EXPRESSIONS ET OPÉRATEURS ......................................................................................................... 51

4.1 EXPRESSIONS ..................................................................................................................................... 51

4.2 OPÉRATEURS ..................................................................................................................................... 52

4.3 CONVERSIONS ................................................................................................................................... 56

5 CONDITIONS ET BOUCLES ................................................................................................................. 59

5.1 INSTRUCTIONS DE TEST ........................................................................................................................ 59

5.2 INSTRUCTIONS DE RÉPÉTITION ............................................................................................................... 64

5.3 ANALYSE D'UN PROGRAMME ................................................................................................................ 68

6 TABLEAUX ........................................................................................................................................ 74

6.1 DÉFINITION ....................................................................................................................................... 74

6.2 MÉMOIRE ......................................................................................................................................... 75

6.3 MANIPULATION ................................................................................................................................. 76

6.4 CHAÎNES DE CARACTÈRES ..................................................................................................................... 77

6.5 TABLEAUX MULTIDIMENSIONNELS .......................................................................................................... 79

6.6 EXERCICES ......................................................................................................................................... 80

7 FONCTIONS....................................................................................................................................... 82

7.1 PRÉSENTATION .................................................................................................................................. 82

7.2 PASSAGE DES PARAMÈTRES .................................................................................................................. 87

7.3 TABLEAUX ......................................................................................................................................... 91

7.4 EXERCICES ......................................................................................................................................... 93

8 TYPES PERSONNALISÉS ..................................................................................................................... 95

8.1 GÉNÉRALITÉS ..................................................................................................................................... 95

8.2 STRUCTURES ..................................................................................................................................... 96

8.3 UNIONS .......................................................................................................................................... 101

8.4 ÉNUMÉRATIONS ............................................................................................................................... 102

8.5 NOMMAGE DE TYPES ........................................................................................................................ 104

9 CLASSES DE MÉMORISATION .......................................................................................................... 106

9.1 PERSISTANCE D'UNE VARIABLE ............................................................................................................ 106

9.2 DÉCLARATIONS LOCALES .................................................................................................................... 106

9.3 DÉCLARATIONS GLOBALES .................................................................................................................. 109

9.4 FONCTIONS ..................................................................................................................................... 109

10 POINTEURS

10.1 PRÉSENTATION

10.2 ARITH

10.3 POINTEURS ET TABLEAUX

11 ALLOCATION DYNAMIQUE

11.1 PRÉSENTATION

11.2 ALLOCATION SIMPLE

11.3 AUTRES FONCTIONS

11.4 EXERCICES

12 FICHIERS

12.1 STRUCTURE FILE

12.2 OUV/FERMETURE

12.3 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CA

12.4 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CH

12.5 LECTURE/ÉCRITURE FORMATÉES

12.6 LECTURE/ÉCRITURE PAR BLOC

12.7 EXERCICES

13 FONCTIO

13.1 PRÉSENTATION

13.2 TYPES DE RÉCURSIVITÉ

13.3 ARBRE DES APPELS

13.4 STRUCTURE D'UNE FONCTION RÉCURSI

13.5 COMPARAISON ITÉRATIF/RÉCURSIF

13.6 EXERCICES

14 LISTES CHAÎNÉES

14.1 PRÉ

14.2 LISTES SIMPLEMENT CHA

14.3 LISTES DOUBLEMENT CHA

15 PILES DE DONNÉES

15.1 PRÉ

15.2 TYPE ABSTRAIT

15.3 IMPLÉMENTATION PAR TA

15.4 IMPLÉMENTATION PAR LI

16 FILES DE DONNÉES

16.1 PRÉSENTATION

16.2 TYPE ABSTRAIT

16.3 IMPLÉMENTATION SIMPLE

16.4 IMPLÉMENTATION CIRCUL

16.5 IMPLÉMENTATION PAR LI

17 COMPLEXITÉ ALGORITHM

17.1 INTRODUCTION À LA COM

17.2 CALCUL DE COMPLEXITÉ

17.3 ALGORITHMES RÉCURSIFS

18 ALGORITHMES DE TRI

18.1 PRÉSENTATION

18.2 TRI À BULLES

18.3 TRI PAR SÉLECTION

18.4 TRI PAR INSERTION

Supports de cours vol.1 Période 2005-2014 5/232 18.5 TRI FUSION...................................................................................................................................... 208

18.4 TRI RAPIDE ...................................................................................................................................... 212

19

ARBRES ........................................................................................................................................... 215

19.1 DÉFINITIONS .................................................................................................................................... 215

19.2 ARBRES BINAIRES ............................................................................................................................. 218

19.3 ARBRES BINAIRES DE RECHERCHE ......................................................................................................... 223

Supports de cours vol.1 Période 2005-2014 6/232 Ce document constitue le support de cours écrit pour différents enseignements

2) et de leurs corrigés (volume 3).

1 (Simple DirectMedia Layer

ue. Les outils utilisés en TP (GCC23

notions abordées le sont parfois de façon simplifiée et/ou incomplète. s de 2 heures réparties

de la façon suivante : Séance Sujet abordé Sections traitées

01 Introduction 1

02 Types simples 2

03 Variables, expressions et opérateurs 3-4

04 Structures de contrôle 5

05 Tableaux 6

06 Définition de fonctions 7-7.2.1

07 Passage de paramètres 7.2.2-7.4

08 Structures et unions 8-8.3

09 Types personnalisés & classes de mémorisation 8.4-9

10 Pointeurs 10

11 Allocation dynamique de mémoire 11

12 Fichiers 12

13 Fonctions récursives 13

14 Listes simplement chaînées 14-14.2

15 Listes doublement chaînées 14.3-14.3.5

16 Piles de données 15

17 Files de données 16

18 Introduction à la complexité 17-17.1

19 Complexité d'algorithmes itératifs 17.2

20 Complexité d'algorithmes récursifs 17.3

21 Tris quadratiques 18-18.4

22 Tris log-linéaires 18.5-18.4

23 Arbres binaires 19-19.2

24 Arbres binaires de recherche 19.3

sabsent du cours magistral, et était plutôt traité lors du tout premier TP. 1https://www.libsdl.org/ 2 3

Les principales références bibliographiques utilisées pour préparer ce cours sont les

, Thomas Cormen, Charles Leiserson & Ronald Méthodologie de la programmation en C, Achille Braquelaire, Dunod, 4ème

Langage, Gerhard Willms, MicroApplication, 1996.

Ce document utilise différentes conventions, dont certaines sont aussi appliquées dans les fonctions, variables, constantes, etc.) sont indiqués en utilisant la polCourier.

Courier

Entrez une valeur

Lorsque du code source est cit

int ma_function(int x)

Concept

1 1.1 1.1.1

Le mot algorithme ème

Al Khuwarizm4rythme, ce qui explique

y

Algorithme

ithme Algorithmiqueensemble des méthodes permettant de définir des (dans le cadre informatique) son implém 1.1.2

Un informel, ou incomplètement

informatique) ou autres. Par opposition, une démonstration mathématique ou un formels5 comp 6 Les étapes sont représentées par des liens

Les étapes de test

Les étapes de début fin

Les étapes de traitement

Les appels à des fonctions sous) sont

4 algèbre.

5 6 entrée/sortie complexes tout en gardant un diagramme lisible. pa exemple -

Version organi

Version pseudo

debut tant fin 1.1.3 Dans notre cas, le problème à résoudre est souvent compliqué d. Cette méthode récursivement

élémentaires,

Début

Fin

Afficher "début du traitement"

Afficher "fin du traitement"

compteur <= 0

Si compteur<4

Traitement X

Incrémenter compteur

faux vrai e

Énoncé du p

o o La table traçante possède un compteur. o Elle est capabl

ƒ lever/baisser

avec la feuille de papier posée sur la table de dessin, ou au contraire

ƒ centrer

ƒ haut/bas/gauche/droite ͳ

ƒ initialiser/incrementer

o Le problème est de dessiner une croix centrée sur la feuille, et dont chaque R début 10 fin o Algorithme de niveau ૛ debut fin o Algorithme de nivea૜

ƒ On décompose aller au centre sans tracer

debut fin ƒ On décompose tracer la branche du haut debut tant que ƒ On recommence avec les autres actions du niveau -, et en remplaçant 1.1.4

On peut considérer un programme comme la

de programmation, i.e. un langage formel compréhensible par un ordinateur. On dit alors que implémentation

Programme : n ordinateur.

Instruction

s programmesource exécutable. Le premier cont code sourcebinaire, aussi appelé machine objet.

Code source :

Code binaire

Remarque programme

compilation. Ce traitement est réalisé par un programme spécial appelé le compilateur.

Compilationaction d

utiliser pour exécuter le programme. implémente sont deux choses bien

La personne qui écrit le programme

Le langage de programmation employé

utilisés etc. ici au cas du langage C, décrit dans la figure ci programme en plusieurs fichiers séparés

La première précompiler

#. Ces version complétée deuxième compilation . assembleur. Ce langage est qualifié de bas troisième assemblage, et consiste à transformer chaque .o. quatrième édition des liens. Elle consiste à rassembler

Remarque abus de langage, on appelle compilation

étape).

1.1.5 en fonction du moment où elles sont détectées

Erreur de compilation

ut autre étape du processus. avertissement main() fonct1() fichiers source précompilation fonct2() fonct3() fonct4() fichiers complétés main() fonct1() fonct2() fonct3() fonct4() ADD

JUMP X

ADD X,Y

ADD Y,Z

LABEL UN

JUMP DE

compilation fichiers assembleur

01101010

01010100

01010101

01110111

01111011

01111011

11010100

11001100

10101001

assemblage fichiers objet

10010101

00010101

00010101

00101010

10010101

01010101

01000111

édition des liens

fichier exécutable 7 votre programme.

échoué. Ces erreurs

compilateur compilateur utilisé pour être capable de les int corriger la toute première causer les erreurs ultér attendu lors de son exécution. fatales non. programme se termine intempestivement. Par contre, localiser la partie du code source non

Remarque entifier les

1.2 superficielle, afin de pouvoir progresser dans le cours. La plupart de ces notions seront ensuite 1.2.1

Le langage C est

Unix8

7 Integra

pour écrire le code source. Pour nos TP, nous utiliserons 8 Portabilitéun langage de programmation est dit portable machines et de systèmes différents, sans avoir besoin d. stabilisée en 1978 et est appelée Kernighan & Ritchie

C K&R;

ANSI9C89

C ANSI

ISO10 répandue. Nous indiq bas niveau 11 que C++, Java, C#, JavaScript ou PHP. Un gra

Remarque

informatique 1.2.2 chaque instruction se termine par un point;). Pour améliorer la lisibilité du code bloc. exemple instruction 1;

Il est aussi possible de définir un bloc

récursivement. On peut alors parler de sous. exemple 9 10 11 instruction 1; de le désigner fonction. Outre son nom, une

Fonction

identificateur. À noter que cette notionquotesdbs_dbs44.pdfusesText_44
[PDF] expression de couturiere

[PDF] fonction récursive

[PDF] automobile in corsa

[PDF] pélican volant de marey (1882)

[PDF] dynamisme d'un cycliste

[PDF] le futurisme mouvement artistique

[PDF] futurisme caractéristiques

[PDF] futurisme définition

[PDF] l5a les clans majeurs pdf

[PDF] l5a pdf

[PDF] l5a 4eme edition pdf

[PDF] pendule élastique vertical

[PDF] l5a 4eme edition pdf download

[PDF] pendule elastique definition

[PDF] l5a 4 edition pdf