Algo & Prog 1 Python : TP séance 03
- Rendu du TP sur Ametice :
- Suivez les instructions pour le rendu du TP en mettant le bon numéro de séance dans le nom du répertoire.
- N'oubliez pas de rendre votre travail à la fin de la séance comme indiqué, même si vous n'avez pas fini la planche de TP, puis de rendre la version finale avant le début de la séance suivante.
Exercice 1 : pgcd et récursivité
Pour chaque question écrire un programme principal qui permet de tester la fonction.
1.a. Calcul pour 2 entiers
Écrire une fonction récursive calculer_pgcd (a, b) qui calcule et renvoie le
plus grand commun diviseur entre 2 nombres \(a\) et \(b\) positifs. Utiliser la
définition suivante :
Par exemple : \(\text{pgcd}(85, 25) = \text{pgcd}(10, 25) = \text{pgcd}(10, 5) = \text{pgcd}(0, 5) = 5\).
1.b. Valeur absolue
Propriété : \(\forall a,b\;\) on a \(\;\text{pgcd}(a,b) = \text{pgcd}(|a|,|b|)\).
Écrire une fonction remplacer_abs_liste (liste) qui reçoit en paramètres
une liste d'entiers. La fonction remplace dans la liste les
entiers négatifs par leur valeur absolue.
1.c. Calcul sur une liste d'entiers
Écrire une fonction calculer_pgcd_liste (liste) qui reçoit en paramètre
une liste d'entiers positifs ou nuls.
La fonction calcule et renvoie le pgcd des entiers stockés dans liste.
- Utiliser la propriété 1 :
- \(\text{pgcd}(a, b, c) = \text{pgcd}(\text{pgcd}(a, b), c)\).
Par exemple, pour calculer le pgcd de \(a, b, c, d\) on calcule :
- \(x = \text{pgcd}(a,b)\) ;
- \(y = \text{pgcd}(x,c)\) ;
- \(z = \text{pgcd}(y,d)\) ;
le résultat est alors \(z\).
Traiter tous les cas de figure (1 élément, 2 éléments, ...) en utilisant si besoin la propriété 2. Si la liste est vide on renvoie 0.
Propriété 2 : \(\forall a \geq 0\;\) on a \(\;\text{pgcd}(a,0) = a\).
1.d. Saisie des entiers
Écrire un programme principal qui saisit des entiers (éventuellement négatifs) au clavier et les stocke dans une liste ; la saisie s'arrête lorsque l'on rentre 0. Le programme affiche un message d'erreur si on ne saisit pas un entier, mais continue quand même la saisie.
Le programme affiche ensuite le pgcd des entiers saisis.
Exercice 2 : points visibles
On appelle point visible (depuis l'origine) un point \(P\) de coordonnées entières \((x,y)\) telles qu'il n'existe aucun autre point de coordonnées entières sur le segment \([O,P]\).
Une condition équivalente est \(\text{pgcd}(x,y) = 1\).
2.1. Test de visibilité
Écrire une fonction est_visible(x,y) qui renvoie True si le point
\((x,y)\) est visible, sinon False.
2.2. Dessin d'une grille
Reprenez l'exemple de dessin en TkInter de la planche de TP01,
puis modifiez le programme de manière à ce qu'il saisisse un entier positif \(n\),
puis appelle la fonction dessiner_grille (zone_dessin, h, w, c, n) où
h est la hauteur et w est la hauteur de la zone de dessin (en pixels), et c est
la longueur en pixels du côté d'une case de la grille.
Écrire une fonction dessiner_grille qui affiche une grille rectilinéaire
(comme les carreaux d'un cahier) de \(n+1\) par \(n+1\) cases (il suffit de
tracer des traits horizontaux et verticaux).
Elle affiche également en bas, et à gauche, les coordonnées des cases de \(0\) à \(n\), comme sur un échiquier (mais que avec des chiffres).
2.3. Dessin des points visibles
Écrire la fonction dessiner_points_visibles (zone_dessin, h, w, c, n) et
appeler la fonction dans le programme principal, juste après l'appel
de dessiner_grille.
La fonction dessiner_points_visibles affiche une croix bleue dans chaque
case \((x,y)\) telle que \(0 \leqslant y \leqslant x \leqslant n\)
si \((x,y)\) est un point visible.
2.4. Comparaison avec Farey
Recopier la fonction calculer_suite_Farey (n) du TP précédent, ainsi
que les fonctions qu'elle appelle.
Appeler calculer_suite_Farey (n) dans votre programme principal,
puis la fonction dessiner_suite_de_Farey (à écrire) qui pour chaque
fraction \(h/k\) de la suite de Farey, affiche un petit cercle rouge
dans la case de coordonnées \((k, h)\).
Que constatez-vous, est-ce que les carrés bleus et les cercles rouges se superposent tous ?