SPOJ.com - Problem PROG0275

PROG0275 - Zeckendorf representation

The Fibonacci sequence is named after Leonardo of Pisa - nicknamed Fibonacci - who in his book Liber Abaci reported a series in which each element is always equal to the sum of the two preceding elements, starting with 1 and 1. The first elements of the row are thus:

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

The Fibonacci sequence has some very interesting features, and is, among other things, connected to the golden ratio. It is also used in the theorem of Zeckendorf - named after the Belgian doctor, army officer and mathematician Edouard Zeckendorf. The theorem states that any positive integer can be written in a unique way as the sum of one or more numbers in a Fibonacci sequence that do not follow each other. Such a sum is called the Zeckendorf representation of a number. The Zeckendorf representation of the number 100 is

100 = 3 + 8 + 89

Other ways to write the number 100 as a sum of numbers from the Fibonacci sequence are not sufficient. For example, we can write that

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

but these sums respectively have 1-2 and 34-55 as successive pairs of numbers in the Fibonacci sequence.

Algorithm

The Zeckendorf representation of a number $n \in \mathbb{N}_0$ can be easily found on the basis of a so-called greedy search strategy. Start with the largest number $m_1$ from the Fibonacci sequence that is smaller or equal to the integer $n$. Then locate the largest number $m_2$ from the Fibonacci sequence that is less than or equal to the difference $n - m_1$. Keep repeating this process until the difference itself is a number in the Fibonacci sequence.

Assignment

Write a function zeckendorf to which a number $n \in \mathbb{N}_0$ has to be passed as argument. The function must return the Zeckendorf representation of $n$ as a string, where the terms appear in ascending order in the sum.

Example

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

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'

Submit solution!

Added by:	Peter Dawyndt
Date:	2012-08-27
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None

Informatics 1