Getallen Piramide

als ik het me goed kan herinneren was het zo
(php tags voor indenting)
<?
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
?>
Zien jullie de logica?
Het getal in het midden is elke keer het opgetelde van de 2 erboven.

Jap.
Elke rij uit de piramide kan je als array voorstellen.
Elk getal als een slice.

Voor elke slice uit de volgende laag geld dat de waarde van de slice gelijk is aan de slice op dezelfde positie uit de vorige array, en eentje naar links.

<?
$lagen = 7;
$array[0][0] = 1;
print "1\n<br>";
for ($i=1; $i < $lagen; $i++) {
for ($j=0; $j <= count($array[$i-1]); $j++) {
$array[$i][$j] = $array[$i-1][$j];
// was nodig in perl.. $array[-1] geeft de laatste uit de array weer.. onverachte resultaten.
if (($j-1) >= 0) {
$array[$i][$j] += $array[$i-1][$j-1];
}
}
print join(' ', $array[$i]);
print "\n<br>";
}
?>

Wiskundig gezien kan je dit gebruiken, doordat het de binomenale verdeling weergeeft.

Dit helpt je vaststellen hoeveel mogelijkheden er voor een bepaalde kanssituatie is. Simpel: 6 keer 6 gooien met een dobbelsteen.

Wanneer je je voorsteld dat elke keer dat je gooit met een dobbelsteen je wel of niet 6 gooit. Elke worp betekend een stap naar beneden in de piramide. Elke keer 6 betekent een stap naar links, elke niet-6 een stap naar rechts.

Om na 6 worpen 6 keer een 6 gegooit te hebben, zie je dat je in het hokje met een 1 staat. Een hokje naar rechts zou betekenen 5 keer 6 en één keer niet 6. De waarde van het hokje betekend hoeveel mogelijkheden er zijn om die samenstelling te verkrijgen.

De 6e laag van het binomium is: 1 6 15 20 15 6 1
Dus: 1 mogelijkheid om 6x6, 6 op 5x6, 15 op 4x6, 20 op 3x6, 15 op 2x6, 6 op 1x6 en 1 op 0x6.

De kans is dan het aantal mogelijkheden gedeelt door het aantal mogelijkheden uit de gehele laag, maal de kans op 1 keer 6.

Dus de kans dat iemand 6 keer 6 gooit is 1 / (1+6+15+20+15+6+1) = 1/64 * 1/6

de kan op 5 keer 6 is 6/64 * 1/6.

Uw wiskundige..

Geweldig uitgelegd Arend :)

Dat is beetje een raar voorbeeld. De kans op 6 is 1/6 en niet 1/2. De kans op 6 keer achter elkaar 6 gooien is gewoon (1/6)^6 oftewel 1^46656.
Het is niet voor niet een BInomiale verdeling, het gaat om 2 gelijke kansen. Een beter voorbeeld is om de piramide voor te stellen als een bak met spijkertjes waar een balletje van boven naar beneden doorheen valt. Ieder getal staat voor het aantal manieren dat het balletje op die plek voorbij kan vallen als het even waarschijnlijk is dat het balletje naar links of rechts zal vallen bij een spijkertje.

De getallen zijn exact gelijk aan wat ik al zei:

0C0
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4

4C2 is het aantal combinaties van 2 uit 4. Door daarmee te werken en het script op die manier te maken is het veel uitgebreider te gebruiken en kan ook alleen de 85e rij bijvoorbeeld weergegeven worden. 4 boven 2 (4C2 dus) is gelijk aan:
4! / (2! * (4-2)!) dus 4! / (2! * 2!) oftewel (4 * 3 * 2 * 1) / ((2 * 1) * (2 * 1)) = 24 / 4 = 6

Om een mooie functie te maken in PHP heb je dus een functie faculteit($getal); nodig en een functie combinatie($boven, $onder); die van faculteit(); gebruik maakt. Op die manier zou je makkelijk alleen de 85e rij kunnen laten zien die er als volgt uit ziet:

84C0 84C1 84C2 ...tot aan... 84C82 84C83 84C84

In PHP zou het er dan zo uitzien:

<?
function faculteit($getal) {
$output = 1;
for ($i = $getal; $i > 1; $i--) {
$output = $output * $i;
}
return $output;
}
function permutatie($groot, $klein) {
$output = faculteit($groot) / faculteit($groot - $klein);
return $output;
}
function combinatie($boven, $onder) {
$output = faculteit($boven) / (faculteit($onder) * faculteit($boven - $onder));
return $output;
}
function pascal($start, $stop) {
$output = '';
for ($i = $start - 1; $i < $stop; $i++) {
for ($j = 0; $j <= $i; $j++) {
$output .= combinatie($i, $j).' ';
}
$output .= '<br>';
}
return $output;
}
echo pascal(4, 5);
?>

Dit geeft netjes als output:

1 3 3 1 <br>1 4 6 4 1 <br>

Het scriptje is nu even snel geschreven en voor de volledigheid staan ook permutaties erbij die niet nodig zijn.
Eigenlijk zou bij combinatie() en permutatie() nog gecontroleerd moeten worden of het 1e getal groter dan of gelijk aan het 2e getal is en of het 2e getal groter dan of gelijk aan 0 is. Ook moeten de cijfers gehele getallen zijn bij die functies en ook dat wordt nog niet gecontroleerd zou je allemaal kunnen maken.
Bij faculteit() moet het getal ook een geheel getal groter dan of gelijk aan 0 zijn.
Bij pascal() moeten het ook gehele getallen zijn groter dan 0. Het 2e getal moet daarbij groter dan of gelijk zijn aan het 1e blablabla.
Er wordt nu altijd achter een regel een zinloze spatie gezet daaraan zou ook nog wat gedaan kunnen worden net als de <br> op de allerlaatste regel die ook niet perse nodig is.
Maar dat was nogal overdreven / onnodig of had ik geen zin in om het er allemaal nog bij te maken :P

stelletje inteligente mensen hier :)

thnx voor jullie antwoorden!!!

[hartstikke offtopic]

wordt die avatar van je nou niet eens moe met lopen Boaz??

[/hartstikke offtopic]

nice scripting van de piramide :o)

Bas Kreleger schreef op 16.09.2004 12:32

[hartstikke offtopic]

wordt die avatar van je nou niet eens moe met lopen Boaz??

[/hartstikke offtopic]

soms wel jah, dan valt ie even om, maar dan gaat ie vaak meteen weer door.

Ik heb er vandaag nog eventjes aan gezeten en de code nog wat geoptimaliseerd. Ik heb meteen wat zitten experimenteren met classes dus ik weet niet of het wel zo verstandig is om er een aparte class probability voor te maken. Misschien dat iemand me uit kan leggen of het wel of niet nuttig is?
Ik heb er ook meteen een stukje bijgemaakt om de parsetime te berekenen, is wel handig om bij te houden als je veel rijen wil zien.
De faculteiten die geweest zijn worden opgeslagen in een array, en bij een nieuwe aanroep van faculteit() wordt eerst gecontroleerd of die arraywaarde niet al bestaat. Zo ja gebruikt hij die, anders wordt het uitgerekend en de uitkomst in de array gemikt.
Ook wordt bij combinatie() gekeken of het 2e getal 0 is, zo ja is de uitkomst altijd 1. Ook als de 2 getallen gelijk zijn. Bij permutatie() (functie die er voor de volledigheid bij zit maar niet gebruikt wordt) is dat ook ingebouwd, maar dan alleen als het 2e getal 0 is. Omdat 2 dezelfde getallen daar dus geen 1 als uitkomst moet geven.
Dit is de code uiteindelijk geworden:

<?
function parsetime_start() {
global $parsetime;
list($micro, $seconds) = explode(' ', microtime());
$parsetime = $micro + $seconds;
return TRUE;
}
function parsetime_stop() {
global $parsetime;
list($micro, $seconds) = explode(' ', microtime());
$parsetime = $micro + $seconds - $parsetime;
return TRUE;
}
function parsetime($digits = 5) {
global $parsetime;
return number_format($parsetime, $digits, '.', '');
}
class probability {
var $facArray = array();
function faculteit($getal) {
if (isset($this->facArray[$getal])) {
$output = $this->facArray[$getal];
}
else {
$output = 1;
for ($i = $getal; $i > 1; $i--) {
$output = $output * $i;
}
$this->facArray[$getal] = $output;
}
return $output;
}
function permutatie($groot, $klein) {
return $klein == 0 ? 1 : $this->faculteit($groot) / $this->faculteit($groot - $klein);
}
function combinatie($boven, $onder) {
return $onder == 0 || $boven == $onder ? 1 : $this->faculteit($boven) / ($this->faculteit($onder) * $this->faculteit($boven - $onder));
}
function pascal($start, $stop) {
$output = '';
for ($i = $start - 1; $i < $stop; $i++) {
for ($j = 0; $j <= $i; $j++) {
$output .= $this->combinatie($i, $j).' ';
}
$output .= '<br>';
}
return $output;
}
}
parsetime_start();
$probability = new probability();
echo $probability->pascal(1, 100);
parsetime_stop();
echo parsetime();
?>

als je toch een class maakt, kun je beter die functies erboven ook in de class zetten :) is netter

Ah ok :) Weer wat geleerd. Heb nog amper met classes gewerkt. Geen idee wanneer het wel of geen nut heeft om ze te gebruiken.
Is daar niet een uitleg / tutorial ofzo over te vinden. Dus niet de basis maar gewoon over wanneer het nu echt nuttig is enzo?