PYTHON 2 FEUILLE n° 11 bis D'EXERCICES

         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
>>>  

               ---------------------------------------------