Veel programmeertaken kunnen op meer dan één manier worden uitgevoerd, maar de ene manier kan veel sneller zijn dan een andere. Snelle programma's ontwerpen is een deel van de kunst en wetenschap van het programmeren van een computer. In deze oefening kijken we naar een aantal voorbeelden.

Deel 1: Bereken niet twee keer hetzelfde

De Rij van Fibonacci is een fascinerende maar ook eenvoudige rij getallen. Begin met twee getallen, 1 en 1. Dan is de regel: om het volgende getal te krijgen tel je de vorige twee op. Het volgende getal is dus 1+1=2. Dan hebben we de eerste drie elementen,

1, 1, 2

en het vierde element is 1+2=3, vervolgens krijgen we 2+3=5, enzovoort:

1, 1, 2, 3, 5, 8, 13, ...

De  Rij van Fibonacci werd aanvankelijk gebruikt om de populatie van konijnen te beschrijven, en het heeft ook fantastische relaties met de architectuur van planten. Hier is een deel van een videoserie over de Rij van Fibonacci:

De definitie van de de Rij van Fibonacci leent zich natuurlijk voor een recursieve functie. In de volgende oefening wordt een functie Fibonacci(n) gedefinieerd die het  nde element levert uit de rij hierboven (te beginnen met n=1).

Volgorde-oefening: Nibofacci

Sleep in dit programma de regels in de juiste volgorde zodat er een recursieve functie ontstaat dat de Rij van Fibonacci oplevert. De grader zal de eerste tien ervan afdrukken.

• return Fibonacci(n-1) + Fibonacci(n-2)
• def Fibonacci(n):
• return 1
• else:
• if (n==1 or n==2):

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Deze recursieve functie wordt echter te langzaam om elementen te berekenen die een eind verderop in  de rij staan. Druk op Test statements invoeren en  type print(Fibonacci(80)). Wanneer je dit test krijg je "Time Limit Exceeded."

Waarom gaat dat zo langzaam? De functie kent geen complexe instructies of loops, alleen maar optellen. Dus moet de traagheid wel gerelateerd zijn aan het aantal keren dat de functie wordt aangeroepen. Wanneer we Fibonacci(3) aanroepen, wordt de functie in totaal drie keer aangeroepen: de begin-aanroep, en dan twee recursieve aanroepen. Wanneer we Fibonacci(4) aanroepen, wordt de recursive functie vijf keer aangeroepen: de begin-aanroep de drie keer die we juist noemden bij n=3, en nog een recursieve aanroep met n=2. Bij het berekenen van Fibonacci(5) gebruiken we in totaal negen aanroepen, en bij Fibonacci(6) zijn er 9+5+1=15 aanroepen. Het aantal aanroepen wordt snel erg groot bij toenemende n!

Als ruwe schatting heeft Fibonacci(n+2) twee maal zoveel aanroepen nodig als Fibonacci(n), want Fibonacci(n+2) roept Fibonacci(n) eenmaal direct aan, en een ander keer indirect via de recursieve aanroep van  Fibonacci(n+1). Dus is de rekentijd evenredig met met een  exponentiële functie tenminste zo groot als (√2)ⁿ. Dit is te langzaam! De aanroep Fibonacci(80) vergt bijvoorbeeld al meer dan  2⁴⁰ = 1099511627776 recursieve aanroepen.

Bovenstaand argument schetst het probleem: Fibonacci(n) twee keer aanroepen en het antwoord erop helemaal opnieuw te berekenen is tijdverspilling. We moeten een nieuwe aanpak verzinnen waarbij we geen tijd verspillen met steeds weer hetzelfde keer op keer te berekenen.

De  oplossing

Laten we proberen iets in Python te schrijven dat meer lijkt op wat we in de inleiding hebben gedaan. We begonnen door 1, 1 op te schrijven. Dan gingen we verder met het uitbreiden van de rij door de laatste twee elementen op te tellen. Hier volgt de code; het is jouw taak om de regels in de juiste volgorde te zetten.

Volgorde-oefening: Fast Fibonacci

Zet de regels, van het programma waarmee snel grote waarden van de Rij van Fibonacci berekend kunnen worden, in de juiste volgorde.

• sequence.append(sequence[i-1] + sequence[i-2])
• def Fibonacci(n):
• return sequence[n]
• for i in range(3, n+1):
• sequence = [0, 1, 1] # Fibonacci(0) is 0, Fibonacci(1) and Fibonacci(2) are 1

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Er is steeds nog wat ruimte voor verbeteringen, omdat bij een nieuwe aanroep het niet nodig is de hele array opnieuw te berekenen, maar het is goed genoeg omdat het snel werkt zelfs bij grote waarden van n!

Deel 2: Bereken geen onnodige dingen

Ons tweede voorbeeld gaat over de test of een getal priem is. Dit is belangrijk voor cryptografie en computerbeveiliging. Een getal is priem wanneer het precies twee delers heeft: 1 en zichzelf. De eerste priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23. (21 bijvoorbeeld is niet priem, omdat het, naast 1 en 21, delers 3 en 7 heeft.)

Hoe kunnen we in Python testen of een getal priem is? We zagen eerder hoe we deelbaarheid kunnen testen:

N % D == 0  # will be True if D is a divisor of N, False otherwise

Door te testen op alle mogelijke delers, komen we tot het volgende programma.

Het werkt! Maar het is te langzaam bij grote getallen. Ga naar Enter input en vul in isItPrime(324635459). Het programma doet er veel te lang over. Wanneer je nog een paar waarden probeert die groter dan 10000000 zijn om na te gaan of die priem zijn, dan zie je dat het programma altijd te weinig tijd heeft, omdat de grader de deelbaarheids-test loop maar 10 miljoen keer per seconde kan uitvoeren. Wanneer we grotere getallen willen testen hebben we een efficiëntere methode nodig. Laten we er voor zorgen dat het programma werkt voor getallen ter grootte van een triljoen (1000000000000)!

Moeten we echt alle getallen testen tussen 2 en N-1, om na te gaan of N priem is? Hint

Het idee, en een redenering

Wanneer je de hint hebt gelezen en hebt geëxperimenteerd, dan zou je hebben kunnen opmerken dat wanneer N niet priem is, het programma meestal een betrekkelijk kleine deler vond in vergelijking tot N. Bijvoorbeeld isItPrime(34827948723948723984729834) wordt tamelijk snel uitgevoerd ondanks dat de input enorm groot is, omdat meteen de deler D=2 gevonden wordt.

Misschien is het helemaal niet nodig om alle mogelijke delers te vinden. Is er een grens aan het aantal delers dat we moeten testen, voordat we er zeker van kunnen zeggen dat N priem is? Gelukkig wel! We kunnen beargumenteren dat als N niet priem is, een van zijn delers ten hoogste sqrt(N) is. Waarom? Als N niet priem is, dan is er een deler A. Omdat A een deler is, betekent dit dat er een ander getal B is zodat

A*B == N

Laten we de argumentatie voortzetten. Als A <= sqrt(N) of B <= sqrt(N), zijn we gelukkig: we hebben dan een deler van N die klein genoeg is zoals we wilden. Maar ze vormen ook de enige mogelijkheid: anders krijgen we een tegenspraak

N = A*B > sqrt(N)*sqrt(N) > N

Mooi! Laten we dan nu dit nieuwe idee in Python implementeren. De gemakkelijkste  weg is om de oude benadering aan te passen is om een test toe te voegen in de for loop: als  D > sqrt(N) (of gelijk daaraan, D*D > N), kunnen we uit de loop stappen en stoppen met testen.

Het programma werkt voor op gigantische priemgetallen!

Slotoefening

In deze oefening combineren we de priemgetallen uit de tweede helft met de lijst-gebaseerde aanpak uit de eerste helft. Je programma moet een tabel vullen van lengte 1000001 zodanig dat isPrime[N] gelijk wordt aan True als N priem is, en False als N dat niet is, voor alle N tot een miljoen. (isPrime[0] en isPrime[1] moeten natuurlijk False aangeven.)

Klik hier voor een hint. Het is een uitgebreide!

Programmeeroefening: Priem klaar voor takeoff

Schrijf een programma dat een tabel definieert in isPrime zoals we boven beschreven (merk op dat isPrime een lijst is, niet een functie). Hint
De grader zal een langer dan gebruikelijke tijdlimiet toestaan om je programma uit te voeren, namelijk 7 seconden. Toch zal gewoon de functie isItPrime uitvoeren niet snel genoeg werken.

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

# verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Help

Dit is de laatste oefening van de CS Circles website. Als je alle lessen hebt doorlopen: gefeliciteerd! Kijk naar de  bronnenpagina's voor suggesties voor vervolgstappen. Veel plezier, veel succes, en programmeer ze!