Hoofdstuk 5 Les 3: Tijdexperimenten, Pagina 1

Algoritmes vergelijken

In deze les, ga je leren dat bepaalde manieren sneller een probleem oplossen dan andere.

Op deze pagina, ga je twee algoritmes vergelijken voor het optellen van de getallen van 1 tot een bepaald invoergetal (zoals in de afbeelding hieronder).
Geen Afbeelding

Alex en Bo zijn een algoritme aan het maken dat een positief, heel getal als invoer heeft en de som van alle hele getalle tot dat invoergetal bij elkaar optelt, zoals hier:
Geen Afbeelding

Deze verschillende aanpakken hebben altijd dezelfde uitkomst voor dezelfde invoer. Alex en Bo bespreken hun aanpak:

Alex: Ik heb twee nieuwe blokken gemaakt. Eerst heb ik een rapporteur gemaakt om alle getallen tussen twee getallen in een lijst te zetten, inclusief de 2 getallen, daarna gebruik ik combineer om de lijst op te tellen.

Het Geen Afbeelding blok heeft als invoer een lijst en een operatie (met twee lege invoervakken). Het rapporteert slecht één resultaat (dus niet een lijst): de combinatie van de elementen in de lijst nadat de gegeven operatie is uitgevoerd. Bijvoorbeeld:

Je kan dit lezen als "combineer de elementen van de lijst {5,6,2,3} door op te tellen".

combineer is een functie van hogere orde. Dit betekent dat het een functie is die als invoer een functie heeft. Je hebt al een aantal functies van hogere orde gezien: for each (in Hoofdstuk 2 Les 2), houd (in Hoofdstuk 2 Les 3) en map (in Hoofdstuk 3 Les 1 ).

Jij kiest een operatie en combineer voert die operatie uit door alle items in de invoerlijst te combineren en rapporteert dan de uitkomst.

Merk op dat de functie die gebruikt wordt om de items te combineren altijd twee lege invoervakken heeft. map en houd hadden maar één leeg vak in hun invoerfunctie maar combineer heeft er twee.

In tegenstelling tot map en houd, wordt combineer vooral gebruikt samen met deze vijf functies:
Geen Afbeelding

Voor blokken die je zelf zou schrijven zijn er maar 2 waarschijnlijke kandidaten:
Geen Afbeelding

Waarom zijn het er zo weinig?

De functie moet associatief zijn, wat betekent dat het niet uitmaakt in welke volgorde de items staan; (7 + 8) + 1 is hetzelfde als 7 + (8 + 1), maar (7 − 8) − 1 is niet hetzelfde als 7 − (8 − 1). Dus

is dubbelzinnig.

Alex laat zijn werk zien:
Geen Afbeelding

Bo: Goed gedaan! Ik denk dat het ook op een andere manier kan.

Alex: Cool. Hoe dan?

Bo: Ik zat na te denken over opsommingen en ik bedacht me dat 1 + 13 = 14, 2 + 12 = 14 en 3 + 11 = 14...

Alex: Dus je was aan het tellen tot veertien?

Bo: Ja, ik schreef de lijst van 1 tot 13 en toen schreef ik dezelfde getallen in omgekeerde volgorde, onder de eerste lijst zoals dit:

Bo schrijft op het bord:

Bo: Toen somde ik op naar beneden en kreeg ik 13 veertiens:

Bo: En 13 keer 14 is 182...

Alex: Maar het antwoord is 91.

Bo: Precies. Ik heb ieder getal dubbel opgeteld dus het antwoord is de helft van 182, wat 91 is.

Bo schrijft

\frac{13 \times 14}{2}

=91

Alex: Oh, en als je de getallen van 1 tot 50 wil optellen dan vermenigvuldig je 50 en 51 en deel je dat door 2 zodat je (Alex rekent) 1275 krijgt.

Alex schrijft

\frac{50 \times 51}{2}

=1275

Bo: (glimlacht) Dus om alle getalen tussen 1 en een ander getal n op te tellen vermenigvuldig je het invoergetal met het invoergetal + 1 en dan deel je de uitkomst door 2...

Bo schrijft

\frac{n \times (n + 1)}{2}

.
Dan bouwt Bo het blok en Alex helpt met debuggen.

Bespreek deze twee algoritmes en stel een hypothese op: Welk algoritme denk je dat efficiënter is? Waarom?
Gebruik voor Alex’s methode, het blok numbers from () tot () in het Variabelenpalet.
Implementeer een som-van-1-tot-algoritme. Je kan Alex' methode gebruiken (met gebruik van combineer), je kan Bo's formule gebruiken of je kan het op je eigen manier doen.

"H5L3-RapporteurTimer"
Werk met een ander team om Alex' en Bo's algoritmes te vergelijken met een groot aantal invoeren. Bepaal welke efficiënter is (welke is sneller).
In de vorige stap heb je met experimenten bepaald welk algoritme sneller is. Je kan dit ook doen door logisch te redeneren om te bewijzen dat het ene algoritme sneller is dan het andere:
1. Als je de getallen van 1 tot 100 optelt, hoeveel rekenkundige operaties (+, –, ×, ÷) zal je dan nodig hebben om Bo's algoritme uit te voeren?
2. Hoeveel rekenkundige operaties zal Alex' methode gebruiken?
3. En als je de getallen van 1 tot 1000 optelt?
4. Zijn de aantallen operaties logisch als je ze vergelijkt met de uitkomsten van de experimenten van de vorige stap?

Als je een diagram-app maakt, probeer dan $y=$ som van 1 tot ( $x$ ) te plotten.