InfoNu.nl > Wetenschap > Wiskunde > Project Euler: getallenroosters

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.

Lees verder

© 2014 - 2018 Starryheart, het auteursrecht (tenzij anders vermeld) van dit artikel ligt bij de infoteur. Zonder toestemming van de infoteur is vermenigvuldiging verboden.
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…
Wiskunde, een grote mysterie?Wiskunde, een grote mysterie?Wiskunde is een zeer brede richting in de wetenschap. Het is een van de oudste wetenschappen en kan beschouwd worden als…
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…
Bronnen en referenties
  • Euler probleem 11 (vierkant), https://projecteuler.net/problem=11
  • Euler probleem 18 (driehoek), https://projecteuler.net/problem=18

Reageer op het artikel "Project Euler: getallenroosters"

Plaats als eerste een reactie, vraag of opmerking bij dit artikel. Reacties moeten voldoen aan de huisregels van InfoNu.
Meld mij aan voor de tweewekelijkse InfoNu nieuwsbrief
Ik ga akkoord met de privacyverklaring en ben bekend met de inhoud hiervan
Infoteur: Starryheart
Gepubliceerd: 17-06-2014
Rubriek: Wetenschap
Subrubriek: Wiskunde
Special: Project Euler
Bronnen en referenties: 2
Schrijf mee!