Remerciez-le!

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

Cours Algorithmique et Programmation en C Université Sultan Moulay Slimane IDRI

Cours Algorithmique et Programmation en C Université Sultan Moulay Slimane IDRISSI NAJLAE Faculté des Sciences et Techniques Filière Ingénieur Béni-Mellal 2009 - 2010 Généralités 1/ • Que désigne le terme « Informatique »? – Science qui étudie les ordinateurs (partie matériel = hardware ) – Traitement automatique de l‟information (partie logicielle = software) • Structure générale d‟un ordinateur 1. Unité centrale (micro-processeur) est composée de : • registres internes destinés à stocker temporairement les informations à l‟intérieur du micro-processeur; • d‟unité arithmétique et logique qui effectue un ensemble d‟opérations; • d‟unité de commande et de contrôle qui permet d‟extraire, d‟interpréter et d‟exécuter les instructions d‟un programme Suite 2/ 2. Mémoire centrale La mémoire centrale « RAM » permet de stocker les informations à traiter. Elle est composée d‟un ensemble de bits (1 bit = 0 ou 1) dit case mémoire. Chaque case est identifiée par un numéro dit « adresse » 3. Unités périphériques 1. d‟entrée & sortie qui permettent à l‟utilisateur de communiquer avec l‟ordinateur (saisie, affichage, …) 2. mémoires auxiliaires qui permettent de stocker les informations en permanence (disque dur, CD, …) N bits case mémoire Données et … … … …programmes 0 . . . 2M - 1 Codage binaire • Les informations traitées par une machine sont traduites en informations binaires (suite de bits de 0 et 1). On parle du „codage binaire‟. • Pour une base de numérotation b, un nombre n peut s‟écrire sous la forme: n = Σaibi / 0≤ai<b  i0,m • Code binaire pur: représente les entiers positifs en base 2. Avec n bits, on peut coder de 0 à 2n -1; – exemple: n = 23, b=2 sur 8 bits n = (00010111)2 23 = 2(10+1)+1 = 2( 2 x ( 2 x 2 + 1) + 1) + 1 = 2( 2 x (22+20) + 20 ) + 20 = 2(23 + 21 + 20) + 20 = 1x24 + 0x23 + 1x 22 + 1x21 + 1x20 = (10111)2 • Code complément à 2: représente les entiers négatifs; dans ce cas, on rajoute la valeur 1 au complément à 1 du nombre à coder; – exemple : n = -15, b=2 sur 8 bits n = (11110001)2 15 = 2x7 + 1= 2 x (22 + 21 + 20) + 20 = 1x23 + 1x22 + 1x21 + 1x20 = (00001111)2 (11110000)2 complément à 1 (00000001)2 on rajoute la valeur 1 (11110001)2 donc (-15) = (11110001)2 Partie I « Algorithmique » Introduction • Que signifie le terme « Algorithme»? – ensemble d‟étapes qui permettent de résoudre un problème donné; – une suite de règles à appliquer dans un ordre déterminé afin d‟arriver au résultat attendu; – un algorithme est indépendant des données, de la machine et du langage de programmation – Exemple: problème posé = calcul de la moyenne de 2 entiers • Analyse: les données fournies = 2 entiers • Résultat désiré = un nombre qui représente la moyenne des données il faut ensuite décrire les étapes qui permettent de passer des données au résultat (algorithme) – Saisir deux entiers – Calculer leur somme – Diviser la somme par 2 Problème analyse I . algorithme traduction II. programmation Résultat Méthodologie générale ◊ Comprendre la nature du problème posé et préciser les données (entrées) ◊ Préciser le(s) résultat(s) désiré(s) (sorties) ◊ Les entrées et les sorties sont des „variables‟ ◊ Déterminer le processus de transformation des données en résultats ◊ Représentation d‟un algorithme 1. Organigramme Représentation graphique de l‟enchaînement de la suite d‟instructions relatives à un algorithme donné 2. Pseudo-code Représentation textuelle de la solution proposée Squelette d‟un algorithme: – Déclaration de variables (entrées) – Début – Bloc d‟instructions – Fin Nom_algorithme Entrées tests résultat1 résultat2 Schéma d‟un organigramme Notion de variables a. Définition = information à stocker et à utiliser au cours d‟un programme désignée par son nom (identificateur attribué par un utilisateur) et une étiquette (référence attribuée par l‟ordinateur) b. Déclaration Attribuer un nom à une variable au sein d‟un programme en précisant son type Syntaxe = Variables nom_var en Type c. Initialisation Affecter une valeur aux variables à l‟aide de l‟opérateur  Syntaxe = nom_var  valeur d. Types de variables • Type numérique (entier, réel, …) • Type alphanumérique (caractères et chaînes de caractères) • Type booléen (vrai ou faux) Familles d‟instructions 1/ -- Ensemble d‟opérations à manipuler sur les différentes variables a. Affectation Attribuer une valeur pour initialisation ou modification par l‟opérateur  b. Lecture & écriture Lire = saisir, introduire des données Syntaxe : Lire nom_var Ecrire = exécuter l‟affichage à l‟écran Syntaxe : Ecrire « texte explicatif », nom_var c. Structure de choix Dans le cas où il existe plusieurs choix correspondants à un certain résultat, on utilise une structure de choix indiquant quel ensemble doit être exécuté i. forme simple: si (condition est vraie) alors (exécuter bloc d’instructions 1) sinon (exécuter bloc d’instructions 2) finsi ii. forme complexe: selon que (condition 1) faire (bloc d’instructions 1) ou que (exécuter bloc d’instructions 2) … ou que (exécuter bloc d’instructions n) autrement (exécuter bloc d’instructions n+1) fselon (fin du selon) Suite 2/ d. Structures de répétition i. Boucle « pour » : utiliser lorsque le nombre d‟opérations ou de répétitions à effectuer est connu d‟avance; Syntaxe : pour nom_var  val_initiale à val_finale faire (bloc instructions) nom_var Suivant Exemple : calculer la moyenne d‟une classe  Données = n nombre d‟étudiants, nt note de chaque étudiant Résultat = moyenne de la classe = somme divisée par n Algo = lire n S  0 Pour i  1 à n Lire nt S  S + nt i Suivant Ecrire « la moyenne des notes est :», S/n ii. Boucle « tantque … »: aucune condition sur le nombre d‟itérations. Le bloc est exécuté tant que la condition est vraie. Sinon on s‟arrête. Syntaxe : tantque (condition) faire (bloc instructions) fintantque iii. Boucle « répéter …jusqu‟à »: ici on répète l‟exécution du bloc jusqu‟à ce que la valeur de la condition soit vraie. On s‟arrête dans ce cas. Syntaxe : répéter (bloc instructions) jusqu’à (condition) iv. Exemple : somme d‟une suite d‟entiers positifs  Algo: variables x, s en Entier Début s  0 x  0 tantque x >= 0 faire s  s + x Lire x Fintantque Ecrire « la somme de la suite est : », s fin Algo: variables x, s en Entier Début s  0 x  0 répéter s  s + x Lire x jusqu’à (x < 0) Ecrire « la somme de la suite est : », s fin Tableau logique and ^ 0 1 0 0 0 1 0 1 or v 0 1 0 0 1 1 1 1 xor 0 1 0 0 1 1 1 0 Donner la table de vérité des expressions suivantes : 1. A = (a ^ ¬b) v c = (a v c) ^ (¬b v c) 2. B = (a ^ b) v (a ^ ¬b) a c avc b ¬b ¬bvc A 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 a b a^b ¬b ¬b^a B 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 Exercices 1/ 1. Donner un algorithme qui calcule la somme de deux entiers 2. Donner un algorithme qui permet d‟échanger les valeurs de 3 variables 3. Donner le type et la valeur des expressions suivantes: – 2 + 3*2 – -0.5 + 3*5 – Vrai et (faux ou vrai) – (2 <3) ^(4>5) 4. Traduire les expressions suivantes en pseudo-code: – X = (2a –bc)/d – Y = (exp(2*a)/2) – Z = log(1/1-x) 5. Écrire un algorithme qui calcule à partir d‟un réel x et une valeur positive a, la puissance xa 6. Écrire un algorithme qui retourne la partie entière inférieure de la racine carrée d‟un entier donné m Suite 2/ 7. Écrire un programme qui demande un nombre à l‟utilisateur, ensuite il lui répond si c‟est un chiffre pair ou impair 8. Écrire un programme qui lit trois chaînes de caractères puis les retourne triées dans l‟ordre alphabétique inverse 9. Écrire un algorithme qui donne le signe (+/-) du produit de 2 nombres sans le calculer 10. Écrire un programme qui décrémente la valeur d‟un produit sachant qu‟il n‟a pas atteint sa valeur minimale 11. Écrire un programme qui n‟affiche que les valeurs paires d‟un dé 12. Écrire un programme qui demande à l‟utilisateur de saisir une chaîne de caractères jusqu‟à la lecture du mot « bye ». Dans ce cas, on s‟arrête 13. Reformuler ce pseudo-code: Variables A, N en Réel Début A  0 N  0 ecrire « entrez votre variable N: » Tantque N >= 0 A  N Lire N si N > A ecrire « le max est : », N sinon ecrire « uploads/S4/ cours-algorithmique-et-programmation-en-c.pdf