PYTHON 2.7 FEUILLE D'EXERCICE n° 11 bis Algorithmique janvier 2017.
Thèmes abordés:
• Recherche de tous les diviseurs d'un entier naturel n supérieur ou égal à 2, saisi .
• Recherche de sa primalité éventuelle.
• Tester si deux entiers relatifs a et b saisis sont congrus ou non modulo un
entier naturel m non nul, saisi.
• Trouver en base 6 l'écriture d'un nombre A divisble par 35.
• Trouver le codage d'une lettre en connaissant la clé ( a, b) d'entiers entre
0 et 25 avec a premier avec 26.
• Trouver le codage d'un mot en connaissant la clé ( a, b) d'entiers entre
0 et 25 avec a premier avec 26.
• a étant un entier naturel compris entre 0 et 25 , premier avec 26.
Trouver le plus petit entier naturel non nul n tel que n ×a ≡ 1 [ 26 ]
• Décoder une lettre quand on connait la clé de codage ( a , b ).
• Codage de Caesar( On décale toutes les lettres de la même façon )
--------------------------------------
EXERCICE 1
Ecrire un algorithme qui recherche tous les diviseurs
d'un entier naturel n supérieur ou égal à 2 que l'on a saisi.
REPONSE:
from random import*
def premier():
n=input("Donner un entier naturel non nul autre que 1 ")
L=[]
for i in range( 1,n+1):
if n%i==0:
L.append(i)
print " La liste des diviseurs de ",n,"est :"
print L
if L!=[1,n]:
print n,"n'est pas premier"
else:
print n,"est un nombre premier"
Cela donne :
>>> premier()
Donner un entier naturel non nul autre que 1 13
La liste des diviseurs de 13 est :
[1, 13]
13 est un nombre premier
>>> premier()
Donner un entier naturel non nul autre que 1 48
La liste des diviseurs de 48 est :
[1, 2, 3, 4, 6, 8, 12, 16, 24, 48]
48 n'est pas premier
>>>
--------------------------------------
EXERCICE 2
Ecrire un algorithme qui regarde si deux entiers
relatifs a et b saisis sont congrus modulo un entier naturel m non nul saisi.
REPONSE:
from random import*
def congrus():
a=input(" Donner un entier relatif a : ")
b=input(" Donner un entier relatif b : ")
m=input(" Donner un entier naturel non nul m: ")
if (a-b)%m==0:
print a,"et",b,"sont congrus modulo",m
else:
print a,"et",b," ne sont pas congrus modulo",m
On obtient :
>>> congrus()
Donner un entier relatif a : 15
Donner un entier relatif b : 5
Donner un entier naturel non nul m: 2
15 et 5 sont congrus modulo 2
>>> congrus()
Donner un entier relatif a : 47
Donner un entier relatif b : 15
Donner un entier naturel non nul m: 3
47 et 15 ne sont pas congrus modulo 3
>>>
----------------------------------------
EXERCICE 3
En base 6 on considère l'entier A = 1x5y4 avec x et y dans { 0;1;2;3;4;5}
Donner un algorithme qui indique les couples ( x , y ) s'ils existent tels que A soit divisible par 35.
et qui indique les couples ( x , y ) s'ils existent tels que A soit divisible par 70.
REPONSE:
from random import*
def divbase6():
print " On considère A=1x5y4 en base 6"
L=[]
F=[]
print "Les couples ( x , y ) tels que 35 divise A sont: "
for i in range(0,6):
for j in range(0,6):
A=1480+216*i+6*j
if A%35==0:
L.append(A)
print "(",i,",",j,")"
print "La liste des nombres A=1x5y4 en base 6"
print "divisibles par 35 est: "
print L
print " Les couples ( x , y ) tels que 70 divise A sont: "
for i in range(0,6):
for j in range(0,6):
A=1480+216*i+6*j
if A%70==0:
F.append(A)
print "(",i,",",j,")"
print "La liste des nombres A=1x5y4 en base 6"
print "divisibles par 70 est: "
print F
On obtient:
>>> divbase6()
On considère A=1x5y4 en base 6
Les couples ( x , y ) tels que 35 divise A sont:
( 5 , 5 )
La liste des nombres A=1x5y4 en base 6
divisibles par 35 est:
[2590]
Les couples ( x , y ) tels que 70 divise A sont:
( 5 , 5 )
La liste des nombres A=1x5y4 en base 6
divisibles par 70 est:
[2590]
>>>
----------------------------------------------------
EXERCICE 4
Donner un algo qui demande la lettre à coder et la clé ( a , b ) constituée de deux entiers
compris ente 0 et 25 avec a premier avec 26.
REPONSE:
from random import*
def codag():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
lettre=raw_input("Donner une lettre majuscule ")
x=ALPHA.index(lettre)
a=input("Donner le premier entier a de la clé. Il doit etre compris entre 0 et 25 et premier avec 26 ")
b=input("Donner le second entier b de la clé. Il doit etre compris entre 0 et 25 ")
print " La clé choisie est : ( a , b ) = ( ",a,",",b," ) "
y=a*x+b
r=y%26
print lettre," est codee ",ALPHA[r]
On obtient :
>>> codag()
Donner une lettre majuscule R
Donner le premier entier a de la clé. Il doit etre compris entre 0 et 25 et premier avec 26 7
Donner le second entier b de la clé. Il doit etre compris entre 0 et 25 13
La clé choisie est : ( a , b ) = ( 7 , 13 )
R est codee C
>>>
Explication: Pour R on a x = 17
Donc: y = 17 x + 13 = 132
132 = 5 × 26 + 2 avec 0 ≤ 2 < 26
r = 2 cela correspond à la lettre C.
--------------------------------------------------
EXERCICE 6
Modifier l'algorithme pour qu'il refuse un a qui ne convient pas.
REPONSE:
from random import*
def codag1():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
lettre=raw_input("Donner une lettre majuscule ")
x=ALPHA.index(lettre)
a=input("Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 ")
while a%2==0 or a%13==0 or a%26==0 or a<0 or a>26:
print "Mauvais choix pour a . "
a=input("Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 ")
b=input("Donner le second entier b de la cle. Il doit etre compris entre 0 et 25 ")
print " La cle choisie est : ( a , b ) = ( ",a,",",b," ) "
y=a*x+b
r=y%26
print lettre," est codee ",ALPHA[r]
On obtient:
>>> codag1()
Donner une lettre majuscule R
Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 0
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit ere compris entre 0 et 25 et premier avec 26 27
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit ere compris entre 0 et 25 et premier avec 26 2
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit ere compris entre 0 et 25 et premier avec 26 26
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 5
Donner le second entier b de la cle. Il doit etre compris entre 0 et 25 7
La cle choisie est : ( a , b ) = ( 5 , 7 )
R est codee O
>>>
-----------------------------------
EXERCICE 7
Donner un algorithme qui permet, quand on saisit un mot écrit en majuscule,
de le coder avec une clé ( a , b ) choisie.
REPONSE:
from random import*
def codg():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
mot=raw_input("Donner un mot en majuscules sans espace: ")
a=input("Donner un entier a compris entre 0 et 25 et premier avec 26 ")
b=input("Donner b compris entre 0 et 25 ")
print " La clé choisie est : ( a , b ) = ( ",a,",",b," ) "
for i in range(0,len(mot)):
x=ALPHA.index(mot[i])
y=a*x+b
r=y%26
print ALPHA[r]
On obtient:
>>> codg()
Donner un mot en majuscules sans espace: TABLE
Donner un entier a compris entre 0 et 25 et premier avec 26 7
Donner b compris entre 0 et 25 0
La clé choisie est : ( a , b ) = ( 7 , 0 )
D
A
H
Z
C
>>>
REMARQUE: Pour avoir le mot codé affiché horizontalement
il suffif de mettre une virgule après ALPHA[r] à la fin de l'algo
from random import*
def codg():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
mot=raw_input("Donner un mot en majuscules sans espace: ")
a=input("Donner un entier a compris entre 0 et 25 et premier avec 26 ")
b=input("Donner b compris entre 0 et 25 ")
print " La clé choisie est : ( a , b ) = ( ",a,",",b," ) "
for i in range(0,len(mot)):
x=ALPHA.index(mot[i])
y=a*x+b
r=y%26
print ALPHA[r] ,
On obtient :
>>> codg()
Donner un mot en majuscules sans espace: TABLE
Donner un entier a compris entre 0 et 25 et premier avec 26 7
Donner b compris entre 0 et 25 0
La clé choisie est : ( a , b ) = ( 7 , 0 )
D A H Z C
>>>
------------------------------------
EXERCICE 8
Soit a un entier compris entre 0 et 25 , premier avec 26.
Ecrire un algorithme qui permet de trouver le plus petit entier naturel n non nul
tel que: n × a ≡ 1 [26] ( On se limitera à 100000 pour n )
REPONSE:
from random import*
def recher():
a=input("Donner un entier compris entre 0 et 25, premier avec 26 ")
i=1
while (a*i)%26!=1 and i< 100001:
i=i+1
if i<100000:
print i,"*",a ," est congru à 1 modulo 26"
else:
print "Recherche vaine"
On obtient:
>>> recher()
Donner un entier compris entre 0 et 25, premier avec 26 7
15 * 7 est congru à 1 modulo 26
>>> recher()
Donner un entier compris entre 0 et 25, premier avec 26 9
3 * 9 est congru à 1 modulo 26
>>> recher()
Donner un entier compris entre 0 et 25, premier avec 26 5
21 * 5 est congru à 1 modulo 26
>>> recher()
Donner un entier compris entre 0 et 25, premier avec 26 13
Recherche vaine
>>> recher()
Donner un entier compris entre 0 et 25, premier avec 26 19
11 * 19 est congru à 1 modulo 26
>>>
Remarque : On voit que pour a = 13 on ne trouve pas de n.
13 n'est pas premier avec 26
C'est pourquoi 13 n'est jamais le premier terme de
la clé ( a , b ) de codage
Remarque: Pour a = 19 on trouve n =11
---------------------------------------------------------
EXERCICE 9
Ecrire un algo qui demande la clé ( a , b ) de cryptage et qui
quand on saisit la lettre cryptée , la décrypte.
REPONSE:
from random import*
def decod():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
a=input("Donner un entier a compris entre 0 et 25, PREMIER avec 26: ")
while a%2==0 or a%13==0 or a%26==0 or a<0 or a>26:
print "Mauvais choix pour a . "
a=input("Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 ")
b=input("Donner un entier compris entre 0 et 25 : " )
print "La clé du codage choisie est donc: ( " ,a,",",b,")"
print "On cherche d'abord l'entier n tel que n*",a ,"soit congru à 1 modulo 26"
i=1
while (a*i)%26!=1 and i< 100001:
i=i+1
if i<100000:
print " n = ",i
print i,"*",a ," est congru à 1 modulo 26"
lettre=raw_input("Donner la lettre à décoder: ")
r=ALPHA.index(lettre) # ou encore r=ALPHA.find(lettre)
print "Elle correspond à r = ", r
print " On a : ", a,"*x + ", b ,"congru à ",r, "modulo 26"
print i,"*",a,"* x + ",i,"*",b,"congru à ",i,"*",r, "modulo 26"
print "x est congru à ", i,"*",r,"-", i,"*",b,"modulo 26"
x=( i*r-i*b)%26
print "x = ", x
print " la lettre ", lettre, " se décode en ", ALPHA[x]
Il est possible de supprimer certaines lignes qui
mettent des résultats inutiles pour le profane
Il est possible de prendre pour ALPHA la chaîne "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
On obtient:
>>> decod()
Donner un entier a compris entre 0 et 25, PREMIER avec 26: 19
Donner un entier compris entre 0 et 25 : 21
La clé du codage choisie est donc: ( 19 , 21 )
On cherche d'abord l'entier n tel que n* 19 soit congru à 1 modulo 26
n = 11
11 * 19 est congru à 1 modulo 26
Donner la lettre à décoder: T
Elle correspond à r = 19
On a : 19 *x + 21 congru à 19 modulo 26
11 * 19 * x + 11 * 21 congru à 11 * 19 modulo 26
x est congru à 11 * 19 - 11 * 21 modulo 26
x = 4
la lettre T se décode en E
>>> decod()
Donner un entier a compris entre 0 et 25, PREMIER avec 26: 19
Donner un entier compris entre 0 et 25 : 21
La clé du codage choisie est donc: ( 19 , 21 )
On cherche d'abord l'entier n tel que n* 19 soit congru à 1 modulo 26
n = 11
11 * 19 est congru à 1 modulo 26
Donner la lettre à décoder: L
Elle correspond à r = 11
On a : 19 *x + 21 congru à 11 modulo 26
11 * 19 * x + 11 * 21 congru à 11 * 11 modulo 26
x est congru à 11 * 11 - 11 * 21 modulo 26
x = 20
la lettre L se décode en U
>>> decod()
Donner un entier a compris entre 0 et 25, PREMIER avec 26: 19
Donner un entier compris entre 0 et 25 : 21
La clé du codage choisie est donc: ( 19 , 21 )
On cherche d'abord l'entier n tel que n* 19 soit congru à 1 modulo 26
n = 11
11 * 19 est congru à 1 modulo 26
Donner la lettre à décoder: K
Elle correspond à r = 10
On a : 19 *x + 21 congru à 10 modulo 26
11 * 19 * x + 11 * 21 congru à 11 * 10 modulo 26
x est congru à 11 * 10 - 11 * 21 modulo 26
x = 9
la lettre K se décode en J
>>>
Autre situations quand on se trompe sur a.
>>> decod()
Donner un entier a compris entre 0 et 25, PREMIER avec 26: 8
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 4
Mauvais choix pour a .
Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 3
Donner un entier compris entre 0 et 25 : 0
La clé du codage choisie est donc: ( 3 , 0 )
On cherche d'abord l'entier n tel que n* 3 soit congru à 1 modulo 26
n = 9
9 * 3 est congru à 1 modulo 26
Donner la lettre à décoder: M
Elle correspond à r = 12
On a : 3 *x + 0 congru à 12 modulo 26
9 * 3 * x + 9 * 0 congru à 9 * 12 modulo 26
x est congru à 9 * 12 - 9 * 0 modulo 26
x = 4
la lettre M se décode en E
>>>
--------------------------------------
EXERCICE 10
Donner un algorithme qui permet de décoder un mot codé saisi
quand on saisit la clé de codage ( a , b ) où a et b sont des
entiers entre 0 et 25 et a est premier avec 26
REPONSE:
from random import*
def decod1():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
a=input("Donner un entier a compris entre 0 et 25, PREMIER avec 26: ")
while a%2==0 or a%13==0 or a%26==0 or a<0 or a>26:
print "Mauvais choix pour a . "
a=input("Donner le premier entier a de la cle. Il doit etre compris entre 0 et 25 et premier avec 26 ")
b=input("Donner un entier compris entre 0 et 25 : " )
print "La clé du codage choisie est donc: ( " ,a,",",b,")"
print "On cherche d'abord l'entier n tel que n*",a ,"soit congru à 1 modulo 26"
i=1
while (a*i)%26!=1 and i< 100001:
i=i+1
if i<100000:
print " n = ",i
print i,"*",a ," est congru à 1 modulo 26"
mot=raw_input( "Donner un mot en majuscules sans espace")
print "Le mot se décode : "
for j in range(0,len(mot)):
r=ALPHA.index(mot[j])
x=( i*r-i*b)%26
print ALPHA[x],
On obtient:
>>> decod()
Donner un entier a compris entre 0 et 25, PREMIER avec 26: 7
Donner un entier compris entre 0 et 25 : 0
La clé du codage choisie est donc: ( 7 , 0 )
On cherche d'abord l'entier n tel que n* 7 soit congru à 1 modulo 26
n = 15
15 * 7 est congru à 1 modulo 26
Donner un mot en majuscules sans espace: DAHZC
Le mot se décode :
T A B L E
>>>
-------------------------------------
EXERCICE 11
Ecrire un algorithme qui demande le décalage des lettres
dans l'alphabet afin de coder un mot saisi.
REPONSE:
from random import*
def Caesar():
ALPHA=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
lettre=raw_input("Quelle lettre devient A ? ")
m=ALPHA.index(lettre)
print "Le décalage est de ", m,"lettres"
mot=raw_input("Donner un mot: ")
for k in range(0,len(mot)):
x=ALPHA.index(mot[k])
if x<26-m:
print ALPHA[x+m],
else:
print ALPHA[x-(26-m)],
On obtient:
>>> Caesar()
Quelle lettre devient A ? B
Le décalage est de 1 lettres
Donner un mot: CUBE
D V C F
>>>
On obtient :
>>> Caesar()
Quelle lettre devient A ? D
Le décalage est de 3 lettres
Donner un mot: TABLE
W D E O H
>>>
>>> Caesar()
Quelle lettre devient A ? G
Le décalage est de 6 lettres
Donner un mot: TABLE
Z G H R K
>>>
>>> Caesar()
Quelle lettre devient A ? M
Le décalage est de 12 lettres
Donner un mot: TABLE
F M N X Q
>>>
EXERCICE 12:
AUTRE VARIANTE DE PROGRAMME pour le code CAESAR:
On peut présenter ALPHA comme une chaîne au lieu d'une liste.
De plus, au lieu de demander ce que devient A , ce qui permettait de connaître
le décalage, on peut carrément donner ALPHAdecale qui est l'alphabet décalé.
Ecrire ce programme.
REPONSE:
Par exemple pour un décalage de trois lettres on doit soi-même penser à:
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
On peut proposer:
from random import*
def essai3():
ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ALPHAdecale="DEFGHIJKLMNOPQRSTUVWXYZABC"
mot=raw_input("Donner un mot en majuscules: ")
for i in mot:
n=ALPHA.index(i) # C'est l'indice de i dans ALPHA. On peut dire aussi n=ALPHA.find(i)
print ALPHAdecale[n], # Donne la lettre d'indice i dans ALPHAdecale
On obtient:
>>> essai3()
Donner un mot en majuscules: CARTABLE
F D U W D E O H
>>>
AUTRE VARIANTE
Pour ne pas mettre une virgule à la fin on peut créer la
chaîne vide " " puis concaténer avec chaque lettre qui arrive.
Ainsi on peut considérer:
from random import*
def test4():
ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ALPHAdecale="DEFGHIJKLMNOPQRSTUVWXYZABC"
mot=raw_input("Donner un mot en majuscules: ")
e=""
for i in mot:
n=ALPHA.find(i)
e=e+ALPHAdecale[n]
print e
On obtient:
>>> test4()
Donner un mot en majuscules: MELODIEUX
PHORGLHXA
>>>
EXERCICE 13:
Codage avec un mot clé
On demande un mot cé de deux lettres.
On repète ce mot en dessous des lettres de l'alphabet autant de fois
que l'on peut , ici treize fois . On demande une lettre de l'alphabet d'indice x.
En dessous il y a une lettre de l'alphabet (du mot clé ), d'indice y.
On lui associe le reste entier r dans la division par 26 de la somme x + y
La lettre d'indice r dans l'alphabet est le code.
Ecrire ce programme.
REPONSE:
from random import*
def test4():
ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
motcle=raw_input("Donner un mot clé de 2 lettres en majuscules")
print ALPHA
ALPHAauxiliaire=motcle*13
print ALPHAauxiliaire
mot=raw_input("Donner un mot en majuscules: ")
e=""
for i in mot:
n=ALPHA.find(i)
lettre=ALPHAauxiliaire[n]
d=ALPHA.find(lettre)
k=n+d
w=k%26
e=e+ALPHA[w]
print e
On obtient:
>>> test4()
Donner un mot clé de 2 lettres en majuscules DE
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEDEDEDEDEDEDEDEDEDEDEDEDE
Donner un mot en majuscules: TABLE
XDFPH
>>>
---------------------------------------------