Télécharger - Kiteb.net

Exemples d'exercices d'algorithmique corrigés avec l'analyse descendante
via pseudo-code

EX N°1
Soit la suite définie par :
. Le premier terme U0 est un entier donné qui dépasse 1.
. Le terme Un est égal à la somme des carrés des chiffres de [pic]
Cette suite est soit périodique ou stationnaire (constante). Établir les
analyses puis les algorithmes permettant d'afficher les termes de la suite
si elle est constante ou les termes de la période si la suite est
périodique.

Solution
|Analyse |
|Résultat = Proc Affiche (P,N,T) |
|(P,N,T)=[N(0,T[0](U0] |
|Répéter |
|N(N+1 |
|T[N](Fn SCC(T[N-1]) |
|P(Fn Recherche(T[N],0,N-1,T) |
|Jusqu'à (T[N]=1) ou (P>=0) |
| |
|U0=[ ] |
|Répéter |
|U0=Donnée("Donner un entier >1 ") |
|Jusqu'à U0>1 |

Le tableau de déclaration des nouveaux types
|Type |
|Tab = Tableau de 21 Entiers {les cases sont numérotées à |
|partir de 0} |

Le tableau de déclaration des objets globaux
|Objet |Type/Nature|Rôle |
|P |Entier |.....|
| | |.. |
|N |Entier |.....|
| | |.. |
|U0 |Entier |.....|
| | |.. |
|T |Tab |.....|
| | |.. |
|SCC |Fonction |.....|
| | |.. |
|Recherche|Fonction |.....|
| | |.. |

|Algorithme |
|Début Ex1 |
|Répéter |
|Écrire("Donner un entier >1 ") |
|Lire(U0) |
|Jusqu'à U0>1 |
|N(0, T[0](U0 |
|Répéter |
|N(N+1 |
|T[N](Fn SCC(T[N-1]) |
|P(Fn Recherche(T[N],0,N-1,T) |
|Jusqu'a (T[N]=1) ou (P>=0) |
|Proc Affiche(P,N,T) |
|Fin Ex1 |

. Analyse de la fonction SCC (Version itérative)
|Analyse |
|Résultat= SCC |
|SCC(S |
|S=[S(0] |
|Répéter |
|S(S+Carré(N mod 10) |
|N( N div 10 |
|Jusqu'à N =0 |

Le tableau de déclaration des objets locaux
|Objet|Type/Nature|Rôle |
|S |Entier |.....|
| | |.. |

|Algorithme |
|Def Fn SCC(N:Entier):Entier |
|S(0 |
|Répéter |
|S(S+Carré(N mod 10) |
|N(N div 10 |
|Jusqu'à N = 0 |
|SCC(S |
|Fin SCC |

. Analyse de la fonction SCC (Version Récursive)
|Analyse |
|Résultat= [ ] |
|Si N=0 Alors SCC(0 |
|Sinon |
|SCC(Fn SCC(N div10)+ Carré(N mod |
|10) |
|Fin Si |

|Algorithme |
|Def Fn SCC(N:Entier):Entier |
|Si N=0 Alors SCC(0 |
|Sinon |
|SCC(Fn SCC(N div 10)+ Carré(N mod 10) |
|Fin Si |
|Fin SCC |

. Analyse de la fonction Recherche (Version Itérative)

|Analyse |
|Résultat= Recherche |
|Recherche=[ ] |
|Si T[I]=X Alors Recherche (I |
|Sinon Recherche (-1 |
|Fin Si |
|I= [ I(D-1 ] |
|Répéter |
|I(I+1 |
|Jusqu'à (T[I]=X) ou(I=F) |

Le tableau de déclaration des objets locaux
|Objet|Type/Nature|Rôle |
|I |Entier |.....|
| | |.. |

|Algorithme |
|Def Fn Recherche(X,D,F:Entier; |
|T:Tab)Entier |
|I(D-1 |
|Répéter |
|I(I+1 |
|Jusqu'à (T[I]=X) ou(I=F) |
|Si T[I]=X Alors Recherche (I |
|Sinon Recherche (-1 |
|Fin Si |
|Fin Recherche |

. Analyse de la fonction Recherche (Version Récursive)
|Analyse |
|Résultat= [ ] |
|Si T[D]=X Alors Recherche (D |
|Sinon Si D>F Alors Recherche (-1 |
|Sinon |
|Recherche (Fn Recherche(X,D+1,F,T)|
| |
|Fin Si |

|Algorithme |
|Def Fn Recherche(X,D,F:Entier; T:Tab)Entier |
|Si T[D]=X Alors Recherche (D |
|Sinon Si D>F Alors Recherche (-1 |
|Sinon Recherche (Fn Recherche(X,D+1,F,T) |
|Fin Si |
|Fin Recherche |



. Analyse de la procédure Affiche
|Analyse |
|Résultat= [ ] |
|Si T[N]=1 Alors |
|Pour I de 0 à N Faire |
|Écrire(T[I]) |
|Fin Pour |
|Sinon |
|Pour I de P à N faire |
|Écrire(T[I]) |
|Fin Pour |
|Fin si |

Le tableau de déclaration des objets locaux
|Objet|Type/Nature|Rôle |
|I |Entier |.....|
| | |.. |

|Algorithme |
|Def Proc Affiche(P,N:Entier; T:Tab) |
|Si T[N]=1 Alors |
|Pour I de 0 à N Faire |
|Écrire(T[I]) |
|Fin Pour |
|Sinon |
|Pour I de P à N faire |
|Écrire(T[I]) |
|Fin Pour |
|Fin si |
|Fin Affiche |


EX N°2
Établir les analyses et les algorithmes permettant de déterminer les deux
entiers A et B qui représentent respectivement le numérateur et le
dénominateur de la somme des N fractions d'entiers.
Exemple:
[pic]

Solution
|Analyse |
|Résultat= Écrire("La somme est = |
|",A,"/",B) |
|(A,B)=Proc Somme(N,Num,Den,A,B) |
|N=[ ] |
|Répéter |
|N = donnée ("N = ") |
|Jusqu'à N dans[1..50] |
|(Num,Den)=Proc Lecture(N,Num,Den) |


Le tableau de déclaration des nouveaux types
|Type |
|Tab = Tableau de 50 |
|Entiers |

Le tableau de déclaration des objets globaux
|Objet |Type/Nature|Rôle |
|A |Entier |.....|
| | |.. |
|B |Entier |.....|
| | |.. |
|N |Entier |.....|
| | |.. |
|Num |Tab |.....|
| | |.. |
|Den |Tab |.....|
| | |.. |
|Lecture|Procédure |.....|
| | |.. |
|Somme |Procédure |.....|
| | |.. |

|Algorithme |
|Début Ex4 |
|Répéter |
|Écrire("N = "), Lire(N) |
|Jusqu'à N dans [1..50] |
|Proc Lecture(N,Num,Den) |
|Proc somme(N,Num,Den,A,B) |
|Écrire("La somme est = ",A,"/",B) |
|Fin Ex4 |


. Analyse de la procédure Lecture
|Analyse |
|Résultat= (Num,Den) |
| |
|(Num,Den) = [ ] |
|Pour I de 1 à N faire |
|Num[I]=Donnée ("Num[",I,"]=") |
|Répéter |
|Den[I]=Donnée ("Den[",I,"]=") |
|Jusqu'à Den[I]0 |
|X(Fn PGCD(Abs(Num[I]),Abs(Den[I])) |
|Num[I](Num[I] div X |
|Den[I](Den[I] div X |
|Fin Pour |

Le tableau de déclaration des objets locaux
|Objet |Type/Nature |Rôle |
|I |Entier |.....|
| | |.. |
|PGCD |Fonction |.....|
| | |.. |

|Algorithme |
|Def Proc Lecture(N:Entier; Var Num,Den: |
|Tab) |
|Pour I de 1 à N faire |
|Écrire("Num[",I,"]="), Lire(Num[I]) |
|Répéter |
|Écrire("Den[",I,"]="), Lire(Den[I]) |
|Jusqu'à Den[I]0 |
|X(Fn |
|PGCD(Abs(Num[I]),Abs(Den[I])) |
|Num[I](Num[I] div X |
|Den[I](Den[I] div X |
|Fin Pour |
|Fin Lecture |

. Analyse de la procédure Somme
|Analyse |
|Résultat= (A,B) |
|(A,B) = [A(0, B(1 ] |
|Pour I