Scholieren.com forum - [WS] Pascal driehoek

Scholieren.com forum (https://forum.scholieren.com/index.php)

- Huiswerkvragen: Exacte vakken (https://forum.scholieren.com/forumdisplay.php?f=17)

- - [WS] Pascal driehoek (https://forum.scholieren.com/showthread.php?t=1662897)

[WS] Pascal driehoek

Ik heb een algorithme nodig waarmee ik makkelijk een bepaalde lijn uit de pascal driehoek krijg.
Nu heb ik wel wat dingen op wikipedia gevonden ((x+y)^n bijvoorbeeld), maar dan moet je dat eerst nog buiten de haakjes halen.
Is er ook een algorithme waarmee je makkelijker een lijn uit die driehoek haalt?
Alvast bedankt :)

PS:
http://en.wikipedia.org/wiki/Pascal's_triangle

Dat staat op die wiki-pagina. Ik weet alleen niet hoe makkelijk je zo'n combinatorische vergelijking codeert.

http://en.wikipedia.org/wiki/Pascal'...individual_row

Van op diezelfde pagina; al geef ik wel toe dat de uitleg nogal vaag is.

Het komt hierop neer: stel je wilt het element op rij R en in kolom K berekenen, dan moet je eerst beginnen met de elementen op rij R en in de kolommen voor K te berekenen. Let er ook op dat je de rijen en kolommen begint te tellen van 0 (en niet vanaf 1!). Stel dat de waarde links van het element dat je wilt hebben de waarde A is; dan is het element dat je wilt hebben gelijk aan:
$A + \frac{(R+1)-K}{K}$ .

Dit kan je natuurlijk blijven herhalen tot je alle elementen hebt. Een kleine vereenvoudiging: een rij zal symmetrisch zijn ten opzichte van het midden van de tabel; dus het eerste en laatste zijn gelijk; tweede en voorlaatste enzovoort. Het komt er dus eigenlijk op neer om het bovenstaand algoritme tot in de helft toe te passen en de rest gewoon in te vullen uit wat je al weet. Hoe je praktisch ziet dat je in het midden zit: als de waarde die je uit die formule haalt, gelijk is aan je vorige of weer kleiner geworden is.

Ik weet wel hoe het werkt.
Ik ben alleen een proggramma aan het schrijven om dat snel op te lossen. Ik heb nu wel een algorithme wat werkt, alleen dat word enorm traag als het de rij hoger wordt wordt. Nu vroeg ik me alleen af of er ook nog andere algorithmes zijn zoals (x+y)^n die wel snel(ler) werken.

Wat bedoel je dan met sneller werken zoals (x+y)^n; die werkt namelijk in dezelfde tijd, tenzij je eerst x+y uitwerkt en dan pas die macht. Als je eerst die macht wilt uitwerken, moet je dus langs die binomiaalcoëfficiënten. Op net dezelfde manier gaat die (x+y)^n ook traag worden voor grote n (juist omdat je die coëfficiënten eerst nodig hebt.

Dingen die je kan toepassen om het sneller te maken is gewoon de expliciete formule gaan gebruiken, maar opletten dat je daar de nodige aanpassingen maakt:
${n \choose k} = \frac{n!}{k! (n-k)!}$ . Dat hoort nu eenmaal ook bij programmeren dat je gaat optimaliseren daarin. Ik geef maar een voorbeeld

(en vermits je geen programmeertaal aangeeft, doe ik maar Python):

Code:

def fac(n):

    product = 1

    for i in range(1,n+1):

        product *= i

    return product



def binom(n,k):

    return fac(n)/(fac(k)*(fac(n-k))

Normaal zou je zelf al moeten merken dat dat niet handig gaat zijn. Het recursieve algoritme dat op WikiPedia gebruikt wordt, zal zo op het eerste gezicht al veel sneller zijn. Mijn best gok is trouwens dat die in O(n/2+1) gaat werken, wat redelijk zuinig is (het algoritme hierboven in O(2n)).

Een versnelling in mijn algoritme hierboven kan je al maken door het wiskundig te gaan bekijken en dan na te gaan waarmee je eigenlijk bezig bent, zodoende kom je op iets dergelijks:

Code:

def product(a,b):

    prod = 1

    for i in range(a,b+1):

        prod *= i

    return prod



def fac(n):

    return product(1,n)



def binom(n,k):

    return product(k+1,n)/fac(k)

Als je hiernaar kijkt, hoe snel hij loopt: O(n). Op net dezelfde manier kan je een symmetrische variant maken die sneller loopt voor kleine waarden van k (vermits bovenstaande beter loopt voor grote waarden van k). Je zou dan eventueel beide algoritmes kunnen combineren (door die looptijd te analyseren, kan je zien voor welke waardes van n i.f.v. k het rendabel is om een van beide te kiezen.

Het wikipedia-algoritme is dus O(n ), en volgens mij vrijwel het meest sneller dat je gaat vinden. Voor grote n (ik denk aan duizend bv.), wordt dat wat trager; al zou dat voor een computer nog geen probleem mogen zijn. Voor een rekenmachine echter, is het een ander paar mouwen; maar daar mag je zeker niet vergeten dat die dingen echt niet snel kunnen rekenen. Maar je kan nu eenmaal niet iets veel vereenvoudigen; op een bepaald moment kom je aan de ondergrens.

Verder bestaan er nog genoeg trucjes om die dingen te doen: stel dat je een programma maakt waar je heel vaak die waardes nodig hebt (voor de faculteit of voor binomiaalcoëfficiënten), dan kan je ook steeds afwegen: hoe veel is mijn dataopslag of geheugengebruik waard tegenover mijn prestaties. Een gekende truc is bv. caching. Dit houdt in dat je eenmaal de hele berekening maakt en dat je het resultaat ergens mooi bijhoudt (in een bestand als je dat vaak nodig hebt; gewoon in het geheugen als het best meevalt). De eerste keer dat die berekening gemaakt zal worden, zal je even lang moeten wachten als normaal; maar elke volgende keer dat je die berekening maakt; krijg je direct je resultaat). Het nadeel natuurlijk is dat je hiermee RAM-geheugen opoffert voor prestaties op rekenkracht.

Om maar een voorbeeld te geven:

Code:

cache = {0: 1, 1: 1}



def fac(n):

    if cache.has_key(n):

        return cache[n]

    else:

        f = n * fac(n-1)

        cache[f] = n

        return f

In dit geval zal het ervoor zorgen dat we steeds pas beginnen tellen bij het hoogste getal waarvan we reeds een faculteit berekend hebben. Dit houdt dus ook in dat als we fac(1000) laten berekenen, hij 1000 resultaten zal bijhouden voor volgend gebruik. Daarop valt natuurlijk te verbeteren (door niet recursief maar in een lus te werken en slechts de gevraagde faculteit zelf te berekenen, of die slechts te berekenen als die maar enkele getallen groter is dan een gekende of slechts faculteit van veelvouden van 10 bij te houden (zodat je met een volle cache O(9) werkt en daarvoor O(n ); natuurlijk met het extra geheugengebruik en wel het gegeven dat je ook eerst die cache moet vullen (wat dus nog steeds zelfde tijdsorde is)).

En bovenstaande Python-code is zonder te testen of zelfs maar de intentie om robuust te zijn (dus negatieve waarden of iets dergelijks en alles kan de soep in lopen). Net zozeer kan het hier of daar wat afgeroomd worden, eventueel wat versneld. Het gaat mij vooral om het concept.

Hartelijk bedankt.
De proggammeertaal die ik gebruik is MSL (mIRC), een interpeter.
Ik zal kijken of ik die python code om kan zetten in MSL (al snap ik er niet erg veel van omdat het er heel wat anders uit ziet dan MSL :p) en of het sneller werkt dan mijn huidige en/of de code korter is.

Nogmaals heel erg bedankt ^^

Post eens de code die je al hebt, dan (niet dat ik MSL ken, maar misschien merk ik al direct wat je verkeerd doet). Vergeet ook niet dat geïnterpreteerde talen voor rekenwerk niet van de snelste zijn (ik snap ook al amper het nut om zoiets in mIRC te integreren).

Die Python omzetten naar MSL, volgens mij zal dat niet zo makkelijk lukken (vermits ik gebruik maak van dictionaries, wat niet in elke taal inzit; ik weet nu ook niet hoe uitgebreid MSL is, maar als dat als simpel scripttaaltje voor mIRC dient, vermoed ik niet dat dat echt geschikt is voor langtijdige opslag van gegevens, zoals je met dergelijke cache wel probeert te doen).

Het hangt echt allemaal af van waarvoor je dit alles wilt gebruiken; als het algoritme van WikiPedia er al lang over doet (voor bv. n = 100), dan is er ofwel iets mis met je code of is die taal gewoon niet geschikt voor grote berekeningen. Want bij n = 100 zou je 101 getallen krijgen, dus 50 berekeningen; wat volgens mij wel op een seconde of 5 (maximaal; zelfs op een oude computer nog ruim geschat, gok ik) gedaan moet zijn.