2.5. Quelques exemples#
2.5.1. Factorielle de \(n\) (notée \(n!\))#
On définit $\( \left\{\begin{array}{l} 0! = 1 \\ n! = n\times (n-1)! \end{array} \right. \)$
Show code cell content
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1)
factorielle(7)
5040
2.5.2. PGCD de \(a\) et \(b\)#
On peut remarquer que pgcd(a,b)= pgcd(b, b - a) et même que pgcd(a,b) = pgcd(b, reste(a,b)).
Show code cell content
def pgcd(a,b):
r = a % b
if r == 0:
return b
else:
return pgcd(b,r)
pgcd(2,3)
1
pgcd(27,81)
27
2.5.3. Retourner une chaîne de caractère#
On veut renverser l’ordre des lettres d’une chaîne de caractères.
Show code cell content
def renverse(chaine):
if len(chaine) == 1:
return chaine
else:
return renverse(chaine[1:]) + chaine[0]
assert renverse('robert') == 'trebor'
assert renverse('noel') == 'leon'
2.5.4. Décomposition d’un entier en une somme d’entiers#
On cherche à décomposer un entier en une somme d’entiers :
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 2 + 1 + 1
4 = 1 + 2 + 1
…
Show code cell content
def decompose(n, decompo_actuelle = None):
if decompo_actuelle is None:
decompo_actuelle = []
if n == 0:
return [decompo_actuelle]
else:
decompositions = []
for i in range(1, n+1):
nouvelle_decompo = decompo_actuelle + [i]
decompositions += decompose(n-i, nouvelle_decompo)
return decompositions
decompose(4)
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
2.5.5. Permutations d’une liste#
Donner toutes les permutations d’une liste.
Show code cell content
def calculer_permutations(liste):
if len(liste) == 0:
return [[]]
permutations = []
for indice in range(len(liste)):
element = liste[indice]
reste = liste[:indice] + liste[indice+1:]
permutations_reste= calculer_permutations(reste)
for perm in permutations_reste:
perm.insert(0, element)
permutations.append(perm)
return permutations
calculer_permutations([1,2,3,4,5])
[[1, 2, 3, 4, 5],
[1, 2, 3, 5, 4],
[1, 2, 4, 3, 5],
[1, 2, 4, 5, 3],
[1, 2, 5, 3, 4],
[1, 2, 5, 4, 3],
[1, 3, 2, 4, 5],
[1, 3, 2, 5, 4],
[1, 3, 4, 2, 5],
[1, 3, 4, 5, 2],
[1, 3, 5, 2, 4],
[1, 3, 5, 4, 2],
[1, 4, 2, 3, 5],
[1, 4, 2, 5, 3],
[1, 4, 3, 2, 5],
[1, 4, 3, 5, 2],
[1, 4, 5, 2, 3],
[1, 4, 5, 3, 2],
[1, 5, 2, 3, 4],
[1, 5, 2, 4, 3],
[1, 5, 3, 2, 4],
[1, 5, 3, 4, 2],
[1, 5, 4, 2, 3],
[1, 5, 4, 3, 2],
[2, 1, 3, 4, 5],
[2, 1, 3, 5, 4],
[2, 1, 4, 3, 5],
[2, 1, 4, 5, 3],
[2, 1, 5, 3, 4],
[2, 1, 5, 4, 3],
[2, 3, 1, 4, 5],
[2, 3, 1, 5, 4],
[2, 3, 4, 1, 5],
[2, 3, 4, 5, 1],
[2, 3, 5, 1, 4],
[2, 3, 5, 4, 1],
[2, 4, 1, 3, 5],
[2, 4, 1, 5, 3],
[2, 4, 3, 1, 5],
[2, 4, 3, 5, 1],
[2, 4, 5, 1, 3],
[2, 4, 5, 3, 1],
[2, 5, 1, 3, 4],
[2, 5, 1, 4, 3],
[2, 5, 3, 1, 4],
[2, 5, 3, 4, 1],
[2, 5, 4, 1, 3],
[2, 5, 4, 3, 1],
[3, 1, 2, 4, 5],
[3, 1, 2, 5, 4],
[3, 1, 4, 2, 5],
[3, 1, 4, 5, 2],
[3, 1, 5, 2, 4],
[3, 1, 5, 4, 2],
[3, 2, 1, 4, 5],
[3, 2, 1, 5, 4],
[3, 2, 4, 1, 5],
[3, 2, 4, 5, 1],
[3, 2, 5, 1, 4],
[3, 2, 5, 4, 1],
[3, 4, 1, 2, 5],
[3, 4, 1, 5, 2],
[3, 4, 2, 1, 5],
[3, 4, 2, 5, 1],
[3, 4, 5, 1, 2],
[3, 4, 5, 2, 1],
[3, 5, 1, 2, 4],
[3, 5, 1, 4, 2],
[3, 5, 2, 1, 4],
[3, 5, 2, 4, 1],
[3, 5, 4, 1, 2],
[3, 5, 4, 2, 1],
[4, 1, 2, 3, 5],
[4, 1, 2, 5, 3],
[4, 1, 3, 2, 5],
[4, 1, 3, 5, 2],
[4, 1, 5, 2, 3],
[4, 1, 5, 3, 2],
[4, 2, 1, 3, 5],
[4, 2, 1, 5, 3],
[4, 2, 3, 1, 5],
[4, 2, 3, 5, 1],
[4, 2, 5, 1, 3],
[4, 2, 5, 3, 1],
[4, 3, 1, 2, 5],
[4, 3, 1, 5, 2],
[4, 3, 2, 1, 5],
[4, 3, 2, 5, 1],
[4, 3, 5, 1, 2],
[4, 3, 5, 2, 1],
[4, 5, 1, 2, 3],
[4, 5, 1, 3, 2],
[4, 5, 2, 1, 3],
[4, 5, 2, 3, 1],
[4, 5, 3, 1, 2],
[4, 5, 3, 2, 1],
[5, 1, 2, 3, 4],
[5, 1, 2, 4, 3],
[5, 1, 3, 2, 4],
[5, 1, 3, 4, 2],
[5, 1, 4, 2, 3],
[5, 1, 4, 3, 2],
[5, 2, 1, 3, 4],
[5, 2, 1, 4, 3],
[5, 2, 3, 1, 4],
[5, 2, 3, 4, 1],
[5, 2, 4, 1, 3],
[5, 2, 4, 3, 1],
[5, 3, 1, 2, 4],
[5, 3, 1, 4, 2],
[5, 3, 2, 1, 4],
[5, 3, 2, 4, 1],
[5, 3, 4, 1, 2],
[5, 3, 4, 2, 1],
[5, 4, 1, 2, 3],
[5, 4, 1, 3, 2],
[5, 4, 2, 1, 3],
[5, 4, 2, 3, 1],
[5, 4, 3, 1, 2],
[5, 4, 3, 2, 1]]
2.5.6. Récurrence double : l’exemple des coefficients binomiaux#
On définit le nombre de combinaisons de \(p\) parmi \(n\) par \(\binom{n}{p} = \frac{n!}{p!(n-p)!}\).
On peut démontrer que $\( \binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p} \)$
Écrire une fonction qui calcule les nombres de combinaisons.
Show code cell content
def combinaison(n,p):
if n < 0 or p < 0:
return 0
elif n == 0 and p == 0:
return 1
elif n == 0 and p == 1:
return p
else:
return combinaison(n-1, p-1) + combinaison(n-1,p)
combinaison(5,3)
20