La récursivité. Cours d'Algorithmique - Christophe Darmangeat. Introduction à l'Algorithmique. I - Les variables. Partie 1 Les Variables « N’attribuez jamais à la malveillance ce qui s’explique très bien par l’incompétence. » - Napoléon Bonaparte « A l’origine de toute erreur attribuée à l’ordinateur, vous trouverez au moins deux erreurs humaines.
II - Lecture et écriture. Partie 2 Lecture et Ecriture « Un programme est un sort jeté sur un ordinateur, qui transforme tout texte saisi au clavier en message d’erreur. » - Anonyme « Un clavier Azerty en vaut deux » - Anonyme Trifouiller des variables en mémoire vive par un chouette programme, c’est vrai que c’est très marrant, et d’ailleurs on a tous bien rigolé au chapitre précédent.
Cela dit, à la fin de la foire, on peut tout de même se demander à quoi ça sert. En effet. Variable A en Numérique Début A ← 12^2 Fin D’une part, ce programme nous donne le carré de 12. D’autre part, le résultat est indubitablement calculé par la machine. C’est pourquoi, heureusement, il existe des d’instructions pour permettre à la machine de dialoguer avec l’utilisateur (et Lycée de Versailles, eût ajouté l’estimé Pierre Dac, qui en précurseur méconnu de l’algorithmique, affirmait tout aussi profondément que « rien ne sert de penser, il faut réfléchir avant »). 2.
Lire Titi Ecrire Toto Ecrire "Entrez votre nom : " Lire NomFamille. III - Les Tests. Partie 3Les Tests « Il est assez difficile de trouver une erreur dans son code quand on la cherche.
C’est encore bien plus dur quand on est convaincu que le code est juste. » - Steve McConnell « Il n’existe pas, et il n’existera jamais, de langage dans lequel il soit un tant soit peu difficile d’écrire de mauvais programmes ». - Anonyme « Si le déboguage est l’art d’enlever les bogues, alors la programmation doit être l’art de les créer. » - Anonyme Je vous avais dit que l’algorithmique, c’est la combinaison de quatre structures élémentaires. IV - Encore de la logique. Partie 4 Encore de la Logique « La programmation peut être un plaisir ; de même que la cryptographie.
Toutefois, il faut éviter de combiner les deux. » - Kreitzberg et Sneidermann 1. Faut-il mettre un ET ? Faut-il mettre un OU ? Une remarque pour commencer : dans le cas de conditions composées, les parenthèses jouent un rôle fondamental. Variables A, B, C, D, E en Booléen Variable X en Entier Début Lire X A ← X > 12 B ← X > 2 C ← X < 6 D ← (A ET B) OU C E ← A ET (B OU C) Ecrire D, E Fin Si X = 3, alors on remarque que D sera VRAI alors que E sera FAUX. S’il n’y a dans une condition que des ET, ou que des OU, en revanche, les parenthèses ne changent strictement rien.
Dans une condition composée employant à la fois des opérateurs ET et des opérateurs OU, la présence de parenthèses possède une influence sur le résultat, tout comme dans le cas d’une expression numérique comportant des multiplications et des additions. On en arrive à une autre propriété des ET et des OU, bien plus intéressante. V - Les boucles. Partie 5 Les Boucles « Les premiers 90% du code prennent les premiers 90% du temps de développement.
Les 10% restants prennent les autres 90% du temps de développement » - Tom Cargill Et ça y est, on y est, on est arrivés, la voilà, c’est Broadway, la quatrième et dernière structure : ça est les boucles. VI - Les tableaux. Partie 6 Les Tableaux « Si on ment à un compilateur, il prendra sa revanche. » - Henry Spencer.
Bonne nouvelle ! Je vous avais annoncé qu’il y a avait en tout et pour tout quatre structures logiques dans la programmation. Eh bien, ça y est, on les a toutes passées en revue. Mauvaise nouvelle, il vous reste tout de même quelques petites choses à apprendre… Imaginons que dans un programme, nous ayons besoin simultanément de 12 valeurs (par exemple, des notes pour calculer une moyenne).
Moy ← (N1+N2+N3+N4+N5+N6+N7+N8+N9+N10+N11+N12)/12 Ouf ! Cerise sur le gâteau, si en plus on est dans une situation on l’on ne peut pas savoir d’avance combien il y aura de valeurs à traiter, là on est carrément cuits. C’est pourquoi la programmation nous permet de rassembler toutes ces variables en une seule, au sein de laquelle chaque valeur sera désignée par un numéro.
Un ensemble de valeurs portant le même nom de variable et repérées par un nombre, s’appelle un tableau, ou encore une variable indicée. VII - Techniques rusées. « Informatique : alliance d'une science inexacte et d'une activité humaine faillible » - Luc Fayard Une fois n’est pas coutume, ce chapitre n’a pas pour but de présenter un nouveau type de données, un nouveau jeu d’instructions, ou que sais-je encore.
Son propos est de détailler quelques techniques de programmation qui possèdent deux grands points communs : Et que valent quelques kilos d’aspirine, comparés à l’ineffable bonheur procuré par la compréhension suprême des arcanes de l’algorithmique ? Hein ? Première de ces ruses de sioux, et par ailleurs tarte à la crème absolue du programmeur, donc : le tri de tableau. Combien de fois au cours d’une carrière (brillante) de développeur a-t-on besoin de ranger des valeurs dans un ordre donné ? Il existe plusieurs stratégies possibles pour trier les éléments d’un tableau ; nous en verrons deux : le tri par sélection, et le tri à bulles.
Commençons par le tri par sélection. Et cetera, et cetera, jusqu’à l’avant dernier. VIII - Tableaux Multidimensionnels. Partie 8 Tableaux Multidimensionnels « Le vrai problème n’est pas de savoir si les machines pensent, mais de savoir si les hommes pensent » - B.F.
Skinner « La question de savoir si un ordinateur peut penser n'est pas plus intéressante que celle de savoir si un sous-marin peut nager » - Edgar W. Dijkstra Ceci n’est pas un dérèglement de votre téléviseur. Oui, enfin bon, avant d’attaquer la quatrième, on va déjà se coltiner la deuxième. IX - Les fonctions prédéfinies. Partie 9 Les Fonctions Prédéfinies « Il y a deux méthodes pour écrire des programmes sans erreurs.
X - Les fichiers. Partie 10 Les Fichiers « On ne peut pas davantage créer des fichiers numériques non copiables que créer de l’eau non humide » - Bruce Schneier Jusqu’à présent, les informations utilisées dans nos programmes ne pouvaient provenir que de deux sources : soit elles étaient inclues dans l’algorithme lui-même, par le programmeur, soit elles étaient entrées en cours de route par l’utilisateur.
Mais évidemment, cela ne suffit pas à combler les besoins réels des informaticiens. XI - Procédures et fonctions. Partie 11 Procédures et Fonctions « L’informatique semble encore chercher la recette miracle qui permettra aux gens d’écrire des programmes corrects sans avoir à réfléchir. Au lieu de cela, nous devons apprendre aux gens comment réfléchir » - Anonyme 1. Fonctions personnalisées 1.1 De quoi s'agit-il ? XII - Notions complémentaires. Partie 12 Notions Complémentaires « Le danger, avec les ordinateurs, ce n’est pas tellement qu’ils deviennent aussi intelligents que les hommes, mais c’est que nous tombions d’accord avec eux pour les rencontrer à mi-chemin » - Bernard Avishai Une fois n’est pas coutume, ce chapitre ne sera l’objet d’aucun exercice.
Cela ne veut pas dire pour autant que ce qui s’y trouve n’est pas intéressant. Non mais des fois. 1. Petit retour sur une notion très rapidement survolée plus haut : celle de « programmation structurée ». Dans certains langages (historiquement, ce sont souvent des langages anciens), les lignes de programmation portent des numéros. Algorithmique pour l'apprenti programmeur. Qu'est-ce qu'un algorithme ? Les grenouilles partent en vacances. La notion de complexité. Un peu de pratique.