TP 1: Divisibilité dans $\mathbb{Z}$

Environnement de travail

Aller dans Outils >Lycée > Informatique >Python>IDLE ou utiliser wing 101

Faire new File pour ouvrir l'éditeur de texte pour pouvoir écrire un programme

A chaque fois qu'un programme est écrit le sauvegarder en faisant CTRL S. La première fois donner un nom significatif au programme, avec un suffixe .py

Ensuite pour exécuter le programme faire F5

Algorithme de division euclidienne

Données : $a$ un entier relatif, $b$ un entier naturel non nul

Sortie : un entier relatif $q$ le quotient et un entier naturel $r$ tel que $a = bq+r$ avec $0 \leqslant r < b$

$b = 2$ et $a = 1003$ donc $q = 500$, $r = 3$

Faire une boucle pour retrancher $b$ de $a$ si $a > 0$ tant que $a > b$ (ou ajouter $b$ à $a$ si $a > 0$ tant que $a < 0$

Une suite croissante

la suite de Sylvester est définie par

$s_{n+1} = (s_{n}-1)\times s_n + 1$ avec $s_0 = 3$

Exercices

  1. Utiliser le squelette suivant sylvester.txt compléter le en suivant les questions suivantes, enregistrer le au format .py et exécuter le
  2. Définir une fonction $g(x)$ en Python telle que $s_{n+1}=g(s_n)$
  3. Utiliser cette fonction $g(x)$ pour compléter la fonction afficheTermes(p) qui affiche les $p$ premiers termes de la suite de Sylvester
  4. Que vaut $s_9$ ?
  5. Compléter la fonction nombreChiffres(n) qui permet de calculer le nombre de chiffres de $n$ (faire une boucle de divisions par 10 tant qu'on peut)
  6. En utilisant l'opérateur modulo % pour chaque terme affiché $s_n$ de $s_0$ à $s_{p-1}$ dans afficheTermes(p) calculer la somme des chiffres de $s_n$ modulo 9 et afficher le résultat

Chiffrement de César

Il s'agit de chiffrer un poème de Paul Verlaine disponible ici, par la méthode de décalage de César

  1. Utiliser le squelette suivant cesar.txt compléter le en suivant les questions suivantes, enregistrer avec le nom cesar.py et exécuter le
  2. Il s'agit d'écrire une fonction decale(car,debut,cle) qui décale le caractère car de cle caractères s'il est dans une des trois zones des caractères ASCII définies ci-dessous de taille 26 et qui commence par debut égale à "A" ou "a" ou "à"

    Les majuscules 'A' jusqu'à 'Z' ont leur nombre d'identification compris entre 65 et 92

    Les minuscules 'a' jusqu'à 'z' ont leur nombre d'identification compris entre 97 et 122

    Certaines minuscules accentuées 'à' jusqu'à 'ù' ont leur nombre d'identification compris entre 224 et 249

    Pour construire cette fonction utiliser ord() chr() et %

    La fonction ord(car) donne le nombre d'identification d'un caractère par exemple, ord('A') retourne 65

    La fonction chr(nombre) donne le caractère associé au nombre, par exemple chr(65) retourne 'A'

    Si on fait un décalage de 3 il faut s'assurer que l'image de 'z' soit 'c' et non pas '}' (on reste dans l'alphabet), d'où l'utilité de l'opérateur modulo % pour rester dans l'alphabet

  3. La fonction cesar(nom_de_fichier_clair,nom_fichier_chiffre,k) est donnée elle ouvre un fichier texte en lecture, lit chaque ligne et pour chaque caractère de la ligne, s'il est dans une des trois zones en question, le décale de k caractères
  4. Comment déchiffrer lorsqu'on connaît la clé k ?
  5. Enfin, voici un poème mystère qui a été chiffré par la méthode de César mais on a perdu la clef, déchiffrer le (méthode "brute"). Qui est le poète ?

Tables de multiplication et arithmétique modulaire

D'abord voir ici pour comprendre le type de dessin que l'on veut produire, ou encore ici(en anglais)

D'abord on place $N$ points régulièrement espacés sur un cercle.

Comment placer sur un cercle centré à l'origine du repère et de rayon $R$, $N$ points regulièrement espacés ?

Un cercle de rayon $R$ a pour périmètre $2\pi R$. Il suffit de prendre comme unité d'angle $\dfrac{2 \pi}{N}$, et donc de l'origine on voit chaque point du cercle sous un angle $k\times \dfrac{2 \pi}{N}$ pour $k$ variant de 0 à $N-1$ Chaque point aura donc comme coordonnées sur le cercle $(R\times \cos(k\times \dfrac{2 \pi}{N}),\ R\times \sin(k\times \dfrac{2 \pi}{N}))$

Enfin on relie le point associé à chaque nombre $i$ de 0 à $N-1$ au point associé à $(i \times M )\%\ N$ où $M$ est le nombre dont on veut dessiner la table de multiplication

Par exemple si $N = 652$ et $M = 13$, à un moment on va relier le point associé au nombre $150$ au point associé au nombre $(150 \times 13) \% 652 = 646$ alors que $150 \times 13 = 1950$

Télécharger le squelette suivant rosace.txt, enregistrer avec le nom rosace.py et exécuter le en changeant les valeurs de NB_POINTS et MULTIPLICATEUR

Exercice

Une fonction $f$ est définie sur les nombres à deux chiffres ainsi : Pour calculer l'image de $n$ par $f$, je multiplie les deux chiffres de $n$ pour obtenir un nouveau nombre $m$, si $m \leqslant 9$ je m'arrête, sinon je continue le processus en multipliant les chiffres de $m$ pour obtenir un nouveau nombre
  1. Pourquoi est on sûr que le processus finira par s'arrêter ?
  2. Faire une fonction python produitChiffres(n) qui retourne le produit des deux chiffres de $n$
  3. Utiliser la fonction produitChiffres(n) pour faire une fonction f(n) qui calcule l'image de $n$ par $f$
  4. On veut chercher tous antécédents de $8$ par $f$ de manière "brute": On parcourt tous les nombres à deux chiffres de 11 à 99 et on calcule leur image et si c'est 8 on l'affiche et le comptabilise. Combien y-a-t-il d'antécédents pour 8 ?. Retrouver ce résultat autrement