Drop hier links of afbeeldingen om ze aan de editor toe te voegen.

Wat zit er verborgen onder de gele balkjes?

Deze afbeelding bevat de kenmerkende gele tekst in het Franklin Gothic lettertype op een zwarte achtergrond met sterren uit de openingsscènes van de Star Wars films. Bovendien herkennen we aan de linkerkant de namen van enkele manen en planeten uit Star Wars.

Deze tips en de titel van de opgave verwijzen naar een getallenrij die vernoemd werd naar de Engelse architect en schrijver Richard Padovan (geboren in 1935). De eerste drie getallen in de rij van Padovan zijn $$P_0 = P_1 = P_2 = 1$$. Elke volgende getal $$P_i$$ ($$i > 2$$) wordt berekend als $$P_i = P_{i-3} + P_{i-2}$$. Dit levert de volgende rij op:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, …

Aan de rechterkant van de afbeelding staan de geheime coördinaten waar de maan of planeet zich verborgen houdt in de rij van Padovan. Hiervoor zetten we de naam van de maan of planeet eerst om naar een codenaam (een reeks cijfers) door

elke letter in de naam te vervangen door zijn positie in het alfabet (A=1, B=2, C=3, …, Z=26)
elk cijfer in de naam te behouden
elk ander karakter weg te laten

Bij deze omzetting wordt geen onderscheid gemaakt tussen hoofdletters en kleine letters. Zo wordt Jedha omgezet naar 105481 (de aaneenschakeling van 10, 5, 4, 8 en 1), D'Qar naar 417118, Yavin 4 naar 251229144 en Vandor-1 naar 22114415181.

Laat ons bijvoorbeeld de eerste regel uit de afbeelding nemen. Daarop staat de naam Jedha die correspondeert met de codenaam 105481. Het eerste getal in de rij van Padovan waarin de cijferreeks 105481 voorkomt, is blijkbaar Padovangetal $$P_{1738}$$ (aangeduid door #1738 in de geheime coördinaten). Dit Padovangetal bestaat uit 213 cijfers (het laatste getal uit de coördinaten) en daarin lezen we de cijferreeks 105481 voor het eerst vanaf positie 94 tot en met positie 99. Hierbij worden de posities van de cijfers in een getal van links naar rechts genummerd vanaf 1. Voor de volledigheid zijn dit alle 213 cijfers van Padovangetal $$P_{1738}$$, waarin we de relevante cijfers aangeduid hebben:

12856476872761368826412337124665816290845154237897141297537926654958720697804863
44210240740411054817800354360406301836700438227598098235590634907743866551613564
61510516579625400073487473896151762076073846053430017

De geheime coördinaten #1738, 94-99 van 213 kunnen met andere woorden samengevat worden als: het getal voorafgegaan door het hekje (#, in dit geval #1738) geeft een bepaald Padovangetal aan (in dit geval $$P_{1738}$$) en de rest van de coördinaten (in dit geval 94-99 van 213) beschrijven welke cijfers uit het Padovangetal moeten gehaald worden om de codenaam te verkrijgen die correspondeert met de naam (in dit geval 105481=Jedha).

Om de vierde regel te ontcijferen (waar het gele balkje de naam verbergt) leveren de coördinaten aan de rechterkant (#10090, 1060-1066 van 1233) de cijferreeks 1512571 op. Hoewel er meerdere namen zijn die met deze codenaam kunnen corresponderen, is er daarvan maar één ook een planeet uit Star Wars — namelijk Olega (15-12-5-7-1).

Om te ontcijferen wat er achter de gele balkjes op de laatste regel staat, is er wat meer puzzelwerk nodig. Maar we verklappen alvast dat daar de naam Kef Bir verborgen zit, waarvan de corresponderende codenaam 11562918 terug te vinden is in Padovangetal $$P_{29772}$$. Dit Padovangetal bestaat uit 3636 cijfers en daarin vinden we de gezochte codenaam voor het eerst terug vanaf positie 1295 tot en met positie 1302. Zo bekomen we de coördinaten #29772, 1295-1302 van 3636.

Opgave

Schrijf een functie padovangetal waaraan een getal $$n \in \mathbb{N}$$ (int) moet doorgegeven worden. De functie moet Padovangetal $$P_n$$ (int) teruggeven.

Tip

De eerste drie Padovangetallen liggen per definitie vast: $$P_0 = P_1 = P_2 = 1$$.

Om Padovangetal $$P_n$$ te berekenen voor $$n > 2$$, moet je ook alle voorgaande Padovangetallen $$P_0, P_1, \ldots, P_{n-1}$$ berekenen. Elk Padovangetal $$P_i$$ wordt immers berekend op basis van twee voorgaande Padovangetallen: $$P_i = P_{i-3} + P_{i-2}$$.

Padovangetal $$P_3$$ wordt berekend op basis van de eerste twee Padovangetallen: $$P_3 = P_0 + P_1$$. Daarvoor heb je Padovangetal $$P_2$$ dus niet nodig. Maar je hebt $$P_2$$ wel nodig om het volgend Padovangetal te kunnen berekenen, want $$P_4 = P_1 + P_2$$.

Je moet dus niet alle voorgaande Padovangetallen bijhouden. Het volstaat om de laatste drie Padovangetallen die berekend werden bij te houden, om daarmee het volgende Padovangetal te kunnen berekenen. Onderstaande video toont stap voor stap hoe Padovangetal $$P_{10}$$ kan berekend worden.
Schrijf een functie cijfers waaraan drie getallen $$n, a, b \in \mathbb{N}$$ (int) moeten doorgegeven worden. De functie moet het getal (int) teruggeven dat gevormd wordt door uit Padovangetal $$P_n$$ de cijfers vanaf positie $$a$$ tot en met positie $$b$$ te halen. Hierbij worden de posities van de cijfers in Padovangetal $$P_n$$ van links naar rechts genummerd vanaf 1.
Schrijf een functie codenaam waaraan een naam (str) moet doorgegeven worden. De functie moet de codenaam (str) teruggeven die correspondeert met de gegeven naam. Bij het bepalen van de codenaam mag geen onderscheid gemaakt worden tussen hoofdletters en kleine letters in de naam.
Schrijf een functie coordinaten waaraan een naam (str) moet doorgegeven worden. De functie moet de geheime coördinaten (str) teruggeven die beschrijven waar de codenaam die correspondeert met de gegeven naam voor het eerst voorkomt in de rij van Padovan.

Tip

Intuïtief zou je misschien geneigd zijn om bij je implementatie van de functie coordinaten de functie padovangetal aan te roepen. Dat zal echter veel te traag zijn. Als je reeds Padovangetallen $$P_1, P_2, \ldots, P_n$$ berekend hebt, gebruik dan een snellere manier om het volgende Padovangetal $$P_{n+1}$$ te berekenen.

Voorbeeld

        >>> padovangetal(10)
12
>>> padovangetal(20)
200
>>> padovangetal(30)
3329
>>> padovangetal(40)
55405

>>> cijfers(1738, 94, 99)
105481
>>> cijfers(3103, 355, 360)
205208
>>> cijfers(4757, 167, 172)
417118
>>> cijfers(10090, 1060, 1066)
1512571

>>> codenaam('Jedha')
'105481'
>>> codenaam("D'Qar")
'417118'
>>> codenaam('Yavin 4')
'251229144'
>>> codenaam('Vandor-1')
'22114415181'

>>> coordinaten('Jedha')
'#1738, 94-99 van 213'
>>> coordinaten('Teth')
'#3103, 355-360 van 379'
>>> coordinaten("D'Qar")
'#4757, 167-172 van 581'
>>> coordinaten('Olega')
'#10090, 1060-1066 van 1233'

Opgave

Tip

Tip

Voorbeeld

Epiloog

Epiloog