Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ALGORITHMIQUE ET PROGRAMMATION EN C Adamou MFOPOU, Université de Douala 17/05/2

ALGORITHMIQUE ET PROGRAMMATION EN C Adamou MFOPOU, Université de Douala 17/05/2016 Table des matières Table des matières ............................................................................................................................................ 2 Premiers programmes ....................................................................................................................................... 4 Objets : types, constantes, variables ............................................................................................................ 4 Objets élémentaires.................................................................................................................................. 4 Objets élémentaires en C ......................................................................................................................... 4 Expressions............................................................................................................................................... 4 Identificateurs............................................................................................................................................ 6 Constantes................................................................................................................................................ 6 Variables ................................................................................................................................................... 7 Expressions avec des variables et des constantes .................................................................................. 7 Exécution : la séquentialité............................................................................................................................ 7 Séquentialité ............................................................................................................................................. 7 Affectation ................................................................................................................................................. 8 Entrées/sorties : écriture et lecture ........................................................................................................... 9 Premiers programmes ............................................................................................................................ 10 Remarques.............................................................................................................................................. 13 Analyse descendante.................................................................................................................................. 13 Fonctions ......................................................................................................................................................... 15 Fonctions avec paramètres et résultat........................................................................................................ 15 Fonctions sans résultat : procédures .......................................................................................................... 16 Fonctions et procédures sans paramètres.................................................................................................. 17 Fonctions avec plusieurs résultats.............................................................................................................. 18 Résultat n-uplet....................................................................................................................................... 18 Les structures en C................................................................................................................................. 18 Paramètres modifiables (passage par adresse) en C ............................................................................ 19 Variables et portée des variables................................................................................................................ 19 Variables locales, variables globales...................................................................................................... 19 Variables statiques et automatiques en C .............................................................................................. 20 Fonctions en paramètre de fonctions.......................................................................................................... 21 Exemples de programmes avec des fonctions ........................................................................................... 22 Volume de l'écrou ................................................................................................................................... 22 Calcul de la durée................................................................................................................................... 23 Langage C : arguments de main................................................................................................................. 25 Langage C : nombre quelconque de paramètres ....................................................................................... 25 Conditionnelle.................................................................................................................................................. 26 Quelques exemples..................................................................................................................................... 26 La deuxième pizza à moitié prix.............................................................................................................. 26 Équation du second degré...................................................................................................................... 27 Autres exemples simples ............................................................................................................................ 28 Macros en C ................................................................................................................................................ 29 Condition et opérations Booléennes ........................................................................................................... 30 Quelques exemples portant sur la conditionnelle ....................................................................................... 32 Calcul du temps de parcours .................................................................................................................. 32 Calcul simplifié de l'impôt sur le revenu.................................................................................................. 33 Énumération des cas................................................................................................................................... 35 Syntaxe ................................................................................................................................................... 35 Calcul de la position d'un jour dans l'année : quantième........................................................................ 37 Itération et récursivité ...................................................................................................................................... 40 Itérations et conditions d'arrêt ..................................................................................................................... 40 faire N fois............................................................................................................................................... 41 Répétition d'un calcul.............................................................................................................................. 44 Itérations et conditions d'arrêt................................................................................................................. 46 Itérations et compteurs ........................................................................................................................... 48 Récursivité................................................................................................................................................... 50 Cas naturels............................................................................................................................................ 51 Compteurs............................................................................................................................................... 51 Moyenne d'une série de nombres........................................................................................................... 52 Répétition d'un calcul.............................................................................................................................. 53 Algorithmique et programmation en C Page 2 Exemples simples ................................................................................................................................... 54 Calcul de l'intégrale par la somme de Riemann ..................................................................................... 58 Tableau d'amortissement du remboursement d'un emprunt .................................................................. 60 Calcul du jour dans l'année : quantième................................................................................................. 62 Récursivité croisée...................................................................................................................................... 62 Tableaux statiques 1D..................................................................................................................................... 63 Opérations élémentaires sur les tableaux .............................................................................................. 64 Application : les ensembles .................................................................................................................... 70 Tri de tableaux ........................................................................................................................................ 72 Tableaux à trous ..................................................................................................................................... 74 Algorithmique et programmation en C Page 3 Itération et récursivité.................................................................................................................................. 54 Premiers programmes Objets : types, constantes, variables Objets élémentaires • Nombres entiers (relatifs) : on les note sous la forme habituelle, soit une suite de chiffres : 26, -172. • Nombres réels : Leur notation est elle aussi classique, identique à celle qu'on utilise pour les machines à calculer. Le séparateur décimal est le point. On peut également écrire les réels en notation scientifique : 2.7, 3.14, 2.0, -3.4 10-3. • Caractères : On les note entre apostrophes comme par exemple 'A' (caractère A), 'a' (caractère a), '0' (caractère 0), ',' (caractère virgule) etc. Les caractères spéciaux peuvent être désignés directement par leur symbole : ENTER (retour chariot), TAB (tabulation), BEEP (son) etc. • Chaînes de caractères : Ce sont des suites de caractères délimitées par des guillemets. On procède comme cela dans la plupart des langages. Exemples : "oui", "bonjour", "ceci", "ceci est une chaîne". • Booléens : Ce sont des objets particuliers qui peuvent prendre uniquement 2 valeurs : VRAI ou FAUX. Objets élémentaires en C • Nombres entiers (relatifs) : En langage C, on a en plus la possibilité de noter les entiers sous forme hexadécimale (base 16) : 0x12 vaut 18 (1*16+2), 0x2A vaut 42 (2*16+10), ou octale (base 8) : 012 vaut 10 (1*8+2). • Nombres réels : En langage C on utilise aussi la notation classique. Exemples : 12.38, 0.15, .15, 2.0, 2., -3.17, 1.e3, 0.1e-2, 123.14E19. • Caractères : En C les caractères sont aussi notés entre apostrophes : 'a', 'Z', '?' etc. Les caractères spéciaux peuvent être désignés directement par leur symbole : ('\n' (retour chariot), '\t' (tabulation) etc.), ou par leur code ASCII, '\007' en octal ou '\x07' en hexadécimal (caractère de code ASCII 7 = bip), '7' (caractère 7). En fait, au niveau de la machine (et du langage C), chaque caractère correspond à un code (ASCII), ainsi 'A' correspond au code ASCII 65, 'a' au code ASCII 97, '0' au code ASCII 48, ',' au code ASCII 44, '\n' au code ASCII 10 etc. • Chaînes de caractères : Exemples : "oui", "bonjour", "ceci", "ceci est une chaîne". • Booléens : Attention, de tels objets n'existent pas explicitement en C, mais existent dans de nombreux autres langages de programmation. En principe, on attribue la valeur entière 0 pour FAUX et 1 pour VRAI. Expressions Le but étant de réaliser des calculs qui font intervenir les objets décrits précédemment, nous allons les combiner pour créer des expressions à l'aide d'opérateurs. Là encore, la notation est proche de la notation usuelle des mathématiques ou des calculettes. Opérateurs • arithmétiques addition +, soustraction -, moins (unaire) -, multiplication *, division /, division entière div, modulo (reste de la division entière) mod. • Booléens ET, OU, NON. • de comparaison = (égal), <> (différent), <, >, <=, >=. Opérateurs en langage C • arithmétiques +, - (unaire et binaire), *, / (entière, réelle), % (modulo), incrémentation ++ (augmente la valeur de 1), décrémentation -- (diminue la valeur de 1), accumulations : -=, +=, /=, *= (des explications sur ces notations seront fournies plus loin). • Booléens && (ET), || (OU), ! (NON) Algorithmique et programmation en C Page 4 • de comparaison == (égal), != (différent) , <, >, <=, >=. Ces opérateurs ne s'appliquent pas aux chaînes de caractères en C. • sur les bits | (OU bit à bit), & (ET bit à bit), << (décalage à gauche), >> (à droite), ^ (ou exclusif bit à bit), ~ (inversion = NON bit à bit). Expressions arithmétiques La formulation des expressions arithmétiques est elle aussi similaire à la notation mathématique : • 2 + 3 • 17 * 73 + 2 • 7 mod 2 • 7 div 2 (vaut 3 : division entière) • 7 / 2 (vaut 3.5 : division réelle) • 0.3 * 168.2 + (4. + 0.11)/5. Expressions arithmétiques en langage C • 2 + 3 • 17 * 73 + 2 • 7 % 2 • 7 / 2 (vaut 3 : division entière) • 7. / 2. (vaut 3.5 : division réelle) • (0.3 * 168.2)+((4. + 0.11)/5.) • 31 >> 4 (vaut 1 : on supprime les 4 derniers bits) Attention aux mélanges de types dans les expressions (certains langages comme le Caml les ont tout simplement interdits), et aux parenthèses. On peut mélanger les types, il existe des règles de conversion par défaut. On peut aussi ne pas mettre de parenthèses et dans ce cas des règles de priorité sont appliquées. Dans le doute, il vaut mieux mettre toutes les parenthèses nécessaires et convertir toutes les valeurs dans le même type. Expressions Booléennes • 3<2 vaut FAUX. • (3<2) ET (6=5). Comme (3<2) vaut FAUX, l'expression (FAUX ET quelque chose) donnera forcément FAUX. • (3>2) OU (6=5). Comme (3>2) vaut VRAI, l'expression (VRAI OU quelque chose) donnera forcément VRAI. Expressions Booléennes en C : ordre d'évaluation En C, l'évaluation d'une expression n'est effectuée que si elle est nécessaire à l'obtention du résultat. • 3<2. L'expression est fausse et vaut 0. • (3<2)&&(6==5). Comme (3<2) est FAUX, l'expression (FAUX ET quelque chose) donnera forcément FAUX. L'expression (6==5) n'est pas évaluée. • (3>2)||(6==5). Comme (3>2) est VRAI, l'expression (VRAI OU quelque chose) donnera forcément VRAI. L'expression (6==5) n'est pas évaluée. Expressions arithmético-Booléennes en langage C Ceci est propre au langage C, qui ne possède pas de véritable type Booléen. Une expression Booléenne valant VRAI prend la valeur 1 dans une expression arithmétique, et 0 si elle vaut FAUX. Une expression arithmétique qui vaut 0 est considérée comme valant FAUX dans une expression Booléenne, alors qu'elle est considérée à VRAI pour toute autre valeur. • (3<4)*(1+((2+3)==5)) vaut (1)*(1+(1)) soit 2. • (3||(4<3)4)) vaut 3||0 donc VRAI OU FAUX , donc VRAI soit 1. Algorithmique et programmation en C Page 5 • Entiers On peut décrire les types entiers du langage C à l'aide de la règle suivante : ¾ [signed | unsigned] [short | long] [int] En pratique, les types entiers couramment utilisés sont : ¾ int : entiers signés sur 4 octets (de -231 à 231-1). ¾ unsigned int : entiers positifs sur 4 octets (de 0 à 232-1). ¾ short : entiers signés sur 2 octets (de -215 à 215-1). ¾ unsigned short : entiers positifs sur 2 octets (de 0 à 216-1). On utilise aussi parfois le type char pour coder les petits entiers : ¾ char : entiers signés sur 1 octet (de -27 à 27-1). ¾ unsigned char : entiers positifs sur 1 octet (de 0 à 28-1). • Booléen Le type Booléen n'existe pas en C, en tout cas pas explicitement, mais peut être obtenu à l'aide des entiers : en effet, une expression Booléenne vaut uploads/s3/ in670-algo.pdf