Formation I.S.N.

Paver un couloir

compter les pavages

On dispose d'un couloir rectangulaire de largeur 2 et de longueur n. On dispose de dalles de largeur 1 et longueur 2. On veut paver le couloir avec les dalles. La question est de connaître le nombre de pavages possible.

On différencie deux dallages par l'orientation des dalles (on suppose les dalles toutes de même couleur, les couleurs ci-dessous sont utilisées pour mieux visualiser les différentes dalles).

Proposer une fonction python récursive dénombrant ces pavages.

Exemple. Les 5 dallages possibles d'un couloir de longueur 4 :
dallages d'un couloir de longueur 4

  • documentation
  • principe
  • un code

On trouvera la doc sur le module turtle ici.

Notons \( u_n \) le nombre de pavages du couloir de longueur \( n \). On a \( u_1=1\) et \(u_2 = 2\).

Pour paver un couloir de longueur \(n\) : on pose les dernières dalles et on est ainsi ramené à paver le début de couloir.

  1. Soit la dernière dalle est verticale et on peut daller de \( u_{n-1}\) façons différentes le début de couloir (de longueur \( n-1 \)).
  2. Soit la dernière dalle est horizontale (et donc en fait les deux dernières dalles) et on peut daller de \( u_{n-2} \) façons différentes le début de couloir (de longueur \(n-2 \)).
  3. Et les pavages cités dans le point 1 sont distincts des pavages du point 2 puisque la dernière dalle est différente dans les deux types de pavage.

On dispose donc maintenant d'un principe de récursion pour construire effectivement le dallage et d'une relation de récurrence pour les compter : \(u_n= u_{n-1}+u_{n-2} \).


def denombre_dallage( longueur_couloir, p1=1, p2=2) :
	if longueur_couloir == 1 : return p1
	elif longueur_couloir == 2 : return p2
	else : return denombre_dallage(longueur_couloir-1, p2, p1+p2)
    
    
print("{} dallage  pour un couloir de longueur {}.".format(denombre_dallage(1), 1))
for i in range(2,10) :
	print("{} dallages différents pour un couloir de longueur {}.".format(denombre_dallage(i), i))

représentation

Écrire ensuite des fonctions permettant de représenter les dallages du couloir avec la tortue.

  • documentation
  • un code

On trouvera la doc sur le module turtle ici.


import turtle as tl
from random import randint


# pour définir les couleurs tortue en rgb :
tl.colormode(255)
# on cache la tortue :
tl.hideturtle()
# tortue rapide :
tl.speed(0)

# on définit une unité pour les dessins :
unite = 20



def dessine_dalle(orientation, coinx, coiny) :
	tl.pensize(2)
	tl.pencolor(255, 255, 255)
	
	
	def dalle() :
		tl.fillcolor(randint(0,255), randint(0,255), randint(0,255))
		tl.begin_fill()
		tl.forward(unite)
		tl.forward(unite)
		tl.left(90)
		tl.forward(unite)
		tl.left(90)
		tl.forward(unite)
		tl.forward(unite)
		tl.left(90)
		tl.forward(unite)
		tl.end_fill()
		
		
	
	if orientation == "H" :
		tl.setheading(0) 
		tl.penup()
		tl.setposition(coinx * unite, coiny * unite)
		tl.pendown()
		dalle()
		tl.setheading(0) 
		tl.penup()
		tl.setposition(coinx * unite, (coiny+1) * unite)
		tl.pendown()
		dalle()
		
	if orientation == "v" :
		tl.setheading(90) 
		tl.penup()
		tl.setposition( (coinx+1)*unite, coiny*unite)
		tl.pendown()
		dalle()

def dallage(longueur_couloir) : 
    """ on crée un 'code' décrivant le dallage.
        v pour une dalle verticale, H pour deux barres horizontales l'une au dessus de l'autre."""
    if longueur_couloir == 1 : return ['v']
    elif longueur_couloir == 2 : return ['vv','H']
    else :
        liste_dallage = []
        for p in dallage(longueur_couloir-1) : liste_dallage.append('v' + p)
        for p in dallage(longueur_couloir-2) : liste_dallage.append('H' + p)
        return liste_dallage


    
def dessine_dallage(longueur_couloir) :
	dallages = dallage(longueur_couloir)
	coinx, coiny = 0, 0
	for D in dallages :
		for orientation in D :
			dessine_dalle(orientation, coinx, coiny)
			if orientation == 'H' : coinx += 2
			else : coinx += 1
		coinx = 0
		coiny -= 3



dessine_dallage(4)
tl.exitonclick()