====== Pavage d'un rectangle par des carrés ======

On s'intéresse au problème suivant : étant donné un rectangle dont les dimensions sont des nombres entiers, quel est le nombre minimal de carrés de côté entier nécessaires pour le paver entièrement, sans déborder ?

Par exemple, pour le rectangle de dimensions 8x6, voici deux pavages possibles.

{{ :nsi:premiere:glouton:pavageglouton1.svg |}}

{{ :nsi:premiere:glouton:pavageglouton2.svg |}}

Le second est meilleur puisqu'il ne nécessite que 4 carrés.

==== Question 1 ====

Trouver un pavage de moins de 8 carrés pour le rectangle 18x13

==== Question 2 ====

Trouver un pavage d'exactement 8 carrés pour le rectangle 34x21

==== Question 3 ====

Déterminer une stratégie permettant de paver le rectangle en essayant de minimiser le nombre de carrés.

==== Question 4 ====

Réaliser le pavage du rectangle 13x11 avec 6 carrés.

Pensez à changer de stratégie !

Que peut-en déduire sur la stratégie énoncée en question 3 ?

===== Le code à compléter =====

Nous allons néanmoins poursuivre avec cette stratégie qui est une stratégie **gloutonne**.

On vous propose un script python à compléter ce qui vous permettra d'afficher le pavage.

{{ :nsi:premiere:glouton:pavagerectangle.py |}}