Recursieformule bij rijen van de cijfers 0, 1 en 2

wij moeten een opdracht uitvoeren waarbij wij recursfie formules moeten geven bij een aantal rijen.
met de cijfers 0,1 en 2 moeten we rijtjes maken van verschillende lengte.
lengte 1: 0 1 2
lengte 2: 00 01 02 10 11 12 20 21 22
lengte 3: 000 001 002 111 112 122 120 enz.

nu moeten we dus kijken veel verschillende mogelijkheden je hebt bij een rijtje van lengte 20. met de rij van fibonnaci dachten wij dat er dan 17711 uit moest komen. maar klopt dit zo of moet je dit berekenen ?

nu het grootste probleem. bij een rijtje van lengte 20 mogen er geen 2 enen achter elkaar staan en wij moeten dus kijken hoeveel mogelijkheden je dan hebt. hoe kun je zoiets berekenen ?

07015
Leerling bovenbouw havo-vwo - maandag 29 mei 2006

Antwoord

Bij gebrek aan reactie op mijn bijkomende vraag, enkel een hint:

Stel dat je het aantal rijen waarin geen 2 enen achter elkaar staan kent voor lengtes tot en met lengte n en noem die aantallen a(i), met i=1,2,...n
Probeer nu het aantal dergelijke rijen van lengte n+1, dus a(n+1), daarmee in verband te brengen. Splits daartoe die bewuste rijen op in

0 + een rij van lengte n
1 + een rij van lengte n
2 + een rij van lengte n

Kan je hieruit een recursieve betrekking vinden die a(n+1) uitdrukt in termen van reeds gekende a-waarden?

zaterdag 3 juni 2006

©2001-2024 WisFaq