[PDF] Informatique (Algorithmique et Langage C) 1. Algorithme et

View - Download Informatique (Algorithmique et Langage C) 1. Algorithme et

Previous PDF

Next PDF

Licence 3 IST

INFORMATIQUE

Informatique (Algorithmique et Langage C)TABLE DES MATI`ERES

1. Algorithme et organigramme 2

1.1. G

´en´eralit´es2

1.2. Principales structures algorithmiques 3

2. Le passage au langage de programmation 6

2.1. Quel langage? 6

2.2. Le Langage C : un peu d"histoire 6

2.3. Mon premier programme C 7

3. Les briques de bases du langage C 7

3.1. g

´en´eralit´es7

3.2. Les variables 8

3.3. Les entr

´ees/sorties 9

3.4. R

´esum´e des principales instructions 10

3.5. Quelques exemples 11

3.6. La biblioth

`eque standard du C 12

3.7. Ce qu"il faut retenir des briques de bases en C 13

4. Principe de base de la compilation 14

4.1. Compiler un programme 14

4.2. debugger un programme 14

5. Op

´erateurs logiques 14

6. Les tableaux15

6.1. D

´efinition et manipulation 15

6.2. Gestion dynamique des tableaux 16

6.3. Exercice17

7. Notion de sous-programme 18

7.1. G

´en´eralit´es 18

7.2. Retour sur les variables 18

7.3. Exemples19

8. Programmation r

´ecursive 20

8.1. Principe20

8.2. En C20

9. Les pointeurs 21

9.1. S

´emantique et manipulation 21

9.2. Occupation m

´emoire 22

9.3. Arithm

´etique des pointeurs 22

10. Les cha

ˆınes de caract`eres 24

10.1. Utilisation 24

10.2. Manipulation 24

11. Les fichiers 25

11.1. Manipulation 25

M. Kowalski

1 INFORMATIQUEALGORITHMIQUE ETLANGAGEC11.2. Lecture/

´ecriture 25

12. Types

´enum´er´es et types structur´es 26

12.1. Besoin de nouveaux types 26

12.2. Type

´enum´er´e 26

12.3. Type Structur

´e 26

13. Quelques types complexes 27

13.1. Les listes cha

ˆın´ees 271. ALGORITHME ET ORGANIGRAMME

1.1.G´en´eralit´es.

Algorithme.

D

´efinition

Un algorithme est un ensemble de r

`egles op´eratoires rigoureuses, ordonnant`a un processeur d"ex´ecuter dans un ordre d

´etermin´e une succession d"op´erations´el´ementaires, pour r´esoudre un probl`eme donn´e.

C"est un outil m

´ethodologique g´en´eral qui ne doit pasˆetre confondu avec le programme proprement dit.

Un algorithme peut

ˆetre :

repr ´esent´e graphiquement par unor ganigramme(ou ordinogramme ), ´ecrit sous forme litt´erale avec un langage algorithmique.

Mon premier algorithme.

la recette du brownie (1) M ´elanger les sucres semoule et vanill´e, les oeufs et la farine tamis´ee (2)

F airefondre le beurre a vecle chocolat

(3) M ´elanger le beurre et le chocolat`a la pˆate (4) M ´elanger les noix de P´ecan et la poudre d"amande`a la pˆate (5)

V ersezla p

ˆate dans un moule`a gˆateau beurr´e

(6)

Mettre

`a cuire 35 minutes dans le four pr´echauff´e`a 170°

Mon deuxi

`eme algorithme.

L"addition en colonnes

(1) Ecrire chaque nombre sur une ligne en alignant les chif fresde m

ˆeme poids

(2)

Se positionner sur la colonne la plus

`a droite (chiffre de plus faible poids) et initialiser la retenue`a 0 (3) Additionner la retenue et tous les chif fresde la colonne courante (4)

Mettre

`a jour la retenue qui devient´egale`a la somme pr´ec´edemment obtenue`a laquelle le chiffre des unit´es a´et´e retir´e.

(5)

Reporter dans la ligne r

´esultat le chiffre des unit´es de la somme, et dans la ligne retenue, la nouvelle retenue (6) Se positionner sur la colonne sui vante(la plus proche `a gauche de la colonne courante) (7)

Recommencer toutes les

´etapes depuis le point 3 si la colonne contient encore au moins un chiffre ou si la retenue est diff´erente de 0

2

INFORMATIQUEALGORITHMIQUE ETLANGAGECG

´en´eralit´es sur les algorithmes.

On peut remarquer que

les algorithmes comportent une ou plusieurs entr

´ees

peuv entren voyerun r

´esultat en sortie

On peut les comparer

`a "fonctions" math´ematiques (on associe une sortie`a des entr´ees)

Les instructionssonts

on ne peut pas faire cuire le brownie avant d"avoir mis la p

ˆate dans le moule.

Organigramme : symboles.Le d

´ebut, la fin ou l"interruption d"un programmeMise `a disposition d"une information`a traiter ou enregistrement d"une information trait

´ee.Les op

´erations ou groupes d"op´erations`a effectuer sur les donn´ees, les

instructions,:::, ou op´eration pour laquelle il n"existe aucun symboleLes tests ou branchements conditionnels

Appel de sous-programmes

1.2.Principales structures algorithmiques.

Structure lin

´eaire ou s´equence.

La structure lin

´eaire se caract´erise par une suite d"actions`a ex´ecuter successivement dans l"ordre de leur

´enonc´e.Structure alternative.

Une structure alternative n"offre que deux issues possible s"excluant mutuellement. Les structures alternatives d ´efinissent unefonction de choixou des´electionentre l"ex´ecution de l"un ou de l"autre des

deux traitements.´Egalement nomm´eesstructures conditionnelles , elles traduisent unsautou une rupture

de s

´equence dans un algorithme.

3

INFORMATIQUEALGORITHMIQUE ETLANGAGECStructures r

´ep´etitives.Dans cette structure, le traitement est effectu

´e une premi`ere

fois, puis sa r ´ep´etition se poursuit jusqu"`a ce que la condition d"arr ˆet soit v´erifi´eeCette structure permet de d"abord tester la condition et ensuite, seulement si elle est vraie, d"effectuer le traitement.Algorithme!organigramme. D

´eterminer si un nombre est pair

Lire un nombre

V

´erifier s"il est divisible par 2

Si oui, af ficher"Le nombre est pair", sinon af ficher"Le nombre est impair"

The friendship algorithm.

4 INFORMATIQUEALGORITHMIQUE ETLANGAGECThe friendship algorithm. 5 INFORMATIQUEALGORITHMIQUE ETLANGAGEC2. LE PASSAGE AU LANGAGE DE PROGRAMMATION

2.1.Quel langage?

L"univers des langages de programmation.

Comment choisir son langage?

Il existe des centaines de langages de programmation...

Pour choisir un lang age,il con vientde d

´efinir certaines propri´et´es du programme qui doitˆetre d

´evelopp´e :

dur

´ee de vie du programme

programme commercial ? programme opensource ? portabilit

´e du programme?

temps de r

´eponse attendu

Il faut

debuggeur, compilateurs efficaces, ...)

Il f aut

´etudier l"existant et essayer de r´eutiliser le plus d"´el´ements d´ej`a conc¸us, d´evelopp´es et test´es

2.2.Le Langage C : un peu d"histoire.

Le langage C.

Les origines

Cr

´e´e en 1972 par B. Kernighan et D. Ritchie en s"inspirant des langages B (1969) et BCPL (1966)

Lang agede bas ni veauconc ¸upour manipuler directement des "mots machine" (bits, octets) A

´et´e massivement utilis´e pour d´evelopper des syst`emes d"exploitation entre 1975 et 1993

F ortementorient

´e programmation syst`eme

Extremement utilis

´e dans la programmation embarqu´ee sur microcontrˆoleurs, les calculs intensifs, les syst `emes d"exploitation et tous les domaines o`u la rapidit´e de traitement est prioritaire

Le langage C.

La popularit

´e C a

´et´e conc¸u pourˆetre tr`es facilement portable : Kernighan et Ritchie estimaient qu"un nouveau

compilateur pour le C pouvait

ˆetre´ecrit en deux mois

Pr ´esent sur de tr`es nombreuses architectures de processeurs

La descendance

De nombreux langages plus r

´ecents sont directement li´es au langage C ou s"en sont fortement inspir´es

1983 : C++

1995 : Ja va,Ja vaScript,PHP

2003 : C#

Un bref historique du langage C.

6 INFORMATIQUEALGORITHMIQUE ETLANGAGEC2.3.Mon premier programme C.

Hello world!

Le code .c1#include2

3intmain () {4printf("Helloworld!\n");

5

6return0;7}Le code .c comment

´e1#include/*Header inclusion*/2

3/*main function: must return an integer*/4intmain () {5printf("Helloworld!\n");/*print on the screen*/6

7return0;/*return value*/8}3. LES BRIQUES DE BASES DU LANGAGEC

3.1.g´en´eralit´es.

Fichiers Headers.

ils sont inclus a vecla commande #include(ex :#include Les fichiers .hinclus au d´ebuts sont lesheaders

Ils permettent d"utiliser des fonctions d

´ej`a programm´ees (ex :printf)

7 INFORMATIQUEALGORITHMIQUE ETLANGAGECLa fonctionmain.

C"est LE point d"entr

´ee de tout programmeC

Quand un fichier est e x

´ecut´e, le point de d´epart est la fonctionmain -`A partir de cette fonction, le programme se d´eroule selon les choix du programmeur

Il peut y a voird"autres fonctions appel

´ee dans lemain

T outprogramme Cdoit avoir une et une seulefonctionmain

Les commentaires.

Les commentaires sont ignor

´es par le compilateur

Les commentaires s"

´ecrivent entre : /* */

/* commentaire */

On peut aussi utiliser les commentaires C++: //

// commentaire d

´efinition de macros : #define.

se d

´eclare juste apr`es lesincude

permet de substituer du code on se limite ici aux macros "simples". par con vention,les macros ont un nom majuscule.

Syntaxe

#define

Exemples

-#define TAILLE 100 -#define PI 3.14

3.2.Les variables.

Variables et leur nom.

Variables

Une variable d

´esigne une information qui peutˆetre modifi´ee au cours du programme. Elle permet : de m ´emoriser une information provenant de l"ext´erieur (fournie par l"utilisateur par exemple) de stock erle r

´esultat d"une op´eration.

ce n"est pas une v ariablemath

´ematique (ou alg´ebrique)!

C"est donc unnomqui permet de rep´erer unemplacement m´emoire.

Nom des variables

Uniquement les 26 caract

`eres de l"alphabet (majuscule et minuscule), les chiffres, et l"underscore

P asde caract

`eres sp´eciaux (accents, &, espaces etc.)

Le premier caract

`ere ne doit pasˆetre un chiffre

Le nom doit f aireau plus 32 caract

`eres

Les majuscules sont distingu

´es des minuscules :aetAsont deux noms diff´erents.

Variables : Types et d

´eclaration.

Types

Les variables sont dites typ

´ees : un entier n"est pas cod´e de la mˆeme mani`ere qu"un r´eel. Il existe plusieurs types de base : -char(caract`eres) Par exemple : "a"..."z", "A"..."Z",... -int(entiers) Par exemple : 129, -45, 0, ... -float(r´eels) Par exemple : 3.14, -0.005, 67.0, ...

V oirla T ableau1 du C dans la poche

8

INFORMATIQUEALGORITHMIQUE ETLANGAGECD

´eclaration

de f ac¸ong

´en´erale :

; ,,; e xemples: int a; float valeur, res; D

´eclarer une variable revient`a lui r´eserver un emplacement m´emoire. On ne connait pas sa valeur

initiale!

Variables : affectation.

But Stock erune information dans un v ariable,pour la r

´eutiliser.

L "op ´erateur d"affectation est le signe=. Ne pas confondre avec le test d"´egalit´e! - = ; Se lit de droite`a gauche, en´evaluanttoutes les expressions`a droite du signe=.

Exemple1intn;2intp;3

4n = 10;5

6p = 2*n-3;Variables : Op

´erations´el´ementaires - 1.

g

´en´eralit´es

T outesles op

´erations´el´ementaires de bases sont permises :+ , - ,*, /

Ces op

´erations d´ependent du type des variables!

cas du typeint la di vision/est la divisioneuclidienne(ou enti`ere). Ex : 11 / 4 = 2 et non pas 2.75!) il e xistel"opquotesdbs_dbs43.pdfusesText_43