TD Fonctions
Valeurs réelles d’une suite
def suite(u0):
Soit la suite u(n+1) = sqrt(u(n)-1)
u=u0
étant donné un u0 tq 1<u0<1e10. while u>1:
afficher toutes les valeurs réelles de u=(u-1)**.5
print(u)
cette suite.
suite(float(input("u0:")))
suites adjacentes
# iterative version
Etant donné 2 suites suivantes: def suite(n,u0,v0):
u,v=u0,v0
u(n+1) = sqrt(u(n)*v(n+1)) for i in range(1,n+1):
v = 2*u*v/(u+v)
v(n+1) = 2*u(n)*v(n) / (u(n)+v(n)) u = (u*v)**.5
return u,v
soit u1 et v1 2 réels saisis par l’utilisateur # recursive version
tel que: 0<u1<𝜋 et v1>𝜋. def suiter(n,u,v):
if n==0:
return (u,v)
Calculer u(n), v(n).
return suiter(n-1,(u*(2*u*v/(u+v)))**.5, 2*u*v/(u+v))
print(suite(5,3,4), suiter(5,3,4), suiter(5,3,4) ==
suite(5, 3, 4))
# iterative version
chiffres def chiffres(x):
s=0
p=1
Etant donné un entier x, calculer la while x!=0:
c=x%10
somme et le produit de ses chiffres. s+=c
p*=c
Exemple: x//=10
return s,p
x=1234 => s=10, p = 24
# recursive version
def chiffresr(x):
if x<10:
return x,x
s,p = chiffresr(x//10)
return s + (x%10), p * (x%10)
print(chiffres(1234), chiffresr(1234))
# iterative version
binaire de x def binaire(x):
b=0
i=0
etant donné un entier x, afficher son while x!=0:
b += (x%2)*(10**i)
binaire comme un autre entier qui
i+=1
contient que les chiffres 0 et 1 x//=2
return b
exemple:
# recursive version
x = 29 => b = 1 0 1 1 1 def binairer(x):
if x==0:
return 0
return binairer(x//2)*10 + (x%2)
print(binaire(23), binairer(23))
# iterative version
suite def suite(n,u0,u1):
u,v = u0,u1
soit u0, u1 deux réels > 0 donner par for i in range(1,n+1):
l’utilisateur. u,v = v, u**.5 + v**.5
return u,v
la suite u(n) est définie tq:
# recursive version
u(n+2) = sqrt( u(n+1)) + sqrt(u(n)).
def suiter(n,u,v):
Afficher la valeur de u(n) pour un n if n==0:
donné. return u,v
return suiter(n-1, v, u**.5 + v**.5)
print(suite(15,3,5), suiter(15,3,5))
# iterative version
le nombre e def fexp(n):
s=1
soit la suite k=1
for i in range(1,n+1):
u(n) = 1/0! + 1/1! +½! + ⅓! + … + 1/n! k *=i
s +=1/k
calculer u(n) pour un n donné return s
# recursive version
calculer n pour que abs(u(n)-e)<1e-8 def fexpr(n,i=0, s=1, k=1):
if i==n:
return s
return fexpr(n,i+1, s+1/(k*(i+1)), k*(i+1))
print(fexpr(5), fexp(5))
from math import e
le nombre e def exp_precision (epsilon=1e-8):
u=1
soit la suite i=0
k=1
u(n) = 1/0! + 1/1! +½! + ⅓! + … + 1/n! while abs(u-e)>epsilon:
i +=1
calculer u(n) pour un n donné k *=i
u +=1/k
calculer n pour que abs(u(n)-e)<1e-8 return i
print(fexpr(11), fexp(11), e, exp_precision ())
suite anonyme
def suite(n):
Observer la liste des nombres entiers
u=3
relatifs ci-dessous, for i in range(1,n+1):
if i%2==1:
puis calculer un, sachant u0=3.
u +=5
3 ; 8 ; −16 ; −11 ; 22 ; . . . ; . . . ; −49 else:
u *=-2
return u
for i in range(5):
print(suite(i))
fonction quasi-constante
Afficher E(9/10, 10) def E(u,m):
from math import exp
Afficher E(2/10, 10) def S(u,m):
s=0
Afficher E(1/10, 10) for i in range(1,m+1):
s+=u**i/i
return s
return (1-u)*exp(S(u,m))
for i in range(1,10):
print(E(i/10,10))
Premiers
# une condition necessaire mais pas suffisante
Afficher tous les premiers <= 1e6 qui
pour que a**n - 1
s'écrivent sous forme a**n - 1. # soit premier est que a=2 et n soit aussi
premier.
a et n sont données par l’utilisateur.
# en plus (2**n - 1) < 1e6 => (n <= 21)
def premiers_special ():
for i in range(1,21):
p = 2**i - 1
if premier(i) and premier(p):
print(p)
premiers_special ()
PGCD
# iterative version
calculer le pgcd et ppcm de 2 entiers a
def pgcd(a,b):
et b. while a%b!=0:
a ,b = b,a%b
exemple: return b
a, b = (12, 18) => pgcd=6, ppcm=36 # recursive version
def pgcdr(a,b):
if a%b==0:
return b
return pgcd(b, a%b)
print(pgcd(12,18)==pgcdr(12,18)==6)
Plantes def plantes(A,B):
j=0
while A>B:
Deux plantes grandissent en longueur chaque jour.
A *=2
A: double sa longueur B *=3
j +=1
B: triple sa longueur
return j
initialement, on a A>B.
def plantes_rec (A,B):
Dans combien de jours le la plante B depasse A en
if A<=B:
longueur.
return 0
Exemple: return 1 + plantes(A*2, B*3)
A, B = 2, 1 => j=2
print(plantes_rec (5,1) == plantes(5,1))
exponentiation rapide # recursive version
def exponentiation_rapide_rec (a,n):
if a==0:
etant donné deux entiers a et n, return 0
if n==0:
on veut calculer a**n en utilisant la
return 1
méthode suivante: if n%2==0:
return exponentiation_rapide_rec (a,n//2)**2
return a*exponentiation_rapide_rec (a,n//2)**2
print(exponentiation_rapide (2,53) ==
exponentiation_rapide_rec (2,53) == 2**53)
A Rook in the chess game
The rook is a piece in the game of chess. During
its turn, it may move any non-zero number of
squares horizontally or vertically. Your task is to
find all possible moves for a rook on an empty
chessboard.
Example:
r,c = 5, ‘d’ => d1 d2 b5 g5 h5 d3 e5 f5 d8 a5 d6
d7 c5 d4
A Rook in the chess game - solution
def rook(r,c):
for i in range(1,9):
if i!=r:
print(i,c)
for cc in range(ord('a'), ord('h')+1):
if cc!=ord(c):
print(r,chr(cc))
print(rook(5,'d'))
Resume - Programme / Fonction
Un programme: c’est l’interaction entre plusieurs fonctions en vue de résoudre un
“grand”-problème
Une fonction: c’est une unité de calcul très spécifique pour résoudre un problème
bien spécifique.
Résumé - Définition d’une Fonction
# f(x,y) = x**2 + y**2 # Appel de f
def f(x,y): a,b = 2,3
return x**2+y**2 c = f(a,b)
# minmax(3,2) => (min=2, max=3) # c == 13
# Appel de minmax
def minmax(a,b):
a,b=7,3
if a<b: return a,b
a,b = minmax(a,b)
else: return b,a
# a == 3 ; b==7
Résumé - Valeurs par défauts
def affine(x,a=1,b=0):
return a*x+b
# Appel avec un seul paramètre
y=affine(2) # y==2
# Appel avec 2 paramètres
y=affine(2,.5) # y==1
# Appel avec 3 paramètres
y=affine(2,.5, .25) # y==1.25
Résumé - Porté d’une variable (locale/globale)
Résumé - Fonction lambda
Résumé - Fonction passée en paramètre
Résumé - Fonction lambda
Résumé - Assertion
Résumé - Contexte d'exécution d’une fonction
Résumé - Fonction récursive
