Bord bedekken met blokjes: hoeveel mogelijkheden?

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
Mathematica
Vast lid
Vast lid
Berichten: 41
Lid geworden op: 29 nov 2009, 12:26

Bord bedekken met blokjes: hoeveel mogelijkheden?

Bericht door Mathematica » 11 nov 2011, 11:27

Hi,

Ik zit met een klein probleempje... Ik probeer een "spelbord" van 2xn vakjes op te vullen met blokjes van het formaat 2x1 en 2x2. (draaien van de blokjes is toegelaten). Nu is de vraag: op hoeveel verschillende manieren kan je dit doen?
Als je enkel 2x1 blokjes hebt, is dit probleem niet moeilijk op te lossen: het aantal mogelijkheden volgt de rij van Fibonacci. Als je echter ook 2x2 blokjes krijgt, is het systeem precies een beetje zoek.

Weet er iemand hier welk algoritme erachter zit? Of kan iemand mij een idee geven van hoe ik zoiets kan/zou moeten vinden? Ik heb al geprobeerd het te tekenen en de mogelijkheden te tellen, maar het worden er al vrij snel vrij veel, en dat werkte dus niet.

Mijn Getallen Tot Nu Toe:
bordformaat =
2x1 => 1 mogelijkheid
2x2 => 3 mogelijkheden
2x3 => 5 mogelijkheden
2x4 => 11 mogelijkheden
En verder ben ik al niet meer zeker of ze nog wel kloppen...
(wat betreft het algoritme: afwisselen van "*2,+1" en "*2,-1" werkte niet)

Ik zit echt helemaal vast en ik heb dit nodig voor een programma dat ik aan het schrijven ben... Help?
life is physics, love is chemistry, everything is mathematics...

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Bord bedekken met blokjes: hoeveel mogelijkheden?

Bericht door Sjoerd Job » 11 nov 2011, 11:56

Je kan simpel beginnen:

Stel je hebt een gebied van . Je kan dan op 3 manieren beginnen:
- een blokje.
- twee blokjes boven elkaar.
- een blokje.

In elk van de gevallen moet je je afvragen: hoeveel blijft er over? De formules worden ietwat ingewikkelder dan bij alleen de blokjes, maar het is even goed op te lossen.
``Life is complex. It has real and imaginary parts.''

Plaats reactie