Project Euler: probleem 1 tot en met 3

Project Euler biedt wiskundige/programmeer hersenkrakers. Probleem 1 tot en met 3 geven een aardig idee wat je kunt verwachten. Zo komen de reeks van Fibonacci en priemfactorisatie voorbij. Een bepaalde volgorde om de Euler problemen te maken is niet verplicht, maar soms is het best handig om gewoon vanaf het begin te beginnen. Iedereen bekijkt zo'n probleem anders. Echter, als je maar niet verder komt kunnen de juiste vragen je op de goede weg helpen om de uitdagingen te voltooien.

Inhoudsopgave

• Euler probleem 1: multiples of 3 and 5
• Euler probleem 2: even Fibonacci numbers
• Euler probleem 3: largest prime factor

Iedereen is anders en heeft een unieke manier om iets op te lossen. Om het plezier van je ontdekkingsreis in project Euler te ondersteunen, kun je een blik werpen op de voorbeeldaanpak per probleem. Er zijn meerdere manieren mogelijk om hetzelfde resultaat te bereiken. De opsomming in pseudocode is er slechts één van.

Euler probleem 1: multiples of 3 and 5

Probleem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Aanpak

Laten we het probleem in stukken verdelen. De eerste twee zinnen vormen de uitleg en geven een voorbeeld inclusief verwachte resultaten voor de aanpak; de laatste zin is de kwestie die je moet oplossen om tot het antwoord te komen.

Je zou de pseudocode voor de hints in het vraagstuk als volgt kunnen opvatten:

1. laat elk getal van een tot en met negen voorbij komen (all the natural numbers below 10)
2. controleer of het getal een veelvoud is van drie of vijf (multiples of 3 or 5, we get 3, 5, 6 and 9)
3. tel alle veelvouden op, het moet uitkomen op 23 (the sum of these multiples is 23)

De vragen die een willekeurig iemand zou kunnen stellen bij Euler probleem 1 zijn bijvoorbeeld:

1. Welke constructie in mijn programmeertaal kan ervoor zorgen dat ik de gewenste getallen doorloop?
2. Wat is een veelvoud?
3. Hoe controleer ik of een getal een veelvoud is?
4. Hoe kan ik vermenigvuldigingen uitvoeren in mijn programmeertaal en welke symbolen gebruik ik daarvoor?
5. Welke plek in mijn broncode is het meest geschikt om alle getallen op te tellen?
6. Als het getal niet 1000 was, maar een miljoen, zou mijn algoritme dan nog steeds redelijk snel zijn?

De vragen die je jezelf stelt variëren op basis van de kennis die je nu bezit over wiskunde en programmeren (en reken er maar op dat je kennis blijft groeien!).

Er zijn geen foute, stomme, of nutteloze vragen. Vragen zorgen er al sinds het begin van de mensheid voor dat er geweldige uitvindingen worden gedaan. Elke vraag is nuttig! Niet alles wat je bedenkt beantwoordt het uiteindelijke probleem, maar het geeft je toch een breder begrip van wat er wordt gevraagd. Dan is het nu tijd om de vragen te beantwoorden die je jezelf hebt gesteld na het lezen van het probleem.

Vraag 1

Hier is één antwoord op mogelijk: een 'loop', maar bedenk wel dat het soort loop een verschil in je uitkomst kan geven ('for'-, 'while'-, 'do while'-, 'if else'-, enzovoort).

Vraag 2 en 3

Hier heb je de basis in rekenkunde nodig: zo is een veelvoud van drie of vijf een getal dat met drie of vijf is vermenigvuldigd. Je zou ook kunnen zeggen dat iets deelbaar is door drie of vijf. Twaalf is een veelvoud van drie, want vier keer drie is twaalf. Twintig is een veelvoud van vijf, want vier keer vijf is twintig.

Vraag 4

De syntax voor delen en vermenigvuldigen hangt af van de programmeertaal die je gebruikt. Sommige talen gebruiken bijvoorbeeld 'div' en 'mod' van 'division' en 'modulus', anderen de tekens '/' of '%' voor delen en '*' voor vermenigvuldigen.

Vraag 5

De plek om de gevonden getallen bij elkaar op te tellen hangt af van de constructie die je in vraag 1 hebt gekozen. Misschien heb je zelfs een compleet andere methode in gedachten.

Vraag 6

Het getal duizend is niet zo groot, dus is de 'brute-force'-methode voor de hand liggend, waarbij je jouw code net zo lang laat draaien op je computer totdat het antwoord is uitgerekend. Echter, bij grotere getallen kan dat al snel een paar minuten duren. Hoe kun je jouw code zodanig aanpassen dat het, in het opzicht van snelheid, ook geschikt wordt voor de berekening van een groter getal?

Euler probleem 2: even Fibonacci numbers

Probleem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Aanpak

Tijd om alles op een rij te zetten en jezelf vragen te stellen:

1. Wat is de reeks van Fibonacci?
2. Hoe zou ik deze reeks kunnen programmeren?
3. Hoe vind ik alle termen die kleiner zijn dan vier miljoen? (terms in the Fibonacci sequence whose values do not exceed four million)
4. Hoe vind ik de even getallen in mijn gevonden reeks? (even-valued terms)

Vraag 1 en 2

De term 'Fibonacci sequence' trekt meteen de aandacht. Je moet eerst weten hoe dat werkt voordat je verder kunt met deze vraag. Gelukkig krijg je een voorbeeld in de uitleg. Als je begint met de getallen een en twee, kun je zelfs uit je hoofd berekenen hoe de reeks verloopt: 55+89=144, 89+144=233, enzovoort.

In elke volgende berekening wordt het eerste getal dus gelijk aan het tweede en het tweede getal wordt de uitkomst van de vorige berekening. Aangezien deze handeling talloze keren nodig is, kun je een recursieve functie overwegen. Recursie houdt in dat een functie zichzelf blijft aanroepen totdat aan een bepaalde voorwaarde is voldaan. Een iteratieve functie doet dit niet.

Vraag 3 en 4

Het is duidelijk dat niet elk getal gewenst is. Dit betekent dat je algoritme een filter nodig heeft. Waar moet je filter dan aan voldoen? Ten eerste worden de termen gevraagd die een waarde hebben onder de vier miljoen, ten tweede heb je de even getallen nodig. Nu is het alleen nog een kwestie van de resultaten optellen.

Euler probleem 3: largest prime factor

Probleem

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Aanpak

Je krijgt een voorbeeld over priemfactorisatie. De vraag die daarop volgt lijkt bedrieglijk simpel.

Een mogelijk stappenplan:

1. Wat is een priemgetal en wat maakt dat zo anders tegenover 'normale' getallen?
2. Wat is priemfactorisatie?
3. Begrijp ik hoe het voorbeeld werkt en kan ik dat reproduceren? (5, 7, 13, 29 als priemfactoren van 13195 verkrijgen)
4. Hoe pas ik mijn code aan zodat het de vraag beantwoordt?

Vraag 1 en 2

Een priemgetal is een getal dat alleen deelbaar is door twee factoren: één en zichzelf. Zeven is bijvoorbeeld priem, omdat het niet gedeeld kan worden door de getallen twee tot en met zes zonder een rest na deling te krijgen. Acht is niet priem, want het is deelbaar door één en zichzelf, maar ook door twee en vier.

Je kunt vervolgens bijna raden wat priemfactorisatie betekent: een getal in priemfactoren ontbinden. Dat houdt in dat je een getal alleen maar door priemgetallen deelt.

Een voorbeeld:

Het resultaat is zelfs te controleren: 2 x 3 x 7 = 42.

Vraag 3

Als je al wist wat de begrippen priemgetal en priemfactorisatie betekenen, kun je meteen aan de slag met het voorbeeld. Neem het getal 13195 en verzin een manier om daar als resultaat 5, 7, 13 en 29 als resultaat uit te krijgen in je code. Gelukt? Mooi, pas het programma aan, want nu heb je alleen nog het grootste resultaat nodig (the largest prime factor).

Vraag 4

Het gevraagde getal (ruim zeshonderd miljard) in priemfactoren ontbinden zorgt, in tegenstelling tot het voorbeeld, ongetwijfeld voor een overflow. Wat kun je daaraan doen? Welke opties biedt jouw programmeertaal daarvoor? Kun je een ander datatype gebruiken? Is het noodzakelijk iets aan het getal te veranderen? Zo ja, welke rekenkundige bewerkingen zijn er dan allemaal mogelijk?

Gefeliciteerd, je hebt de eerste drie uitdagingen opgelost. Als het goed is heb je nu een award verdiend op project Euler! De eerste drie problemen waren zoals het 'abc' van ons alfabet. Ben je er klaar voor om verder te gaan met je ontdekkingsreis?