Exercice type 7 - 2014

# -*- coding: utf-8 -*-
# Katia Barré - Lycée Lesage Vannes

#--- question 1 ----------------------------------------------------------------
print
('\n --- Question 1 --- ')

ord_a = ord('a')
lettres
= ''

for i in range(ord_a, ord_a + 26):
   
lettres += chr(i)
# ou bien : lettres = ''.join([chr(ord_a + i) for i in range(26)])

print
(lettres)

#--- question 2 ----------------------------------------------------------------
print
('\n --- Question 2 --- ')

def decalage(n):
   
"""

    n : entier
    Renvoie l'alphabet après décalage de n vers la gauche

   
"""
   
global lettres
    decale
= ''
   
for i in range(26):
        decale
+= lettres[(i + n) % 26]
   
return decale

    # ou bien :
   
# global ord_a
   
# return ''.join([chr(ord_a + (i + n) % 26) for i in range(26)])

for i in [1, 3]:
   
print('decalage({}) = {}'.format(i, decalage(i)))

#--- question 3 ----------------------------------------------------------------
print
('\n --- Question 3 --- ')

def indices(x, phrase):
   
"""

    x : caractère
    phrase : chaîne de caractères
    Retourne la liste des indices de x dans la phrase (vide si x n'y figure pas)

   
"""
    ind
= []
    long
= len(phrase)
   
for i in range(long):
       
if phrase[i] == x:
            ind
.append(i)
   
return ind

ee, pphrase = 'e', "phrase originale avec des e "
print
('indices({}, "{}") = '.format(ee, pphrase), indices(ee, pphrase))
yy
= 'y'
print
('indices({}, "{}") = '.format(yy, pphrase), indices(yy, pphrase))

#--- question 4 ----------------------------------------------------------------
print
('\n --- Question 4 --- ')

def codage(n, phrase):
   
"""

    n : entier
    phrase : chaîne de caractères
    Renvoie la chaîne phrase codée avec un décalage de n lettres

   
"""
   
global ord_a
   
if n % 26 == 0:
       
return phrase
   
else:
        long
= len(phrase)
       
lettre_codee = ''
       
for lettre in phrase:
            lettre_codee
+= chr(ord_a + (ord(lettre) - ord_a + n) % 26))
       
return lettre_codee

print("codage(3, 'oralensam') : ", codage(3, 'oralensam'), '\n')

#---- seconde idée : usage d'un dictionnaire

def dico(n):
   
global ord_a
   
return {chr(ord_a + i) : chr(ord_a + (i + n) % 26) for i in range(26)}

print('dico(0) = ', dico(0))
print
('dico(3) = ', dico(3), '\n')

def codage_dico(n, phrase):
   
"""

    n : entier
    phrase : chaîne de caractères
    Renvoie la chaîne phrase codée avec un décalage de n lettres

   
"""
   
if n % 26 == 0:
       
return phrase
   
else:
        dico_n
= dico(n)
       
return ''.join(dico_n[lettre] for lettre in phrase)

 
print
("codage_dico(3, 'oralensam') : ", codage_dico(3, 'oralensam'))

#--- question 5 ----------------------------------------------------------------
print
('\n --- Question 5 --- ')
print
('Pour décoder un mot codé de décalage n, il suffit d\'appliquer un décalage de -n (ou de 26-n, ...)')

print("codage(-3, codage(3, 'oralensam')): ", codage(-3, codage(3, 'oralensam')))

 

--- Question 1 ---

abcdefghijklmnopqrstuvwxyz

 

 --- Question 2 ---

decalage(1) = bcdefghijklmnopqrstuvwxyza
decalage(3) = defghijklmnopqrstuvwxyzabc

 --- Question 3 ---

indices(e, "phrase originale avec des e ") =  [5, 15, 19, 23, 26]
indices(y, "phrase originale avec des e ") =  []

 --- Question 4 ---

codage(3, 'oralensam') :  rudohqvdp
dico(0) =  {'c': 'c', 'b': 'b', 'a': 'a', 'g': 'g', 'f': 'f', 'e': 'e', 'd': 'd', 'k': 'k', 'j': 'j', 'i': 'i', 'h': 'h', 'o': 'o', 'n': 'n', 'm': 'm', 'l': 'l', 's': 's', 'r': 'r', 'q': 'q', 'p': 'p', 'w': 'w', 'v': 'v', 'u': 'u', 't': 't', 'z': 'z', 'y': 'y', 'x': 'x'}
dico(3) =  {'c': 'f', 'b': 'e', 'a': 'd', 'g': 'j', 'f': 'i', 'e': 'h', 'd': 'g', 'k': 'n', 'j': 'm', 'i': 'l', 'h': 'k', 'o': 'r', 'n': 'q', 'm': 'p', 'l': 'o', 's': 'v', 'r': 'u', 'q': 't', 'p': 's', 'w': 'z', 'v': 'y', 'u': 'x', 't': 'w', 'z': 'c', 'y': 'b', 'x': 'a'}

codage_dico(3, 'oralensam') :  rudohqvdp

 --- Question 5 ---

Pour décoder un mot codé de décalage n, il suffit d'appliquer un décalage de -n (ou de 26-n, ...)
codage(-3, codage(3, 'oralensam')):  oralensam
codage(23, codage(3, 'oralensam')):  oralensam

Exercice type 6 - 2014

# -*- coding: utf-8 -*-
# Katia Barré - Lycée Lesage Vannes

#--- question 1 ----------------------------------------------------------------
print
('\n --- Question 1 --- ')

print('La fonction d retourne la liste croissante des diviseurs de l\'entier n')

def d(n):
   
"""

    n : entier naturel non nul
    Renvoie la liste croissante des diviseurs de l\'entier n

   
"""
    L
= [1]
   
for nombre in range(2, n+1):
       
if n % nombre == 0:
            L
.append(nombre)
   
return L


for n in [4, 9, 10, 11]:
   
print('d({}) = {}'.format(n, d(n)))

#--- question 2 ----------------------------------------------------------------
print
('\n --- Question 2 --- ')

def DNT(n):
   
"""

    n : entier naturel non nul
    Renvoie la liste croissante des diviseurs "non-trivaux" de l\'entier n

   
"""
    L
= []
   
for nombre in range(2, n):
       
if n % nombre == 0:
            L
.append(nombre)
   
return L
   
# ou bien : return d(n)[1:-1]

 
for
n in [4, 9, 10, 11]:
   
print('DNT({}) = {}'.format(n, DNT(n)))

#--- question 3 ----------------------------------------------------------------
print
('\n --- Question 3 --- ')

def sommeCarresDNT(n):
   
"""

    n : entier naturel non nul
    Renvoie la somme des carrés des diviseurs "non-trivaux" de l\'entier n

   
"""
    s
= 0
   
for nombre in range(2, n):
       
if n % nombre == 0:
            s
+= nombre**2
   
return s

for n in [4, 9, 10, 11]:
   
print('sommeCarresDNT({}) = {}'.format(n, sommeCarresDNT(n)))

#--- question 4 ----------------------------------------------------------------
print
('\n --- Question 4 --- ')

maxi = 1000
print
('Les nombres <= et="" gaux="" la="" somme="" de="" leurs="" br="">diviseurs non triviaux sont :'.format(maxi))
for
i in range(2, maxi + 1):
   
if i == sommeCarresDNT(i):
       
print(i, end = ', ')

print('\n\nOn peut conjecturer, à la lecture de cette liste,\
que les nombres égaux à la somme de leurs diviseurs non triviaux sont\

les carrés des nombres premiers.')

 

--- Question 1 ---

La fonction d retourne la liste croissante des diviseurs de l'entier n
d(4) = [1, 2, 4]
d(9) = [1, 3, 9]
d(10) = [1, 2, 5, 10]
d(11) = [1, 11]

 --- Question 2 ---

DNT(4) = [2]
DNT(9) = [3]
DNT(10) = [2, 5]
DNT(11) = []

--- Question 3 ---

sommeCarresDNT(4) = 4
sommeCarresDNT(9) = 9
sommeCarresDNT(10) = 29
sommeCarresDNT(11) = 0

 --- Question 4 ---

Les nombres <= 1000="" et="" gaux="" la="" somme="" de="" leurs="" diviseurs="" non="" triviaux="" sont="" :="" br="">4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961,

On peut conjecturer, à la lecture de cette liste, que les nombres égaux à la somme de leurs diviseurs non triviaux sont les carrés des nombres premiers.

Exercice type 5 - 2014

# -*- coding: utf-8 -*-
# Katia Barré  - Lycée Lesage Vannes

import numpy as np
import
matplotlib.pyplot as plt
import
scipy.optimize as spo

#--- question 1 ----------------------------------------------------------------
print
('\n --- Question 1 --- ')

def g(x):
   
if (x >= 0) and (x < 1):
       
return x
   
elif (x >= 1) and (x < 2):
       
return 1

g_v = np.vectorize(g)

lx = np.arange(0, 1.99, 0.01)
gx
= g_v(lx)

plt.figure(1)
plt
.plot(lx, gx)
plt
.xlabel('$x$')
plt
.ylabel('$g(x)$')
plt
.axis([-0.1, 2.1, -0.1, 1.1])
plt
.title('Graphe de $g$')
plt
.grid()
plt
.show()

#--- question 2 ----------------------------------------------------------------
print
('\n --- Question 2 --- ')

def f(x):
   
if (x >=0) and (x < 2):
       
return g(x)
   
elif (x >= 2):
       
return (x**0.5) * f(x-2)

f_v = np.vectorize(f)

#--- question 3 ----------------------------------------------------------------
print
('\n --- Question 3 --- ')

lx1 = np.linspace(0, 6, 500)
fx
= f_v(lx1)

plt.figure(2)
plt
.plot(lx1, fx, linestyle = 'None', marker = '.', ms = 3)
plt
.xlabel('$x$')
plt
.ylabel('$f(x)$')
plt
.axis([-0.1, 6.1, -0.1, 5.1])
plt
.title('Graphe de $f$')
plt
.grid()
plt
.show()

#--- question 4 ----------------------------------------------------------------
print
('\n --- Question 4 --- ')

print('On lit graphiquement que alpha est dans [5, 6], intervalle sur lequel f est croissante.')

# --- programmons la méthode de dichotomie

eps = 0.01
a
, b = 5, 6
fa
, fb = f(a), f(b)

while b-a > eps:
    c = (a+b) / 2
    fc
= f(c)
   
if f(c) > 4:
        b
= c
        fb
= fc
   
else :
        a
= c
        fa
= fc

print('Une valeur approchée à {} près de la plus petite valeur alpha > 0\
telle que f(alpha) > 4 est :\n {}\n'
.format(eps, b))

print('f(alpha-{}) = {}, f(alpha) = {}\n\n'.format(eps, f(b - eps), f(b)))
print('(Recherche du zéro de f-4 dans [5, 5.5] par méthode de dichotomie de scipy :')

print(spo.bisect(lambda x : f(x) - 4, 5, 5.5), ').')

--- Question 1 ---

--- Question 2 ---
--- Question 3 ---


--- Question 4 ---

On lit graphiquement que alpha est dans [5, 6], intervalle sur lequel f est croissante.
Une valeur approchée à 0.01 près de la plus petite valeur alpha > 0 telle que f(alpha) > 4 est : 5.125

f(alpha-0.01) = 3.9916443979893805, f(alpha) = 4.001952648395531

(Recherche du zéro de f-4 dans [5, 5.5] par méthode de dichotomie de scipy :
5.123105625617427 ).

 

Exercice type 4 - 2014

# -*- coding: utf-8 -*-

# Katia Barré - Lycée Lesage Vannes

import math as m

import scipy.misc as spm

#--- question 1 ----------------------------------------------------------------

print('\n --- Question 1 --- ')

def Px(k, n, p):

    """

    k : entier naturel

    n : entier naturel >0

    p : float de ]0, 1[

    La v.a.r X suit une loi de Poisson P(n*p)

    Renvoie P(X = k)

    """

    np = n * p

    return (np)**k * m.exp(- np) / m.factorial(k)

n, p = 30, 0.1

lX = [Px(k, n, p) for k in range(n + 1)]

#--- question 2 ----------------------------------------------------------------

print('\n --- Question 2 --- ')

def Py(k, n, p):

    """

    n : entier naturel >0

    k : entier naturel de [0,n]

    p : float de ]0, 1[

    La v.a.r Y suit une loi binomiale B(n, p)

    Renvoie P(Y = k)

    """

    return spm.comb(n, k) * p**k * (1-p)**(n-k)

lY = [Py(k, n, p) for k in range(n + 1)]

print('Listes des P(X=k) et des P(Y=k) pour n = {0}, p = {1}\

et k dans [0, {0}] :\n'.format(n, p))

print(' k | P(X=k)                 | P(Y=k)')

print('-------------------------------------------------')

for k in range(n + 1):

    print('{:>2} | {:<22} | {}'.format(k, lX[k], lY[k]))

#--- question 3 ----------------------------------------------------------------

print('\n --- Question 3 --- ')

def Ecart(n, p):

    """

    n : entier naturel >0

    p : float de ]0, 1[

    La v.a.r. X suit la loi de Poisson P(n*p)

    La v.a.r. Y suit la loi binomiale B(n, p)

    Renvoie le plus grand des nombres |P(Y=k)-P(X=k)| pour k dans [0, n]

    """

    maxi = 0      # contiendra le résultat

    for k in range(n+1):

        distance = abs(Px(k, n, p) - Py(k, n, p))

        if distance > maxi:

            maxi = distance

    return maxi

eps = Ecart(n, p)

print('Ecart({}, {}) = {}'.format(n, p, eps))

#--- question 4 ----------------------------------------------------------------

print('\n --- Question 4 --- ')

def N(e, p):

    """

    e : float > 0

    p : float de ]0,1[

    Renvoie le plus petit entier naturel n > 0 tel que Ecart(n, p) <= e

    """

    n = 1

    while Ecart(n, p) > e:

        n += 1

    return n

print('N(Ecart({0}, {1}), {1}) = {2}'.format(n, p, N(eps, p)))

#--- question 5 ----------------------------------------------------------------

print('\n --- Question 5 --- ')

for (p, e) in [(0.075, 0.008), (0.075, 0.005), (0.1, 0.008)]:

    print('N({}, {}) = {}'.format(e, p, N(e, p)))

print('Dans le cas p = 0.1 et e = 0.005, la réponse du programme\

(à l\'appel de la ligne 19)  est : \n\

"OverflowError: long int too large to convert to float".')

print('Aucune valeur de n telle que n! soit plus petit\

que le plus grand float codable sur 64 bits (n <= 170)\

  ne satisfait Ecart(n, 0.1) < 0.005.')

print('float(m.factorial(170))=',float(m.factorial(170)) )

print('\nCependant, on considère quelquefois que de bonnes conditions\

d\'approximation de B(n,p) par P(n*p)')

print('sont : p <= 0.1, n >= 30 et n * p <= 15.')

print('Pour p = 0.1, il suffirait que n soit dant [30, 150].')

 

--- Question 1 ---

--- Question 2 ---

Listes des P(X=k) et des P(Y=k) pour n = 30, p = 0.1 et k dans [0, 30] :

k | P(X=k)                 | P(Y=k)

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

0 | 0.049787068367863944   | 0.04239115827521624

1 | 0.14936120510359183    | 0.14130386091738778

2 | 0.22404180765538775    | 0.22765622036689948

3 | 0.22404180765538775    | 0.23608793223234328

4 | 0.16803135574154082    | 0.1770659491742562

5 | 0.10081881344492448    | 0.10230477063401491

6 | 0.05040940672246225    | 0.04736331973796974

7 | 0.02160403145248382    | 0.0180431694239884

8 | 0.008101511794681432   | 0.0057637902326629605

9 | 0.002700503931560477   | 0.0015654738903529075

10 | 0.0008101511794681432  | 0.0003652772410823458

11 | 0.00022095032167312998 | 7.379338203683735e-05

12 | 5.5237580418282494e-05 | 1.298216906203625e-05

13 | 1.2747133942680574e-05 | 1.997256778774803e-06

14 | 2.7315287020029804e-06 | 2.694711526918383e-07

15 | 5.46305740400596e-07   | 3.1937321800513934e-08

16 | 1.0243232632511176e-07 | 3.3268043542202017e-09

17 | 1.8076292880902075e-08 | 3.044134703208064e-10

18 | 3.0127154801503463e-09 | 2.4428241445496697e-11

19 | 4.756919179184757e-10  | 1.7142625575787149e-12

20 | 7.135378768777135e-11  | 1.0476048962981064e-13

21 | 1.0193398241110193e-11 | 5.542883049196318e-15

22 | 1.3900088510604809e-12 | 2.5194922950892144e-16

23 | 1.8130550231223663e-13 | 9.737168290199917e-18

24 | 2.266318778902958e-14  | 3.1555637977499687e-19

25 | 2.71958253468355e-15   | 8.414836793999927e-21

26 | 3.1379798477117877e-16 | 1.7980420499999867e-22

27 | 3.48664427523532e-17   | 2.9597400000000102e-24

28 | 3.735690294894985e-18  | 3.523499999999959e-26

29 | 3.864507201615502e-19  | 2.7000000000000107e-28

30 | 3.864507201615502e-20  | 1.0000000000000017e-30

--- Question 3 ---

Ecart(30, 0.1) = 0.01204612457695553

--- Question 4 ---

N(Ecart(30, 0.1), 0.1) = 1

--- Question 5 ---

N(0.008, 0.075) = 1

N(0.005, 0.075) = 124

N(0.008, 0.1) = 71

Dans le cas p = 0.1 et e = 0.005, la réponse du programme (à l'appel de la ligne 19)  est :

"OverflowError: long int too large to convert to float".

Aucune valeur de n telle que n! soit plus petit que le plus grand float codable sur 64 bits (n <= 170="" span="" style="mso-spacerun: yes;" data-mce-style="mso-spacerun: yes;">  ne satisfait Ecart(n, 0.1) < 0.005.

float(m.factorial(170))= 7.257415615307999e+306

Cependant, on considère quelquefois que de bonnes conditions d'approximation de B(n,p) par P(n*p)

sont : p <= 0="" 1="" n="">= 30 et n * p <= 15="" o:p="">

Pour p = 0.1, il suffirait que n soit dant [30, 150].

Exercice type 3 - 2014

# -*- coding: utf-8 -*-
# Katia Barré - Lycée Lesage Vannes

 
#--------------- données de test -----------------------------------------------

t1 = [0,1,1,1,0,0,0,1,0,1,1,0,0,0,0]
print
('t1 = ', t1)
long_t1
= len(t1)

#--- question 1 ----------------------------------------------------------------
print
('\n --- Question 1 --- ')

def nombreZeros(t,i):
   
"""

    t : tableau de 0 et 1
    i : indice du tableau
    renvoie le nombre de 0 consécutifs à partir de t[i] si t[i] = 0
    renvoie 0 sinon

    """

    n = len(t)
   
if t[i]:
       
return 0
   
else:
       
s = 1       # contiendra le résultat
        j
= i+1
       
while (j < n) and (t[j] == 0):
            s
+= 1
            j
+= 1
       
return s

print('                i  | ', end = '')
for
i in range(long_t1):
   
print('{:>2} | '.format(i), end = '')
print
()
print
('nombreZeros(t1, i) | ', end = '')

for i in range(long_t1):
   
print('{:>2} | '.format(nombreZeros(t1, i)), end = '')
print
()

 

#--- question 2 ----------------------------------------------------------------

print('\n --- Question 2 --- ')

print('Le nombre maximal de zéros contigus d\'une liste t de longueur 1 est\
le maximum de la liste des nombreZeros(t,i) pour i dans [0,n-1]\n'
)

def nombreZerosMax(t):
   
"""

    t : liste de 0 et 1
    renvoie le nombre maximal de 0 contigus de t

    """

    n
= len(t)
    maxi
= nombreZeros(t,0)     # contiendra le résultat
   
for i in range(1,n):
        m
= nombreZeros(t,i)
       
if m > maxi :
           
maxi = m
   
return maxi

print('Nombre maximal de 0 contigus de t1 :', nombreZerosMax(t1))

#--- question 3 ----------------------------------------------------------------
print
('\n --- Question 3 --- ')

print('En notant N la longueur du tableau t, \
la complexité de nombreZeros est en O(N) et nombreZerosMax  y fait N appels ;\

la complexité de nombreZerosMax est donc en O(N**2).'
)

#--- question 4 ----------------------------------------------------------------
print
('\n --- Question 4 --- ')

print('Idée : parcourir le tableau une seule fois.')
print
('Si t[z] = 0, alors le premier 0 de la série suivante est au plus tôt')
print
('en t[z + nombreZeros(t, z) + 1].')
print
('Conserver la valeur maximale des nombreZeros calculés.\n')

#--- calcul du nombre maximal de 0 contigus - algorithme linéaire, en O(N) -----
def nombreZerosMax2(t):
   
"""

    t : liste de 0 et 1
    Renvoie le nombre maximal de 0 contigus de t

    """

    n = len(t)
    maxi
= 0                      # contiendra le résultat
   
z = 0
   
while z < n:
       
if t[z]:
           
z += 1                # t[z] = 1 ; on passe à l'indice suivant
       
else:
            m
= nombreZeros(t, z)
           
if m > maxi:
                maxi
= m
            z
+= (m + 1)
           
# t[z] = 0
           
# et t[i] = 0 pour i dans [z, z + m -1]
           
# tandis que t[z + m] = 1
           
# le premier 0 suivant est au plus tôt t[z + m + 1]

    return maxi

print('Nombre maximal de 0 contigus de t1 :', nombreZerosMax2(t1))


t1 =  [0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]

--- Question 1 ---

                i  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14
nombreZeros(t1, i) |  1 |  0 |  0 |  0 |  3 |  2 |  1 |  0 |  1 |  0 |  0 |  4 |  3 |  2 |  1 |

 --- Question 2 ---
Le nombre maximal de zéros contigus d'une liste t de longueur 1 est le maximum de la liste des nombreZeros(t,i) pour i dans [0,n-1]

Nombre maximal de 0 contigus de t1 : 4

--- Question 3 ---

En notant N la longueur du tableau t, la complexité de nombreZeros est en O(N) et nombreZerosMax  y fait N appels ;la complexité de nombreZerosMax est donc en O(N**2).

--- Question 4 ---

Idée : parcourir le tableau une seule fois.
Si t[z] = 0, alors le premier 0 de la série suivante est au plus tôt
en t[z + nombreZeros(t, z) + 1].
Conserver la valeur maximale des nombreZeros calculés.

Nombre maximal de 0 contigus de t1 : 4

Search