CSC 3101 – Algorithmique et langage de programmation

Calcul du plus grand commun diviseur (∼40mn – moyen – obligatoire)

Le but de cet exercice est d'écrire un programme permettant de calculer le plus grand commun diviseur (pgcd) de deux entiers.

Créez un projet nommé pgcd contenant une classe Pgcd, elle-même contenant une méthode main.

Affichez les arguments de votre programme après avoir spécifié que ses paramètres sont 243 576.

Modifiez votre programme de façon à vérifier que le nombre d'arguments est bien égal à 2. Si ce n'est pas le cas, votre programme doit afficher un message d'erreur et quitter à l'aide de la méthode System.exit(n), où n est le code de retour de votre programme. Si vous vous souvenez de votre cours d'introduction aux systèmes, vous devriez vous rappeler que toute valeur différente de 0 signifie que votre programme quitte avec une erreur. Vérifiez que votre programme se comporte correctement en modifiant les paramètres. Après vos tests, pensez à rétablir les arguments 243 et 576.

Les arguments sont donnés sous la forme de chaînes de caractères. Il faut donc les convertir en entier avant de pouvoir calculer leur plus grand commun diviseur. Pour cela, définissez deux variables entières nommées p et q, et utilisez Integer.parseInt(uneChaine) pour convertir la chaîne de caractères uneChaine en entier. Affichez les valeurs de p et q.

Un algorithme calculant le plus grand commun diviseur peut reposer sur la propriété suivante :

si p=0, alors pgcd(p ,q) = q,
si q=0, alors pgcd(p ,q) = p,
si p>q, alors pgcd(p ,q) = pgcd(p-q, q),
sinon : pgcd(p, q) = pgcd(p, q-p).

Mettez en œuvre un algorithme itératif (par opposition à récursif) utilisant cette propriété pour calculer le plus grand commun diviseur de p et q. Pour cela, utilisez une boucle while. Si vous obtenez pgcd(243, 576) = 9, vous avez gagné, bravo !

Pgcd.java

Estimez la complexité de cet algorithme de PGCD dans le pire des cas en fonction de n = p + q.

Pour répondre à cette question, nous devons estimer la complexité des étapes de l'algorithme. Ici, tout est en

O (1)

. Ensuite, il nous faut borner le nombre maximum de passages dans la boucle while en fonction de n. Étant donné que p et q décroissent strictement à chaque tour de boucle, le nombre maximum d'itérations est n. En particulier, ce nombre d'itérations est atteint pour p=n-1 et q=1.
La complexité finale est donc

O (n)

Il est possible d'implémenter un algorithme de PGCD plus efficace en remarquant que si p ≥ q, pgcd(p, q) = pgcd(q, p mod q). Implémenter cette variation du PGCD.

Pgcd2.java

(Difficile) Estimez la complexité de ce nouvel algorithme dans le pire des cas en fonction de n = p + q. Pour cela, nous montrerons la propriété suivante : Soit

(p_{i}, q_{i})

tel que

p_{i} \geq q_{i}

et i le nombre d'itérations dans la boucle (si vous n'avez pas utilisé une structure récursive) avec ces deux entrées. Alors, nous avons

q_{i} \geq F i b_{i}

avec Fib la suite de Fibonacci. On rappelle que

F i b_{i} \underset{i \to + \infty}{\sim} φ^{i}

. Vous pouvez commencer par estimer la complexité de

p g c d (F i b_{i + 1}, F i b_{i})

en fonction de i, puis la traduire en une complexité en

F i b_{i}

Pour calculer la complexité de

p g c d (F i b_{i + 1}, F i b_{i})

, nous calculons

F i b_{i + 1} \equiv F i b_{i} + F i b_{i - 1} \equiv F i b_{i - 1} [F i b_{i}]

. Nous observons qu'à chaque étape, nous descendons d'un élément dans la suite de Fibonacci. On a donc une complexité linéaire en i. Comme

F i b_{i} \underset{i \to + \infty}{\sim} φ^{i}

on obtient une complixité en

O (l o g (F i b_{i}))

quand i tend vers l'infini.
Ensuite, on peut prouver la propriété par induction.

Si i = 0, alors $b_1=0 \ge Fib_0$
Si i = 1, alors $b_2 \ge 1 = Fib_1$
Pour k ≥ 1 itérations, on a l'enchainement $(a_{k+1}, b_{k+1}) \rightarrow (a_{k}, b_{k}) \rightarrow (a_{k-1}, b_{k-1})$ . Par conséquent, $a_k = b_{k+1}, a_{k-1} = b_k, b_{k-1} \equiv a_k [b_k]$ . On a donc $a_k = q*b_k+b_{k-1}, q \ge 1$ et $b_{k+1} \ge b_k+b_{k-1} \ge Fib_{k-1} + Fib_{k-2} = Fib_{k}$ .

À partir de là, on a informellement pour i très grand :

b_i \ge \phi^i

et donc

i \le \frac{log(b_i)}{log(\phi)}

. On en déduit que la complexité est en

\mathcal{O}(log(n))

Notons que le pire des cas se produit quand les entrées sont deux nombres de Fibonacci consécutifs.