Project Euler: getallenroosters

Project Euler: getallenroosters Er zijn enkele opgaven in Project Euler waarin je een rooster met getallen krijgt voorgeschoteld. Daarin moet je dan iets uitrekenen en er zijn dus allerlei bewerkingen nodig, maar hoe pak je dat aan? Hoe 'werkt' een 'vierkant' getallenrooster en bestaan er ook driehoekige? Ongeacht welke vorm je in de uitdagingen tegenkomt, er is altijd een oplossing als je maar weet hoe en waar je moet beginnen.

Inhoudsopgave


Wat is een getallenrooster?

Definitie

Allereerst de definitie van een 'getallenrooster' in Project Euler: een verzameling kolommen en rijen die een bepaalde rangschikking hebben en waarin getallen staan. Dit kan in de vorm van een 'normaal' vierkant zijn, maar ook een driehoek en wie weet in de toekomst zelfs een vijf- of een zeshoek!

Laten we eens kijken naar een simpel voorbeeld van vier kolommen en vier rijen.
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

Richtingen

Als ik je nu zou vragen om vier getallen te vinden in dezelfde richting, die rechtstreeks met elkaar verbonden zijn, welke mogelijkheden zijn er dan?

Ten eerste de vier horizontale rijen: reeksen '1 2 3 4', '5 6 7 8', '9 1 2 3', '4 5 6 7'.
Ten tweede de vier verticale kolommen: reeksen '1 5 9 4', '2 6 1 5', '3 7 2 6', '4 8 3 7'.
Ten derde de twee diagonalen: '1 6 2 7' en '4 1 7 4'.

Je zoekt dus van boven naar beneden, van links naar rechts en diagonaal. Het is net een woordzoeker! Deze regels veranderen niet als het rooster groter wordt. Zo heeft Project Euler probleem 11: largest product in a grid, een veld van twintig bij twintig getallen. Dat wordt een stuk lastiger om met de hand uit te rekenen, nietwaar?

Voorbeeld door middel van een assenstelsel

Transformatie van getallenrooster naar coördinaten

Tijd om dat getallenrooster nog nauwkeuriger te bekijken. Wat zou er gebeuren als je het probleem zou voorstellen als een assenstelsel met coördinaten? Dan wordt de vier linksonder punt (0,0), de één linksboven punt (0,3), de zeven rechtsonder punt (3,3) en de vier rechtsboven punt (3,3).

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

wordt

(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)
(0,0) (1,0) (2,0) (3,0)

Het is handig om een datastructuur (array, vector, enzovoort) toe te passen om de getallen in op te slaan. Bedenk zelf welke voor- en nadelen dat biedt met het oog op grotere getallenroosters. Nu hoef je alleen nog maar de waarde van een coördinaat toe te kennen aan het opgeslagen getal.

Van coördinaten naar code

Hoe gebruik je deze nieuwe informatie? Zodra je een bewerking wilt uitvoeren (vermenigvuldiging, in het geval van Euler probleem 11) op een aantal getallen in dezelfde richting, heb je alleen nog de coördinaten nodig.

Het werkt bijvoorbeeld als volgt:

Horizontaal
Punt linksonder tot en met het vierde getal naar rechts.
(x, y) * (x+1, y) * (x+2, y) * (x+3, y)

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)

(0,0) (1,0) (2,0) (3,0)


Verticaal
Punt linksboven tot en met het vierde getal naar beneden.
(x, y+3) * (x, y+2) * (x, y+1) * (x, y)

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

wordt

(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)
(0,0) (1,0) (2,0) (3,0)

Diagonaal linksboven naar rechtsonder
(x,y+3) * (x+1, y+2) * (x+2, y+1) * (x+3, y)

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

wordt

(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)
(0,0) (1,0) (2,0) (3,0)

Diagonaal linksonder naar rechtsboven
(x,y) * (x+1, y+1) * (x+2, y+2) * (x+3, y+3)

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

wordt

(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)
(0,0) (1,0) (2,0) (3,0)

En zo doorzoek je het hele getallenrooster van links naar rechts, van boven naar beneden en diagonaal totdat je alles hebt uitgerekend.

Andere vormen

Euler probleem 18 heeft de vorm van een driehoek. Dat doet denken aan de driehoek van Pascal! Daarin zijn de getallen op de volgende rij de som van de getallen op de rij daarboven. Toegegeven, het is niet identiek, maar de logica die er inzit kun je toepassen op het driehoekige getallenrooster.

Bijvoorbeeld:
__2__
_2_2_
2_4_2

Stel dat ik wil weten welke route in deze 'piramide' de hoogste uitkomst heeft, dan is dat snel gevonden: 2 van de eerste rij, plus 2 van de tweede rij, plus 4 van de derde rij is 2+2+4 = 8.

Echter, wat als het driehoekige getallenrooster niet uit drie rijen met getallen bestaat, maar uit meer dan duizend? Zou het niet makkelijker zijn om de rijen zodanig te bewerken dat hun aantal vermindert? Door de hoogste getallen uit elke rij bij elkaar op te tellen krijg je het volgende:

We beginnen bij de tweede en de derde rij:
_2_2_
2_4_2

Het maximum van alle getallen in de derde rij is vier. Het maximum van de getallen in de tweede rij is (in dit geval) twee. Tel de gevonden getallen op bij het maximum van rij één (er is maar een getal aanwezig) en je komt ook uit op acht. Zo heb je drie rijen gereduceerd tot één. Herhaal het proces totdat je de laatste rij van de piramide hebt uitgerekend.
© 2014 - 2022 Starryheart, het auteursrecht van dit artikel ligt bij de infoteur. Zonder toestemming is vermenigvuldiging verboden. Per 2021 gaat InfoNu verder als archief, artikelen worden nog maar beperkt geactualiseerd.
Gerelateerde artikelen
Het vermoeden van GoldbachHet vermoeden van GoldbachHet vermoeden van Goldbach is een van de bekendste onopgeloste problemen uit de wiskunde. Het stelt dat "ieder even geta…
Project Euler: probleem 1 tot en met 3Project Euler: probleem 1 tot en met 3Project Euler biedt wiskundige/programmeer hersenkrakers. Probleem 1 tot en met 3 geven een aardig idee wat je kunt verw…
Project Euler: priemgetallenProject Euler: priemgetallenEr zijn een aantal problemen in Project Euler waarin priemgetallen een rol spelen. Soms moet je ze genereren, of je moet…
Iedere vergelijking gaat opIedere vergelijking gaat op. Het tegendeel is ook juist: iedere vergelijking loopt mank. Het is een kwestie van hoe je h…

De vierkleurenstellingDe vierkleurenstellingDe vierkleurenstelling houdt in, dat je een landkaart met oneindig veel landen kunt inkleuren met maar vier kleuren, zon…
Pi-Day - Dag van het oneindige cirkelgetal PiPi-Day - Dag van het oneindige cirkelgetal PiOp 14 maart is het Pi-Dag, π-dag. De dag wordt in Amerika geschreven als 3-14, de driecijferige benadering van `…
Bronnen en referenties
  • Euler probleem 11 (vierkant), https://projecteuler.net/problem=11
  • Euler probleem 18 (driehoek), https://projecteuler.net/problem=18
Starryheart (9 artikelen)
Gepubliceerd: 17-06-2014
Rubriek: Wetenschap
Subrubriek: Wiskunde
Bronnen en referenties: 2
Per 2021 gaat InfoNu verder als archief. Het grote aanbod van artikelen blijft beschikbaar maar er worden geen nieuwe artikelen meer gepubliceerd en nog maar beperkt geactualiseerd, daardoor kunnen artikelen op bepaalde punten verouderd zijn. Reacties plaatsen bij artikelen is niet meer mogelijk.