On dispose d'une planche de longueur n (où n est un entier naturel non nul) et de largeur 2. On dispose
par ailleurs de dalles de longueur 2 et largeur 1.
L'objectif est de paver le couloir avec les dalles.
On veut savoir combien de tels pavages on peut réaliser. On veut également expliciter les divers pavages.
Écrire tout d'abord une fonction python récursive prenant en entrée la longueur n du couloir et donnant en sortie
le nombre de pavages possibles.
Écrire ensuite une fonction python récursive qui donnera explicitement les pavages possibles sous forme d'une liste.
Dans ce premier exercice, la liste sera composée de chaînes de caractères comme décrit ci-dessous sur l'exemple.
Exemple d'un couloir de longueur 4.
On peut paver de 5 façons différentes un couloir de longueur 4 (les couleurs n'ont pas d'importance, ce sont les positions
verticales ou horizontales qui nous importent ici) :
Pavage :
Codage sous forme d'une chaîne :
'hhhh'
'hhV'
'Vhh'
'hVh'
'VV'
h = une dalle horizontale, V = vv deux dalles verticales côte à côte
Le nombre de pavages
Le nombre de pavages d'un couloir de longueur 1 est clairement $$u_1 = 1$$
Le nombre de pavages d'un couloir de longueur 2 est $$u_2 = 2$$
Pavage
Codage
hh
V
Pour paver un couloir de longueur n :
Soit on commence par poser une dalle horizontale et pour compléter, il faut paver le couloir de longueur n-1 restant.
Ce qui peut se faire de \(u_{n-1}\) façons différentes.
Soit on commence par poser deux dalles verticales côte à côte. Pour compléter, il faut paver le couloir de longueur
\(n-2\) restant, ce qui peut se faire de \(u_{n-2}\) façons différentes.
On a donc \(u_1=1\), \(u_2=2\) et \(\forall n\geqslant 2\ u_{n} = u_{n-1}+u_{n-2}\).
def pavage(n) :
if n==1 : return 1
if n==2 : return 2
return pavage(n-1)+pavage(n-2)
def paver(n) :
if n==1 : return ['h']
if n==2 : return ['hh','V']
listepavage=[]
for p in paver(n-1) :
listepavage.append(p+'h')
for p in paver(n-2) :
listepavage.append(p+'V')
return listepavage