Algorithmes : Généralités

Algorithme

Étant un problème, nous appelons algorithme une suite d'instructions décrivant un processus visant à résoudre ce problème. Ce processus travaille sur un ensemble d'objets (les variables)  et appelle certaines fonctions d'un ensemble de fonctions lié au langage de programmation.

Les instructions de base de l'algorithme sont :

  •  la déclaration, l'affectation de variable;
  •  les instructions conditionnelles qui ne seront exécutées que dans certains cas;
  •  la boucle, qui exécute plusieurs fois la même instruction dans unprogramme.

Algorithme linéaire

On dit que l'algorithme est linéaire s'il n'y a ni boucle, ni conditionnelle

  •  On entre des valeurs : affectation avec input
  •  On effectue des calculs : affectation
  •  On affiche les résultats : print

 pas de conditionnelle, pas de répétition.

instructions composées

Elles se composent :

  •  d'une ligne d'en-tête terminée par deux-points ;
  •  d'un bloc d'instructions indenté au même niveau.

Remarque :  S'il y a plusieurs instructions indentées sous la ligne d'en-tête, elles doivent l'être exactement au même niveau (comptez un décalage de 4 caractères, par exemple).

Attention, l'indentation est importante en Python

Remarque :  On peut imbriquer des instructions composées pour réaliser des structures de décision complexes.

Exemple :

  • valeurs=(2,3,4,6,8)
  • somme = 0.0
  • nb_valeurs = 0
  • for v in valeurs:
  •     nb_valeurs = nb_valeurs + 1
  •     somme = somme + v
  • moyenne = somme / nb_valeurs
  • print(moyenne)

Choisir : L'instruction if

if expression1:
    instruction1
elif expression2:
    instruction2
else:
    instruction3

  •  La valeur de expression1 est évaluée et, si elle est Vrai, instruction1 est exécutée.
  •  si expression1 est Faux, la valeur de expression2 est évaluée et, si elle est Vrai, instruction2 est exécutée.
  •  si expression1 et expression1 sont False alors instruction3 est exécutée.

Remarque :  instruction1, instruction2 et instruction3 peuvent être des instructions simples ou des blocs.

Remarque :  La clause else peut être omise.
\mc{Syntaxe compacte d'une alternative} : pour les plus motivés
Pour trouver, par exemple, le minimum de deux nombres, on peut utiliser écrire classiquement :

  • x, y = 4, 3
  • if x < y:
  •    plus_petit = x
  • else:
  •    plus_petit = y

ou une écriture  condensée :

  • x, y = 4, 3
  • plus_petit = x if x < y else y

L'instruction while

while expression:
    instruction # ou bloc d'instructions

  •  instruction est exécutée de façon répétitive aussi longtemps que le résultat de expression est Vrai.
  •  expression est évaluée avant chaque exécution de instruction.
  •  si vous avez besoin d'un compteur pour savoir combien d'itérations vous avez effectués, vous devez le gérer vous même (cpt=0 avant la boucle, cpt = cpt+1 dans la boucle)

Exemple I : Saisir et contrôler une saisie.

n = input('Entrez un entier [1 .. 10] : ')
while (n < 1) or (n > 10):
      n = input('Entrez un entier [1 .. 10], S.V.P. : ')
      n=int(n)
print(n)

Exemple II : Déterminer le plus grand entier $n$ tel que $2^n\leq x$.

x=int(input('Entrez un nombre : '))
y=x  # on réserve la valeur pour l'affichage.
cpt = 0
while x > 0:
     x = x // 2 # division avec troncature
     cpt += 1 # incrémentation
cpt=cpt-1
print("2^",cpt,"=",2**(cpt),"<=",y,"<",2**(cpt+1),"=2^",cpt+1)

L'instruction for

Avec une instruction for, on parcourt des séquences

  • les textes (str) : ce sont des suites de lettres :     "Ceci est du texte" ;
  • les listes (list) :  ce sont des suites  de termes  très variés : [4,6,'texte',3,'x']
  • les tuples (tuple) : ce sont des listes non modifiables.

exemple : Mesurer quelques chaînes:
a = ['chat', 'fenêtre', 'défenestrer']
for x in a:
    print (x, len(x))

Remarque : par principe, ne pas modifier la séquence sur laquelle on itère ni modifier la variable d'itération

Ceci étant, les programmes tournent. peut-être pas comme vous l'espériez !

Modification du compteur

  • for x in range(10):
  •     if x==5:x=9
  •     print(x)

Modification de la séquence

  • L=list(range(10))
  • for x in L:
  •     L=L+[1]
  •     print(x)
  • print(L)

La Fonction range()

Si on a besoin d'itérer sur une progression arithmétique, on utilise la fonction range

  • for i in range(debut,pas, fin)
  •  range(fin) :  affiche tous les entiers de 0 à fin-1 qui doit être une entier.

Exemple :  range(10) affiche [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
En réalité, il faut écrire list(range(10)) pour avoir l'affichage

  •  range(debut,fin) :  affiche tous les entiers de debut à fin-1 qui doit être une entier.

Exemple :  range(5, 10) affiche  [5, 6, 7, 8, 9]

  •  range(debut,fin,pas) : affiche tous les entiers de debut à fin-1 avec un incrément pas (même négatif)

Exemple :  range(0, 10, 3) affiche  [0, 3, 6, 9]

Remarque:Le nombre $fin$ en paramètre n'est jamais dans la liste générée ;

$> > >$ range(10) génère une liste de 10 valeurs commençant par 0

Court-circuiter une boucle

Remarque : pour les plus motivés

2 instructions continue, break permettent de gérer les boucles en évitant d'exécuter la totalité des instructions d'une boucle.

  • [continue : ]Passe immédiatement à l'itération suivante de la boucle for ou while en cours contenant l'instruction en reprenant à la ligne de l'en-tête de la boucle
  • [break : ]Sort immédiatement de la boucle for ou while en cours contenant l'instruction.

Remarque :  Dans la pratique, ces deux instructions sont assez souvent utilisées. Même avec une boucle for, l'usage de l'instruction break est cohérent : for signifiant que l'on parcourt un ensemble, mais dès qu'on a ce que l'on cherche, on s'arrête. Cependant, on les déconseille pour les débutants

Attention : utiliser ces instructions avec précaution, pour beaucoup, for signifie que l'on sait combien d'itérations, on va faire (cette approche de la boucle for est incompatible avec l'instruction break).

Remarque :  Lorsque l'on utilise une fonction, l'usage d'un return au milieu d'une boucle interrompt toutes les boucles et finit la fonction (un super break en somme)

ne pas écrire des bouvles while avec for + break, ne pas écrire des boucles for avec while + compteur.
 

Fichier Joint: 

Ajouter un commentaire

Plain text

  • Aucune balise HTML autorisée.
  • Les adresses de pages web et de courriels sont transformées en liens automatiquement.
  • Les lignes et les paragraphes vont à la ligne automatiquement.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Saisir les caractères affichés dans l'image.