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 8×6, voici deux pavages possibles.

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

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

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

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

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

Pensez à changer de stratégie !

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

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.

pavagerectangle.py