Pascals driehoek en efficiëntie

Dit is een oplossing voor het pascalblok:
Geen Afbeelding

Er zijn twee basisgevallen, het begin en het eind van een rij. De recursieve aanroep berekent de som van twee waardes in de vorige rij.

Geen Afbeelding = Geen Afbeelding + Geen Afbeelding

Je gaat nu uitvinden hoeveel recursieve aanroepen je nodig hebt om een waarde in Pascals Driehoek te berekenen.

    Wat kan je toevoegen aan het blok om dit bij te houden?
  1. Pas je pascalblok aan om bij te houden hoe vaak het blok uitgevoerd wordt.
  2. Hoe vaak wordt het pascalblok aangeroepen wanneer je Geen Afbeelding berekent?
  3. Wat gebeurt er als je Geen Afbeelding aanroept?
Houd bij wat Geen Afbeelding allemaal aanroept om te zien wat overbodig is. Een aanroep is overbodig als die aanroep al een keer gedaan is.

Veel van de recursieve aanroepen zijn overbodig. Geen Afbeelding zal bijvoorbeeld Geen Afbeelding veel aanroepen, om iedere keer dezelfde informatie te vragen.

    Deze techniek heet memoïsatie. Omdat ieder opgeslagen antwoord een soort "memo" is.
  1. Gebruik een lijst om bij te houden welke waardes al berekend zijn, zodat als dezelfde invoer twee keer gegeven wordt, de functie de opgeslagen waarde rapporteert in plaats van weer recursieve aanroepen te doen.
  2. Er is een formule voor pascal die vaak gebruikt wordt:
    3. \text{pascal}(n,r) = \frac{n!}{r!(n-r)!}

    Bouw een versie van pascal die deze formule gebruikt. Vergelijk hoe efficiënt deze nieuwe versie is met de oude, recursieve versie.

Terug Volgende