Algorithmique - Correction du TD3 - univ-artois.fr

1 Algorithmique - Correction du TD3. IUT 1 re Ann e 18 d cembre 2012. 1 Les boucles (suite). Exercice 1. Ecrire un algorithme qui re oit en entr e un nombre entier de 1 10 et affiche en sortie la table de multiplication de ce nombre. Par exemple, si l'algorithme re oit le nombre 7, il affichera la table : 1 7 = 7. 2 7 = 14.. 10 7 = 70. Algorithme 1: Table de Multiplication variables entier i ,n d but lire n pour i de 1 10 faire afficher i " fois " n " est gal " i n fin Exercice 2. A la naissance de Marie, son grand-p re Nestor, lui ouvre un compte bancaire. Ensuite, chaque anniversaire, le grand p re de Marie verse sur son compte 100 e, auxquels il ajoute le double de l' ge de Marie.

2 Par exemple, lorsqu'elle a deux ans, il lui verse 104 e. Ecrire un algorithme qui permette de determiner quelle somme aura Marie lors de son n-i me anniversaire. Algorithme 2: Compte de Marie variables entier compte,age d but compte 0. pour age de 1 n faire compte compte + 100 + (2 age). afficher "Le compte de Marie au n-i me aniversaire est " compte fin Exercice 3. La population des Sims Alpha est de 10, 000, 000 d'habitants et elle augmente de 500, 000 habitants par an. Celle des Sims Beta est de 5, 000, 000 habitants et elle augmente de 3% par an. Ecrire un algorithme permettant de d terminer dans combien d'ann es la population de Sims Beta d passera celle des Sims Alpha.

3 1. Algorithme 3: Populations alpha et beta variables entier ann es,alpha,beta d but alpha 10 000 000. beta 5 000 000. ann es 0. tant que beta alpha faire ann es ann es + 1. alpha alpha + 500 000. beta beta afficher "Il faut " ann es " ann es pour que la population de beta d passe celle de alpha". fin Exercice 4. Corriger le programme C++ suivant afin de r soudre le probl me suivant : Donn es : un nombre entier positif n 1. R sultat : le r sultat de la suite harmonique : n P. i =1 i Algorithme 4 Suite Harmonique #include <iostream >. using namespace std ;. i nt main ( ). {. i nt i , n ;. f l o a t somme = 0 ;. cout << " Entrer l e nombre e n t i e r : ".}

4 Cin >> n ;. for ( i = 1 ; i <= n ; i ++). somme = somme + 1 . 0 / i ;. cout << "Le r s u l t a t e s t : " << somme << endl ;. return 0 ;. }. Exercice 5. Construire un algorithme permettant d' valuer vos chances de gagner dans l'ordre ou dans le d sordre au tierc , quart ou quint . De mani re formelle, le probl me est le suivant : Donn es : un nombre p de chevaux partants et un nombre j {3, 4, 5} de chevaux jou s R sultat : la probabilit de gagner au jeu dans l'ordre, et la probabilit de gagner au jeu dans le d sordre 2. Rappel : les formules habituelles de comptage sont donn es dans la table ci-jointe. Nombre de possibilit s de construire une liste ordonn e, avec r p titions, de j l ments pj parmi p p!

5 Nombre de possibilit s de construire une liste ordonn e, sans r p tition, de j l ments (p j )! parmi p p! Nombre de possibilit s de construire un ensemble non ordonn , sans r p tition, de j l - (p j )! j ! ments parmi p Note : dans la Correction on utilise la fonction factorielle d j d finie en cours et en TD. N'h sitez pas r utiliser les fonctions ou proc dures que vous avez d j construites. Algorithme 5: Tierc . variables entier p, j d but afficher "Chevaux partants : ". lire p afficher "Chevaux jou s : ". lire j afficher "Probabilit de gagner dans l'ordre : " fact(p j )/fact(p). afficher "Probabilit de gagner dans le d sordre : " fact(p j ) fact( j )/fact(p).

6 Fin 2 Les tableaux Exercice 6. Corriger l'algorithme en pseudo-code suivant afin de r soudre le probl me suivant : Donn es : deux vecteurs p et q dans un espace ( euclidien ) 3 dimensions R sultat : la somme des vecteurs p + q Algorithme 6: Somme De Vecteurs variables r el p[3]. r el q[3]. r el r[3]. d but pour i 0 2 faire r[i ] p[i ] + q[i ]. fin Exercice 7. Ecrire un algorithme permettant de r soudre le probl me suivant : Donn es : deux vecteurs p et q dans un espace ( euclidien ) 3 dimensions R sultat : le produit scalaire de p et q 3. Algorithme 7: Produit Scalaire variables r el p[3]. r el q[3]. r el v d but v 0. pour i 0 2 faire v v + (p[i ]*q[i ]).

7 Afficher v fin Exercice 8. Pour sa naissance, la grand-m re de Gabriel place une somme de 1000 e sur son compte pargne r - mun r au taux de (chaque ann e le compte est augment de ). D velopper un algorithme permettant d'afficher un tableau sur 20 ans associant chaque anniversaire de Gabriel la somme acquise sur son compte. Algorithme 8: Compte de Gabriel variables r el compte[21], i d but compte[0] 1000. pour i 1 20 faire compte[i ] compte[i ] fin Exercice 9. Felix est un fermier qui dispose d'un couple de shadoks capables de se reproduire vitesse ph nom nale. Un couple de shadocks met deux mois pour grandir ; partir du troisi me mois, le couple de shadocks engendre une paire de nouveaux shadocks (qui mettront deux mois pour grandir et donc trois mois pour engendrer une nouvelle paire, etc.)

8 Et surtout, les shadoks ne meurent jamais ! D'apr s cet exercice le nombre de couples de shadoks F n chaque mois n ob it la loi : F1 = 1. F2 = 1. F n = F n 1 + F n 2. D velopper un algorithme permettant de construire le tableau des couples depuis le premier jusqu'au 20 me mois. Algorithme 9: Suite de Fibonacci variables r el couples[20]. d but couples[0] 1. couples[1] 1. pour i 2 19 faire couples[i ] couples[i 1] + couples[i 2]. fin Exercice 10. Corriger le programme C++ suivant afin de r soudre le probl me suivant : Donn es : un tableau de 100 entiers, une valeur enti re x R sultat : le nombre d'occurrences de x dans le tableau 4. Algorithme 10 Nombre d'ccurrences #include <iostream >.

9 Using namespace std ;. i nt main ( ). {. i nt tableau [ 1 0 0 ] ;. i nt i , x , occurrences ;. cout << " Entrer votre valeur : " ;. cin >> x ;. i = 0;. occurrences = 0 ;. for ( i = 0 ; i < 100; i ++). occurrences = occurrences + ( x == tableau [ i ] ) ;. cout << occurrences << endl ;. return 0 ;. }. Exercice 11. Nous souhaitons d velopper un algorithme permettant de rechercher un l ment dans un tableau de 100 entiers en partant des deux extr mit s. Dans cette perspective, corriger le programme C++ suivant. Algorithme 11 Recherche Bipolaire #include <iostream >. using namespace std ;. i nt main ( ). {. i nt tableau [ 1 0 0 ] ;. i nt i , j , x.}

10 Bool trouve ;. cout << " Entrer votre valeur : " ;. cin >> x ;. i = 0;. j = 99 ;. trouve = 0 ;. do {. trouve = ( tableau [ i ] == x ) | | ( tableau [ j ] == x ) ;. i ++;. j ;. }. while ( ! trouve && i <= j ) ;. cout << trouve << endl ;. return 0 ;. }. Exercice 12. Ecrire un algorithme permettant de r soudre le probl me suivant : Donn es : un tableau tableau contenant 100 entiers R sultat : vrai si les entiers sont cons cutifs et faux sinon Rappel : deux entiers x et y sont cons cutifs si et seulement si y = x + 1. 5. Algorithme 12: El ments cons cutifs variables entier tableau[100], i bool en cons cutifs d but cons cutifs vrai i 0. tant que (cons cutifs = vrai) et (i < 99) faire cons cutifs tableau[i + 1] = tableau[i ] + 1.