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'
| 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 |
RSS