Een strobogrammatisch getal (strobogrammatic number) blijft hetzelfde als je het 180° draait. Zo wordt 69 opnieuw 69: de cijfers wisselen van plaats en de 6 en 9 veranderen in elkaar.
We gebruiken de gebruikelijke afspraak met de cijfers 0, 1, 6, 8 en 9, in een geschikte schrijfwijze. De vorm van de cijfers is dus van belang.
| Cijfer | Na een halve draai |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 6 | 9 |
| 8 | 8 |
| 9 | 6 |
De opdracht
Geef voor een positief geheel getal n alle strobogrammatische getallen met precies n cijfers, in stijgende volgorde. Een getal met meerdere cijfers mag niet met een nul beginnen. Voor n = 1 tellen we 0, 1 en 8 mee.
Van binnen naar buiten
We bouwen de getallen vanuit het midden op. Bij een even aantal cijfers beginnen we met een lege tekst. Bij een oneven aantal beginnen we met 0, 1 of 8: alleen deze cijfers kunnen in het midden staan.
Daarna voegen we links en rechts steeds een passend paar toe: (0, 0), (1, 1), (6, 9), (8, 8) of (9, 6). Het paar (0, 0) mag alleen binnenin voorkomen. Zo wordt bijvoorbeeld het midden 0 met het paar (6, 9) het getal 609.
We bewaren de tussenresultaten als tekst, zodat we cijfers eenvoudig kunnen toevoegen en nullen binnenin behouden. Pas op het einde maken we er gehele getallen van en sorteren we ze.
Python-programma
def strobogrammatische_getallen(n: int) -> list[int]:
"""Geef alle strobogrammatische getallen met precies n cijfers."""
if n < 1:
raise ValueError("n moet minstens 1 zijn.")
paren = [("0", "0"), ("1", "1"), ("6", "9"),
("8", "8"), ("9", "6")]
# Begin in het midden: leeg bij een even aantal cijfers.
if n % 2 == 0:
getallen = [""]
lengte = 0
else:
getallen = ["0", "1", "8"]
lengte = 1
# Voeg telkens een passend cijfer links en rechts toe.
while lengte < n:
nieuwe_getallen = []
for midden in getallen:
for links, rechts in paren:
if lengte + 2 == n and links == "0":
continue # Het volledige getal mag niet met 0 beginnen.
nieuwe_getallen.append(links + midden + rechts)
getallen = nieuwe_getallen
lengte += 2
return sorted(int(getal) for getal in getallen)
for n in (2, 3):
resultaat = strobogrammatische_getallen(n)
print(f"n = {n}: {resultaat}")
print(f"Aantal: {len(resultaat)}")
De functie werkt voor elke positieve gehele n. Met bijvoorbeeld strobogrammatische_getallen(4) krijg je alle oplossingen met vier cijfers. Het aantal oplossingen groeit snel wanneer n groter wordt.
Uitwerking voor n = 2
Er is geen middelste cijfer. De vier toegestane buitenste paren geven:
11, 69, 88, 96
Dat zijn 4 getallen. 00 telt niet mee: het is geen getal met twee cijfers.
Uitwerking voor n = 3
Er zijn vier keuzes voor het buitenste paar en drie voor het middelste cijfer: 0, 1 of 8. We krijgen dus 4 × 3 = 12 getallen:
101, 111, 181, 609, 619, 689, 808, 818, 888, 906, 916, 986
Het programma geeft:
n = 2: [11, 69, 88, 96]
Aantal: 4
n = 3: [101, 111, 181, 609, 619, 689, 808, 818, 888, 906, 916, 986]
Aantal: 12
Ter vergelijking: 609 is strobogrammatisch, maar 666 niet; na een halve draai wordt dat 999.
Bron voor de getallenrij en cijferafspraak: OEIS A000787.