Embedded Files
DIVISER POUR REGNER
Puzzle de triominos
On considère un plateau de256(16x16) cases sur lequel une unique case est «inutilisable» ou «coloriée».
On cherche un algorithme permettant de paver le reste du plateau avec des «triominos» en forme de L,
c'est à dire des pièces composées de 3 cases disposées en forme de «L» :
Résoudre ce problème de pavage pour n=256 cases peut se ramener à résoudre quatre sous-problèmes de taille n' = 62cases.
Autrement dit, **on se ramène à résoudre à quatre sous-problèmes de taille quatre fois plus petite** (alors que pour la dichotomie on se ramenait à un seul sous-problème de taille deux fois plus petite).
Pour cela il suffit :
- 1) de positionner un triomino au centre du plateau carré, à cheval sur les trois «sous-carrés» qui ne comportent pas la case «inutilisable» ;
- 2) puis de résoudre les quatres sous-problèmes correspondant à chacun des quatre «sous-carrés» (dans chacun desquels une seule case est «inutilisable»).
En images cela donne :
https://progalgo.fr/basthon-notebook/?from=https://progalgo.fr/3/10_diviser_pour_regner/diviser_pour_regner_00_COURS.ipynb&inline=true
https://progalgo.fr/basthon-notebook/?from=https://progalgo.fr/3/10_diviser_pour_regner/diviser_pour_regner_02_rotation_en_place.ipynb&inline=true
Page updated
Google Sites
Report abuse