Tag archieven: recursieve formules

Functies in Python

Geplaatst op door

Python bezit de mogelijkheid zelf functies te definiëren. Zo kunnen we bijvoorbeeld de kwadraatfunctie definitiëren:

Het  begin van een functie duiden we aan met def , nadien komt de naam en tussen de haakjes staan de argumenten, in dit geval dus gewoon x. Na return komt er wat de functie moet teruggeven. het is ook mogelijk om: meerdere argumenten te geven.  Als je in een programma vaak iets moet berekenen, maak je best een functie voor die berekening.

Je kan in Python zelfs gebruik maken van de functie in de functie zelf! We kunnen bijvoorbeeld gebruik maken van de recursieve relatie van faculteiten om hiervoor een functie te maken:

De functie zal zichzelf aanspreken.Je hebt natuurlijk ook beginwaarden nodig, anders kan je nooit een antwoord geven voor een willekeurige n. Als, zoals in ons voorbeeld, n = 20 zal de functie na 19 keer zichzelf aan te spreken, een 1 teruggeven, en dus eindigen.

Som 28

Geplaatst op door

Op hoeveel manieren N kan je 28  schrijven als som van verschillende natuurlijke getallen ( \neq 0)?

  • Noteer S_k(n) als het aantal mogelijkheden om n te schrijven als som van k verschillende natuurlijke getallen, verschillend van 0.
  • Het is niet zo  moeilijk om S_2(28) uit te rekenen: 1+27,2+26,…13+15. Dus S_2(28)=13.
  • Omdat 1+2+3+4+5+6+7=28 is S_7(28)=1. Bovendien zal voor k>7: S_k(28)=0.
  • Berekenen we eerst S_3(28). Stel dus dat x+y+z=28 en neem x<y<z. Als x>1, dan is x-1,y-1,z-1 een drietal met som 25, dus een mogelijkheid  uit S_3(25). Omgekeerd kan je ook met elke mogelijkheid van S_3(25), een mogelijkheid van S_3(28) laten corresponderen met elementen groter dan 1. 
  • Stel echter dat x=1, dan is  y-1,z-1 een tweetal met som  25 en dus een mogelijkheid uit S_2(25).
  • Uit vorige redeneringen  volgt S_3(28)=S_3(25)+S_2(25) of algemener:

        \[S_3(n)=S_3(n-3)+S_2(n-3)\]

  • Herhaaldelijk toepassen van die formule geeft: S_3(28)=S_2(25)+S_2(22)+S_2(19)+S_2(16)+S_2(13)+S_2(10)+S_2(7)+S_2(4).
  • Maar S_2(n)=\frac{n}{2}-1 als n even is en S_2(n)=\frac{n-1}{2} als n oneven is. Hieruit volgt dat S_3(28)=12+10+9+7+6+4+3+1=52.
  • Om S_4(28) te berekenen gebruiken we een analoge formule S_4(n)=S_3(n-4)+S_2(n-4). Idem voor S_5(28) en S_6(28).
  • Enkele berekingen staan in volgende tabel en zo vinden we

        \[N=13+52+84+57+14+1=221\]