BTS SIO - Notes de cours

Accueil > Seconde Année > Algorithmique > Exercices du 02/09

Exercices du 02/09

samedi 7 septembre 2013, par

Voici la feuille d’exercices du 02/09.

Correction

Exercice a :
On utilise l’algorithme d’Euclide pour calculer le PGCD

Algorithme Euclide
Paramètres : a, b deux entiers naturels non nuls
Résultat : le PGCD de a et b
Variables : t,r entiers naturels
Debut
        # Pour l'algorithme d'Euclide, on doit s'assurer que a > b
        Si a <= b alors
                t <- a
                a <- b
                b <- t
        fin si
        # On commence l'algorithme par le calcul du reste de la division euclidienne de a par b
        r <- a mod b # on peut écrire aussi a%b
        tant que r != 0 faire
                a <- b
                b <- r
                r <- a mod b
        fin tant que
        # l'algorithme est fini, le reste est nul, le PGCD est dans b
        retourner b
Fin

Exercice b
On utilise l’algorithme précédent et la formule : PPCM(a,b)=a*b/PGCD(a,b)

Algorithme PPCM
Paramètres : a, b deux entiers naturels non nuls
Résultat : le PPCM de a et b
Variables :
Debut
        retourner a*b/PGCD(a,b)
Fin

Exercice c
On utilise la méthode du crible d’érathosthène.

Algorithme Erathosthene
Paramètres : n entier naturel > 2
Résultat : tableau P des nombres premiers < n
Variables : tableau de booléens T, i,j indices
Debut
        # le tableau T représente le fait pour un nombre d'être premier ou non. On suppose que tous sont premiers, et on va éliminer ceux qui ne le sont pas.
        pour i allant de 1 à n faire
                T[i] <- vrai
        fin pour
        i <-2
        tant que i*i<n faire
                si T[i] alors
                        # le nombre est premier, on élimine tous ses multiples
                        j=2
                        tant que j*i < n faire
                                # on élimine un multiple
                                T[j*i] <- faux
                                j <- j+1
                        fin tant que
                fin si
                i <- i+1
        fin tant que
        # on lit le tableau T en insérant dans P les nombres premiers
        j <- 0
        pour i allant de 1 à n faire
                si T[i] alors P[j]<- i
                j <- j+1
        fin pour
        retourner P
Fin

Attention ! Lors de ma correction au tableau j’ai omis d’incrémenter i dans la boucle tant que i*i<n faire. Pensez à corriger vos notes.

Un message, un commentaire ?

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.