Algo & Prog 1 Python : TP séance 02

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.

Vocabulaire : les mots employés dans l'énoncé ont un sens très précis, ne confondez pas :

la fonction saisit → elle fait un input
la fonction affiche → elle utilise print
la fonction renvoie → elle fait un return

Exercice 1 : fractions, utilisation de tuples

On se propose de manipuler des fractions \(h/k\) sous la forme de tuples (h,k).

1.a. Saisie

Écrivez une fonction saisir_frac() qui saisit au clavier les 2 membres entiers d'une fraction puis les renvoie dans un tuple.

1.b. Affichage

Écrivez une fonction afficher_frac (f) qui reçoit en paramètre une fraction sous la forme d'un tuple, puis affiche la fraction sous la forme "h/k" sans espace ni retour à la ligne.

1.c. Médian

On appelle médian de \(h/k\) et \(h'/k'\) la fraction \((h+h')/(k+k')\). Écrivez une fonction calculer_median (f, g) qui reçoit en paramètres deux fractions sous la forme de tuples, puis renvoie leur médian dans un tuple.

1.d. Programme

Écrivez un programme utilisant les 3 fonctions, qui saisit 2 fractions, calcule leur médian puis l'affiche.

Exercice 2 : suites de Farey, liste de tuples, insertion par recopie

Les suites de Farey \(F_n\) d'ordre \(n\) sont les séries croissantes de fractions irréductibles entre 0 et 1, dont les dénominateurs n'excèdent pas \(n\).

Les premières suites sont :: \(F_1 : 0/1 < 1/1\); \(F_2 : 0/1 < 1/2 < 1/1\); \(F_3 : 0/1 < 1/3 < 1/2 < 2/3 < 1/1\); \(F_4 : 0/1 < 1/4 < 1/3 < 1/2 < 2/3 < 3/4 < 1/1\)

Dans tout l'exercice on code une suite de Farey sous la forme d'une liste de tuples, par exemple \(F_2\) par [(0,1), (1,2), (1,1)].

2.a. Affichage

Écrivez la fonction afficher_suite_Farey (sf) qui affiche la suite de Farey reçue en paramètre, sur une seule ligne en utilisant afficher_frac().

Par exemple, si sf représente \(F_3\), on devra obtenir cet affichage :

0/1 < 1/3 < 1/2 < 2/3 < 1/1

Tester la fonction dans un programme principal, et faire de même pour les questions suivantes.

2.b. Test de l'ordre

Écrivez la fonction frac_est_ordre_n (f, n) qui reçoit en paramètres une fraction f irréductible entre 0 et 1 sous la forme d'un tuple, et un entier n. La fonction renvoie True si son dénominateur n'excède pas n, sinon False.

2.c. Construction d'une suite

Propriété 1 : si \(h/k < h''/k'' < h'/k'\) sont 3 termes successifs de \(F_n\), alors \(h''/k''\) est le médian de \(h/k\) et \(h'/k'\).

Étant donnée la suite de Farey \(F_{n-1}\), on peut donc construire \(F_n\) en intercalant entre chaque couple de fractions successives de \(F_{n-1}\) leur médian lorsque son dénominateur n'excède pas \(n\).

Écrire la fonction construire_suite_Farey (n, sf_n_1) qui reçoit en paramètres un ordre \(n > 1\) et la suite de Farey sf_n_1 d'ordre \(n-1\). La fonction construit la suite \(F_n\) à l'aide de la propriété 1, puis la renvoie.

2.d. Calcul depuis le début

Écrire la fonction calculer_suite_Farey (n) qui calcule la suite de Farey d'ordre \(n \geq 1\) puis la renvoie. La fonction part de \(F_1\) puis construit les suites \(F_2\), ... \(F_n\) en itérant sur construire_suite_Farey().

Exercice 3 : utilisation de dict et de set

3.a. Unicité

Écrire une fonction verifier_unicite_fractions (sf) qui reçoit en paramètre une suite de Farey sf sous la forme d'une liste de tuples, chaque tuple représentant une fraction comme dans les exercices précédents. La fonction renvoie True si chacune des fractions de la suite est unique dans la suite, sinon False.

Pour déterminer l'unicité, convertir la liste (qui est de type list) en ensemble (de type set) puis comparer leurs longueurs respectives.

Écrire un programme principal permettant de tester différents cas de figure, puis tester sur des suites obtenues avec construire_suite_farey.

3.b. Rang d'une fraction

Écrire une fonction creer_dictionnaire_rangs (sf, n) qui reçoit en paramètre une suite de Farey sf et son ordre n. La fonction calcule puis renvoie un dictionnaire dico_rangs dans lequel chaque clé est un tuple représentant une fraction, et la valeur associée est son rang dans sf, c'est-à-dire son indice dans la liste.

Par exemple pour \(F_2\), la fonction renvoie { (0,1) : 0, (1,2) : 1, (1,1) : 2 }.

Écrire un programme principal qui demande à saisir un ordre n, puis calcule \(F_n\) et le dictionnaire de rangs. Le programme entre ensuite dans un boucle infinie, dans laquelle il saisit une fraction, cherche son rang dans le dictionnaire de rangs, affiche le rang si il a été trouvé, sinon il affiche "absent". La boucle de saisie s'interrompt lorsque 0 0 est saisi.

Exercice 4 : cercles de Ford

Étant donné une suite de Farey \(F_n\), les cercles de Ford de la suite sont les cercles de centre \(\displaystyle (\frac{h}{k},\frac{1}{2k^2})\) et de rayon \(\displaystyle\frac{1}{2k^2}\) pour chaque fraction \(h/k\) de \(F_n\).

Ces cercles ont une propriété remarquable : deux cercles de Ford sont tangents si et seulement si leurs fractions sont consécutives dans une des suites de Farey.

Reprenez l'exemple de dessin en TkInter de la planche de TP01, puis modifiez le programme de manière à ce qu'il saisisse un ordre \(n\), calcule \(F_n\) puis appelle la fonction dessiner_cercles_Ford (zone_dessin, h, w, n) (à écrire) qui dessine les cercles de Ford correspondants.

Dans la fonction il faudra multiplier les coordonnées par la largeur h et la hauteur w de la zone de dessin pour que les cercles prennent tout l'espace.