Aller au contenu
Non seulement un programme doit être correct mais en plus il doit se terminer.- Par exemple, dans le cas d'une boucle dont on ne connaît pas le nombre de répétitions, il faut qu'à l'intérieur de ces boucles l'état de la mémoire évolue pour satisfaire la condition d'arrêt.
- boucle while condition booléenne do ..enddo
exemple 1 :
input('N = ',N);
I := 0;
while I < N do
begin
I :=I + 1 ;
writeln(I);
end;
- boucle repeat .. until condition booléenne
exemple 2 :
input('N = ',N);
I := 0;
repeat
I :=I + 1 ;
writeln(I);
until I = N;
- Autre exemple : Résolution de $f(x) = 0$ par dichotomie
Le théorème de BOLZANO qui est un corollaire du Théorème des valeurs intermédiaires affirme que :
Si $f$ est continue sue $[a \ ; \ b]$ et si $f(a)$ et $f(b)$ sont de signes contraires alors $\exists \ c \in [a \ ; \ b] \quad f(c) =0$
Pour déterminer une valeur approchée de $c$ on peut procéder par dichotomie :
- on part de l'intervalle $[ a \ ; \ b ]$ pour encadrer $c$
- puis on subdivise cet intervalle en deux sous-intervalles de même longueur
- on cherche dans quel sous-intervalle se trouve $c$
- on réitère ce procédé autant de fois qu'il faut jusqu'à atteindre la précision demandée
début
(* entrée des données *)
lire au clavier(a);
lire au clavier(b);
lire au clavier(n)
(* traitement *)
répéter
$ x := a; y := f(x);$ afficher(y);
$e := y; x:=\dfrac{a + b}{2};y := f(x); $afficher(y);
si $y*e > O$ alors a:=x
sinon $b:=x$;
afficher('nouvelle valeur de a = ',a);
afficher('nouvelle valeur de b = ',b);
jusqu'à $\mid (b - a) \mid < 10^{-n}$
(* affichage des résultats *)
afficher("par défaut à $10^{-n} \ c \approx $",a);
afficher("par excès à $10^{-n} \ c \approx $",b);
afficher(" à $10^{-n} \ c \approx $",$\dfrac{a + b}{2}$);
fin
- Cet algorithme se termine car la largeur de l'intervalle contenant $c$ décroît vers $0$ quand $n$ grandit.
au début $c$ se trouve dans un intervalle de longueur $b - a$.
au 1er tour $c$ se trouve dans un intervalle de longueur $\dfrac{b - a}{2}$.
au 2ème tour $c$ se trouve dans un intervalle de longueur $\dfrac{b - a}{2^2}$.
etc...
au 1er tour $c$ se trouve dans un intervalle de longueur $\dfrac{b - a}{2^n}$.
-
-
