Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Les sous
Extrait - Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition)
Extraits du livre
Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition) Revenir à la page d'achat du livre

Les sous-programmes

Procédures et fonctions

Vous êtes encore en train d’apprendre à modéliser votre pensée en informatique avec des problèmes assez simples et dans ce chapitre vous allez aller un plus loin dans votre réflexion. Imaginez un programme comme un logiciel de vidéo à la demande ou encore un client de messagerie ? Ne pensez-vous pas que ces programmes contiennent des millions, voire des milliards d’instructions ? Comment donc se retrouver facilement dans cette nuée d’instructions ?

Une première réponse est assez simple : découpez votre logique en petites parties qui seront appelées à la demande. Cette découpe permet de fortement réduire la complexité du programme en se focalisant uniquement sur des sous-problèmes plus simples à résoudre. Ces parties sont les sous-programmes qui seront appelés dans le programme principal, le point d’accès de l’application, comme le représente la figure suivante.

images/06RI01V3.png

Programme principal et sous-programmes

En algorithmie, les sous-programmes se déclarent avant le programme comme suit :

SOUS-PROGRAMME sous_prog_A  
VAR  
   ... 
DEBUT  
   ... 
FIN  
PROGRAMME principal  
VAR  
   ... 
DEBUT  
   ...  
   sous_prog_A 
FIN 

En réalité, un programme n’est que rarement composé d’une seule série d’instructions qui s’enchaînent les unes après les autres. Pour pouvoir créer et maintenir correctement une application, les développeurs décomposent toujours le programme principal en plusieurs sous-programmes qui vont être appelés par ce dernier. Les sous-programmes représentent en fait une petite fonctionnalité du programme. Ils peuvent également s’appeler entre eux pour définir une hiérarchie de tâches.

Prenons comme exemple un jeu simple : le jeu du pendu. Décomposons-le en termes de fonctionnalités :

  • Saisie du mot à deviner.

  • Initialisation du mot masqué.

  • Lancement de la partie :

  • Affichage du mot masqué.

  • Saisie de la lettre de l’utilisateur....

L’élégance de la récursivité

Par définition, un sous-programme récursif est un sous-programme qui s’appelle lui-même.

L’objectif de la récursivité est de simplifier, en théorie, un traitement complexe contenant des itérations, en écrivant uniquement des traitements simples. Cependant, il existe toujours un fossé entre la théorie et la pratique.

Regardons un peu l’évolution des langages de programmation avec beaucoup de vulgarisation. Les premiers langages de programmation, et encore certains exotiques de nos jours, n’implémentaient pas les structures itératives, seulement les conditionnelles. Comment faire alors pour répéter une instruction ?

Simplement en rappelant le sous-programme contenant cette instruction dans une conditionnelle, jusqu’à ce que la condition d’arrêt de l’itération, mise donc dans la condition du SI, soit juste.

Modélisons ce principe avec l’affichage d’un tableau.

Pour afficher un tableau, nous devons le parcourir du premier élément au dernier. Nous devons donc nous arrêter après l’affichage de ce dernier élément. Ainsi notre condition d’arrêt est "nous avons traité le dernier élément".

Un parcours de tableau se fait grâce à un compteur qui s’incrémente au fur et à mesure du parcours. Nous pouvons donc modéliser notre condition d’arrêt ainsi : le compteur doit être supérieur à la taille du tableau. Si j’ai traité le dernier élément du tableau je m’arrête, c’est-à-dire le compteur est arrivé à la taille du tableau.

Il existe plusieurs types de récursivités : la simple, la multiple, la croisée et l’imbriquée. Nous n’aborderons dans ce chapitre que les deux premiers types et nous laissons le lecteur aller plus loin par lui-même pour les deux derniers. Ces différents types de récursivités sont tous basés sur le même principe que la récursivité simple, seule la hiérarchie des appels récursifs change.

1. Récursivité simple

La récursivité simple...

Algorithmes avancés sur les tableaux

L’objectif principal de l’informatique est de simplifier les traitements complexes pour l’utilisateur. Il va donc de soi que lorsqu’un programme travaille sur des tableaux, saisis par l’utilisateur ou non, il doive trier ces tableaux pour en faciliter les manipulations et donc les recherches.

Maintenant que nous avons étudié les sous-programmes et la récursivité, nous pouvons voir comment effectuer ces tris en partant des algorithmes les plus simples pour l’être humain, donc les moins performants pour la machine, aux plus optimisés pour l’ordinateur, donc les moins simples pour le cerveau humain (sous-entendu utilisant des sous-programmes récursifs).

1. Procédure échanger

Lorsque nous trions un tableau, nous sommes sûrs de devoir échanger des valeurs assez fréquemment. Nous allons définir une procédure pour effectuer cette opération afin de la réutiliser dans les algorithmes de tri qui suivent.

PROCEDURE echanger(E/S : x, y : ENTIER)  
VAR  
   tmp : ENTIER  
DEBUT  
   tmp <- x  
   x <- y  
   y <- tmp  
FIN 

2. Tri par sélection

Le tri par sélection est le tri ayant la logique la plus simple. Nous commençons par chercher la plus petite valeur du tableau et nous la plaçons à la première case en décalant les autres cases, comme le montre la figure ci-après. Il ne nous reste plus qu’à appliquer les mêmes opérations sur le sous-tableau commençant à la case 2, puis celui commençant à la case 3, etc. jusqu’à arriver à un dernier sous-tableau de taille 1, ce qui indique que le tableau est bien trié.

images/06RI05V3.png

Tri par sélection

Le tri par sélection demande donc deux manipulations :

  • Trouver la plus petite valeur.

  • Échanger la case courante avec la première case du sous-tableau correspondant. 

Nous avons donc besoin d’un sous-programme pour rechercher la plus petite valeur, ou plutôt l’indice de la plus petite valeur d’un tableau.

FONCTION indice-minimum (tab : TABLEAU[] : ENTIER, début, 
taille : ENTIER) : ENTIER  ...

Fonctions et procédures avec Python

Comme nous l’avons remarqué dans la section précédente, le Python n’implémente que les fonctions.

1. Les fonctions en Python

Les fonctions en Python sont obligatoirement déclarées en début de script. Le bloc d’instructions est obligatoire pour les fonctions. Si nous devons, pour une raison de praticité, laisser le corps d’une fonction vide, nous utilisons le mot-clé pass. Pour définir une fonction, nous utilisons le mot-clé def.

Une bonne pratique pour séparer les fonctions du code principal est d’utiliser une instruction if particulière à Python :

if __name__ == '__main__': 

# une fonction sans corps  
def maFontion():  
   pass  
  
# code pour la procédure affiche_tableau  
def afficheTableau(tab):  
   for e in tab:  
      print(e)  
  
# code de la procédure double  
def double(a):  
   return a * a  
  
# code de la fonction maximun  
def maximun(a,b):  
   if a > b :  
      return a  
   else:  
      return b  
  
# programme principal  
if __name__ == '__main__':  
   afficheTableau([1,2,3])  
   a...

Exercices

1. Exercice 1

Écrivez un algorithme qui calcule dans un sous-programme la surface d’un cercle. Codez le script Python correspondant.

2. Exercice 2

Écrivez un algorithme qui calcule dans un sous-programme le volume d’une boîte. Codez le script Python correspondant en utilisant des valeurs par défaut pour les paramètres de la fonction.

3. Exercice 3

Écrivez un algorithme qui calcule et retourne dans un sous-programme la valeur la plus grande d’un tableau entre celles des deux indices passés en paramètres. Codez le script Python correspondant.

4. Exercice 4

Écrivez un algorithme avec un sous-programme qui retourne le nom du mois en fonction de son numéro. Par exemple, si l’utilisateur entre 1, il sera affiché janvier. Codez le script Python correspondant.

5. Exercice 5

Écrivez un algorithme qui calcule le nombre de mots d’une chaîne de caractères avec un sous-programme. Nous considérons que deux mots sont uniquement séparés par un espace pour des raisons de simplicités. Codez le script Python correspondant.

6. Exercice 6

Écrivez un algorithme qui donne le nombre de chiffres d’un entier entré par l’utilisateur. Codez le script Python correspondant.

7. Exercice 7

Écrivez un algorithme qui détermine si deux mots sont des anagrammes ou non. Codez le script Python correspondant....