De rij van Fibonacci is genoemd naar Leonardo van Pisa — bijgenaamd Fibonacci — die in zijn boek Liber abaci melding maakt van een rij waarvan elk element steeds gelijk is aan de som van de twee voorgaande elementen, te beginnen met 1 en 1. De eerste elementen van de rij zijn dus:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …

De rij van Fibonacci beschikt over een aantal zeer interessante eigenschappen, en houdt onder andere verband met de gulden snede. Ze wordt gebruikt in de stelling van Zeckendorf — vernoemd naar de Belgische dokter, legerofficier en wiskundige Edouard Zeckendorf. De stelling zegt dat elk positief geheel getal op een unieke manier kan geschreven worden als de som van één of meer getallen uit de rij van Fibonacci die elkaar niet opvolgen. Een dergelijke som wordt de Zeckendorfrepresentatie van een getal genoemd. De Zeckendorfrepresentatie van het getal 100 is

100 = 3 + 8 + 89

Andere manieren om het getal 100 te schrijven als som van getallen uit de rij van Fibonacci voldoen niet. Zo kunnen we bijvoorbeeld schrijven dat

100 = 1 + 2 + 8 + 89
100 = 3 + 8 + 34 + 55

maar deze sommen hebben respectievelijk 1-2 en 34-55 als opeenvolgende paar getallen uit de rij van Fibonacci.

Algoritme

De Zeckendorfrepresentatie van een getal $$n \in \mathbb{N}_0$$ kan makkelijk gevonden worden aan de hand van een zogenaamde gretige zoekstrategie. Start met het grootste getal $$m_1$$ uit de rij van Fibonacci dat kleiner is of gelijk aan het getal $$n$$. Zoek daarna het grootste getal $$m_2$$ uit de rij van Fibonacci dat kleiner is of gelijk aan het verschil $$n - m_1$$. Blijf dit proces herhalen totdat het verschil uiteindelijk zelf een getal is uit de rij van Fibonacci.

Opgave

Schrijf een functie zeckendorf waaraan een getal $$n \in \mathbb{N}_0$$ als argument moet doorgegeven worden. De functie moet de Zeckendorfrepresentatie van $$n$$ als string teruggeven, waarbij de termen in stijgende volgorde in de som voorkomen.

Voorbeeld

>>> zeckendorf(100)
'3 + 8 + 89'
>>> zeckendorf(848)
'5 + 233 + 610'
>>> zeckendorf(1234)
'1 + 13 + 233 + 987'