game maker
Gebruikersnaam:
Wachtwoord:
Home Info Forums Help
Welkom, Gast. Alsjeblieft inloggen of registreren.
De activerings e-mail gemist?
+  Forums
|-+  Werken met Game Maker
| |-+  Tutorials en Uitbreidingen (Moderator: Maarten Baert)
| | |-+  [Scr] Faculteit, Combinaties en Permutaties
Pagina's: [1]
« vorige volgende »
Print
Advertenties

ChrisCompany
Gebruiker


Offline Offline

Berichten: 1412


WWW
« Gepost op: 30 September 2008, 19:05:53 »

Faculteit, Combinaties & Permutaties
Gamemaker Versie:  Game Maker 5.x  Game Maker 6.x en  Game Maker 7 (alle versies waar for inzit)
Moeilijkheidsgraad: (gml) Makkelijk, (wiskundig) Gemiddeld
Omschrijving: Wiskundige functies faculteit, combinaties en permutaties voor snel gebruik in Gamemaker.

1. Inleiding
In sommige gevallen zal je bij het maken van spellen te maken krijgen met kansrekenen. Bijvoorbeeld bij het maken van een AI, het simpelweg berekenen van het aantal mogelijke zetten bij een bord-game of bij het maken van een rekenmachine, daarvoor zijn handige functies uitgevonden met wiskunde en die bespreek ik hier.

Opzich is het meer een kwestie van het weten van de wiskundige formules en het correct toepassen. De kennis van GML speelt hier niet echt een grote rol bij. Toch, voor mensen die er wel moeite mee hebben, zijn hier een paar handige codes om je te helpen. Ik heb ook de zoekfunctie gebruikt, maar er zijn nog geen examples hierover.

Meer over: Faculteit|Combinaties|Permutaties

1.1 Faculteit
Faculteit is de makkelijkste kansberekening en ook eigenlijk de basis voor de rest. De notatie is n! en het werkt op de volgende manier: (n - 0) x (n - 1) x (n - 2) etc. tot je bij 1 aankomt. Als je bijvoorbeeld wilt weten op hoeveel manieren 8 mensen op 8 verschillende stoelen kunnen zitten gebruik je 8! Omdat voor iedere volgende stoel 1 iemand minder is om de stoel te bezetten.

Maargoed, we zijn hier niet voor wiskundeles. Deze methode is makkelijk toe te passen in GML namelijk:
GML:
// Omschrijving: Rekent de n! uit
// Arguments: argument = n
// Return: antwoord op n!

if is_real(argument0) {
if argument0 = 0 { return 1; exit; }
if argument0 >= 70 { return -1; exit; }
var _ans; _ans = 1;
for(i=0; i<argument0; i+=1;)
{ _ans =  _ans * (argument0 - i); }
return _ans; } else { return 0; }
Ik heb hier wel rekening gehouden met het feit dat 0! = 1 en dat de faculteit van 70 of hoger niet te berekenen is. Dan returnt de code -1 (ook wel: oneindig).

Deze code ziet er alleen een beetje moeilijk uit en doet een paar overbodige dingen die alleen van belang zouden kunnen zijn als je een rekenmachine programma wilt maken. Overigens zijn ben ik erachter gekomen dat het berekenen van faculteiten groter dan 70 wel degelijk mogelijk is, alleen zal je computer een beetje moeite hebben met zoveel rekenwerk in 1 step. Dit kun je oplossen door een timeline/alarm of meerdere steps te gebruiken. Dankzij joffysloffy heb ik een code kunnen maken die zo min mogelijk werkgeheugen van je computer eist (wat een rol zou gaan kunnen spelen als je iedere step het aantal mogelijkheden berekent dmv deze code). Bedankt hiervoor!
GML:
//factorial(number)
var number,i,n;
number = argument0;
n = 1;

for(i=0; i<number; i+=1;)
{ n = n * (number - i); }

return n;
Je moet hier alleen zelf rekening houden dat een negatieve faculteit niet kan! (Ook bij mij 1e manier trouwens.)
Bedankt Marcoscosci voor het wijzen op het feit dat ik argument0 vergeten was te verangen door number!


1.2 Permutaties
Permutaties spelen ook een belangrijke rol in het kansberekenen. Notatie is x nPr n (in mijn geval), kort samengevat is x het totaal en is n het aantal dat je eruit gaat kiezen waarbij de volgorde waarop je ze kiest van belang is.

Ik heb hier 2 manieren voor, waarvan er 1 gebruik maakt van de faculteit code (aangeduidt als factorial, engelse term voor faculteit).
GML:
// Omschrijving: Rekent x nPr n uit
// Arguments: argument0 is x, het getal voor de permutatie,
//            argument1 is n, het getal erna
// Return: antwoord op x nPr n

if is_real(argument0) && is_real(argument1) {
if (argument0 == argument1) { return factorial(argument1); exit; }
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0) { return 1; exit; }
var _ans;
_ans = ( factorial(argument0) ) / ( factorial(argument0 - argument1) );
return _ans; } else { return 0; }

MAAR!: hou er rekening mee dat faculteit niet hoger kan zijn dan 70, terwijl permutaties vele male hoger kunnen zijn. Bijvoorbeeld 100 nPr 2 is gewoon uit je hoofd te berekenen en is namelijk 9900 (= 100x99). Dus is er een betere en officiŽlere manier om dit te bereken. De code lijkt heel erg op de code van Faculteit alleen dan korter en beter te berekenen.
GML:
// Omschrijving: Berekent x nPr n, versie2
// Verbetering: Script factorial niet meer nodig + werkt beter
// Arguments: argument0 is x, argument1 is n
// Return: Antwoord op x nPr n.

if is_real(argument0) && is_real(argument1) {
var _ans; _ans = 1;
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0) { return 1; exit; }
for(i=0; i<argument1; i+=1;)
{ _ans = ( _ans * (argument0 - i) ); }
return _ans; } else { return 0; }
Hou er wel rekening mee dat deze code geen limiet heeft en dus een overflow kan returnen. Bijvoorbeeld 100 nPr 98 zal een overflow geven.

1.3 Combinaties
Een andere manier om kans (mogelijkheden) te berekenen is het gebruik van combinaties. Notatie n boven k.

Er zijn verschillende methodes om een combinatie te berekenen, ik heb er al een aantal geschreven. Waarvan er 1 werkt met het faculteit script erbij en eentje waarbij de faculteit code er al inzit. Maar het probleem bij faculteit is nog steeds dat het niet hoger kan dan 70 anders is het getal INF.

Ik laat hier alleen de functie zien waarbij faculteit in de code zit verwerkt, je kan zelf gewoon een aantal aanpassingen toepassen zodat je factorial() kunt gebruiken.
GML:
// Omschrijving: Berekent het aantal combinaties van k uit n. (n boven k)
// Manier: manier 1
// Arguments: argument0 is n, argument1 is k
// Return: Antwoord van n boven k

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans, _a, _b, _c; _a = 1; _b = 1; _c = 1;

// Calculate n!
for(i=0; i<argument0; i+=1;)
{ _a = ( _a * (argument0 - i) ); }

// Calculate k!
for(i=0; i<argument1; i+=1;)
{ _b = ( _b * (argument1 - i) ); }

// Calculate (n - k)!
for(i=0; i<(argument0 - argument1); i+=1;)
{ _c = ( _c * (argument0 - argument1 - i) ); }

_ans = ( _a ) / ( _b * _c );
return _ans; } else { return 0; }

En hier het speciale trucje die wel nauwkeurig hoort te zijn, maar dat blijkbaar niet is. Maar wel met grote getallen kan werken!
GML:
// Omschrijving: Berekent het aantal combinaties van k uit n. (n boven k)
// Manier: manier 2 (beste)
// Arguments: argument0 is n, argument1 is k
// Return: Antwoord van n boven k

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans; _ans = 1;
for(i=0; i<argument1; i+=1;)
{ _ans = ( _ans * (argument0 - i) / (argument1 - i) ); }
return _ans; } else { return 0; }

Hier is het script met de officieŽle manier.

bron:wikipedia
GML:
// Omschrijving: Berekent het aantal combinaties van p uit n. (n boven p)
// Manier: manier 3 (officieŽle manier) + Gebruikt factorial script
// Arguments: argument0 is n, argument1 is p
// Return: Antwoord van n boven p

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans;
_ans = factorial(argument0)/(factorial(argument1)*factorial(argument0-argument1));
return _ans; } else { return 0; }

Het aantal combinaties van p uit n kan ook berekent worden door het aantal permutaties van p uit n nogmaals te delen door p! (p faculteit). Dit is overigens ook de beste manier aangezien permutaties wel met grote getallen kan werken.
GML:
// Omschrijving: Berekent het aantal combinaties van p uit n. (n boven p)
// Manier: manier 4 (gebruikt permutaties + factorial script)
// Arguments: argument0 is n, argument1 is p
// Return: Antwoord van n boven p

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans;
_ans = permutaties(argument0,argument1)/factorial(argument1);
return _ans; } else { return 0; }


1.4 Afsluiting
Hoop codes, ik heb ook de codes die wat minder handig zijn erbij gepost zodat je kunt zien op wat voor manieren het allemaal kan. Ik zal nog even nadenken over het combinatie script, dat moet te doen zijn om daar een goede code uit te krijgen die ook met getallen boven de 70 kan werken. Ik heb al zo m'n ideeŽn dus die ga ik binnenkort even uitwerken.

Ook zal ik binnenkort alle codes even met examples uploaden en de download links plaatsen zodat je alle mogelijke codes die ik ervoor heb gemaakt inclusief een handig example hebt, waarin je kunt zie hoe je het moet gebruiken.

Als er nog vragen zijn kun je me pm'en of mailen naar christiaan.93@hotmail.com!

Gr Chris

« Laatste verandering: 6 April 2011, 18:51:12 door ChrisCompany »

Naar boven Gelogd

joffysloffy
Gebruiker


Offline Offline

Berichten: 647

Game Maker 8.0 Pro.


« Antwoord #1 Gepost op: 14 Januari 2009, 19:31:04 »

Faculteit (factorial) kan veel makkelijker. Namelijk:
GML:
//factorial(number)
var number,i,n;
number = argument0
i = 1
n = 1

repeat(number)
{ n *= i
  i += 1 }

return n
Deze code zou het moeten doen met getallen groter dan 70, maar gm kan geen grote getallen aan. Hij loopt ergens in de 20-30 vast Tong.
Voor de rest goede tut Gemoedelijk.

EDIT: Oops Twijfelachtig. Topic is een beetje oud.

« Laatste verandering: 14 Januari 2009, 19:33:22 door joffysloffy »

Naar boven Gelogd

Maarten Baert
Forumbeheerder


Offline Offline

Berichten: 4942

Gelieve quote te gebruiken als je PMs beantwoordt.


WWW
« Antwoord #2 Gepost op: 15 Januari 2009, 16:13:46 »

Leuk en best handig in veel gevallen. Alleen gebruik je een wat vreemde notatie, meestal wordt dit gebruikt:
n nPr p = Vnp
n nCr p = Cnp = (np)

De codes zijn ook niet echt optimaal, ze zouden heel wat korter kunnen en vooral de combinatie functie kan veel beter (zodat je minder snel overflow krijgt).

Dit topic is trouwens helemaal niet zo oud, voor tutorials is het niet zo vreemd om na een paar maanden een nieuwe reactie te plaatsen.


Naar boven Gelogd

ChrisCompany
Gebruiker


Offline Offline

Berichten: 1412


WWW
« Antwoord #3 Gepost op: 22 Januari 2009, 14:30:31 »

Faculteit (factorial) kan veel makkelijker. Namelijk:
GML:
//factorial(number)
var number,i,n;
number = argument0
i = 1
n = 1

repeat(number)
{ n *= i
  i += 1 }

return n
Deze code zou het moeten doen met getallen groter dan 70, maar gm kan geen grote getallen aan. Hij loopt ergens in de 20-30 vast Tong.
Voor de rest goede tut Gemoedelijk.

EDIT: Oops Twijfelachtig. Topic is een beetje oud.

Jouw code ziet er makkelijker uit, maar is opzich slechter uitgewerkt dan die van mij. Jij doet bijna precies hetzelfde als ik, alleen werk jij met een opwaardse loop terwijl ik met een afwaardse loop werk. Voordeel van een achterwaardse loop is dat *1 makkelijk te vermijden is wat wel werkgeheugen kost, maar niks uithaalt.

Jij hebt er alleen voor gekozen om een repeat loop te gebruiken, waar ik gekozen heb voor een for loop. Deze maakt de variable i zelf al aan, maar werkt verder hetzelfde. Het enige grote verschil van jouw code is, en dat is waarom ie er ook makkelijker uitziet, is dat de invoer een reeŽl getal moet zijn (wat opzicht niet zo belangrijk is) en dan een faculteit groter dan 70 zo'n groot getal is (bijna 1 googol) dat je niks aan die waarde hebt.

Maar inderdaad zo nog een keer naar jouw code kijkend zie ik dat je code makkelijker is dan mijne, maar het was maar om te laten zien hoe je het KAN doen. : )  Bedankt voor je reply.

@ Matrebatre
Ja ik wist niet de precieze notatie en op wikipedia gebruikten ze k en n. En tja, was eigenlijk alleen maar zodat ik iets had waarmee ik het kon laten zien. Wel bedankt, nu weet ik wat het wel hoort te zijn.

Inderdaad de combinatie code is aan de slechte kant. Hier is de officieŽle manier:

GML:
// Omschrijving: Berekent het aantal combinaties van p uit n. (n boven p)
// Manier: manier 3 (officieŽle manier) + Gebruikt factorial script
// Arguments: argument0 is n, argument1 is p
// Return: Antwoord van n boven p

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans;
_ans = factorial(argument0)/(factorial(argument1)*factorial(argument0-argument1));
return _ans; } else { return 0; }

Het kan waarschijnlijk op een nog betere manier die wel met hogere getallen kan werken, volgens mij had ik daar eerst wel een oplossing voor. Het kan trouwens ook gewoon met het permutaties script en die nog een keer extra delen door p!. Dan ziet de code er zo uit:

GML:
// Omschrijving: Berekent het aantal combinaties van p uit n. (n boven p)
// Manier: manier 4 (gebruikt permutaties + factorial script)
// Arguments: argument0 is n, argument1 is p
// Return: Antwoord van n boven p

if is_real(argument0) && is_real(argument1) {
if (argument0 == 0) { return 0; exit; }
if (argument1 == 0 or argument1 == argument0) { return 1; exit; }
var _ans;
_ans = permutaties(argument0,argument1)/factorial(argument1);
return _ans; } else { return 0; }

Zou heel goed zijn dat ik een rekenfout heb gemaakt omdat ik een beetje haastig bezig ben, maar dit zou moeten kloppen en moeten werken met grote getallen.

Bedankt voor de reacties en tips Gemoedelijk

« Laatste verandering: 23 Januari 2009, 18:06:12 door ChrisCompany »

Naar boven Gelogd

joffysloffy
Gebruiker


Offline Offline

Berichten: 647

Game Maker 8.0 Pro.


« Antwoord #4 Gepost op: 22 Januari 2009, 17:34:15 »

Als je bij mijn script invoert: factorial(5.34) Dan krijg je gewoon 120.
En als je een negatief getal invult, krijg je 1 terug.
Volgens mij voert jouw code ook *1 uit Tong.
En het stukje code:
GML:
if argument0 >= 70 { return -1; exit; }
Lijkt mij overbodig, aangezien Game Maker toch zal vastlopen voor de 30 Tong.
En kost het checken of het groter is dan 70 en gelijk is aan 0 en of het een string is niet meer werkgeheugen dan een getal *1 te doen? (Ik gok dit maar, ik heb hier geen verstand van.)

EDIT:
Ik heb alleen in het create event gezet: factorial(170), en dat deed ie gewoon. Bij 171 liep ie vast, met zowel mijn code, als jouw code. Dus ik denk niet de codes veel zullen verschillen van hoeveel ze gebruiken.

« Laatste verandering: 22 Januari 2009, 17:41:06 door joffysloffy »

Naar boven Gelogd

Shiritt
Gebruiker


Offline Offline

Berichten: 733

YAY FAIRY WA LIEF WA ZACHT!


WWW
« Antwoord #5 Gepost op: 22 Januari 2009, 20:30:16 »

 Twijfelachtig, misschien wil je de moeilijkheidsgraad iets opkrikken, voor de niet wiskundige onder ons.




Venator Inc. Forum                                                  Venator Inc. Website
Naar boven Gelogd

ChrisCompany
Gebruiker


Offline Offline

Berichten: 1412


WWW
« Antwoord #6 Gepost op: 23 Januari 2009, 17:42:27 »

Twijfelachtig, misschien wil je de moeilijkheidsgraad iets opkrikken, voor de niet wiskundige onder ons.

Haha, zal ik doen. Hoewel het programmatie werk niet zo heel erg gevorderd is, het is alleen het toepassen van wiskunde formules die te maken hebben met kans in game-maker.

Ik heb alleen in het create event gezet: factorial(170), en dat deed ie gewoon. Bij 171 liep ie vast, met zowel mijn code, als jouw code.

Kan gamemaker dat berekenen? De uitkomst moet zijn 7.25741561530799x10^306 (doe ik even uit mn hoofd) wat naar mijn idee te groot is voor gamemaker om Łberhaupt in een integer te plaatsen.

Het probleem vastlopen is niet van belang gezien het feit dat je dat ook gewoon stapsgewijs (dmv een timeline, alarms of steps) kunt doen, maar het feit dat het getal zo groot is dat je er niks aan hebt wel. In het hele heelal bevinden zich niet eens googol deeltjes dus wat kan je mogelijk aan het getal hebben. Bovendien als je spel 1googol kansen heeft voor een volgende zet (waar de codes eigenlijk voor zijn en wat in geen enkel spel mogelijk is), zou je spel (als je een heel erg slim spel hebt) er langer dan een eeuw over doen om tot een conclusie te komen, wat wel erg lang wachten is hoor!

En nee, als het goed is voert mijn code niet het *1 uit, ik had dat nog speciaal getest Rolt ogen
Als het goed is als je
GML:
for(i=0; i<argument0; i+=1;)
verandert in:
GML:
for(i=0; i<argument0-1; i+=1;)
komt er een ander antwoord uit. Zo niet dan is dat de nieuwe manier :")

Maar ik geef toe jouw code is wat makkelijker, maar het gaat mij niet zo zeer om makkelijkheid, maar meer om prestatie in het spel. Het geheugengebruik van *1 is vrijwel niks, maar zodra je een heel spel maakt waarbij iedere step het aantal kansen wordt berekent helpt ieder klein beetje.

En nogmaals gaat het me er meer om dat mensen die dit willen gaan gebruiken, verschillende mogelijkheden zien en ben ik blij dat je jouw manier (die veel makkelijker oogt en beter begrijpbaar is) ook hebt gepost. En net wat je zegt gebruikt mijn code waarschijnlijk door de checks toch nog net iets meer werkgeheugen dan die van jou. Ik zal zien of ik een mix van de codes kan maken en zal die zo ff posten in edit.

EDIT:
De code die denk ik het best is om te gebruiken (dankzij joffysloffy)
GML:
//factorial(number)
var number,i,n;
number = argument0;
n = 1;

for(i=0; i<argument0; i+=1;)
{ n = n * (argument0 - i); }

return n;

« Laatste verandering: 23 Januari 2009, 17:58:23 door ChrisCompany »

Naar boven Gelogd

joffysloffy
Gebruiker


Offline Offline

Berichten: 647

Game Maker 8.0 Pro.


« Antwoord #7 Gepost op: 24 Januari 2009, 22:00:39 »

Ben ik blij dat je jouw manier ook hebt gepost.
Blij dat ik kon helpen Gemoedelijk.

Kan gamemaker dat berekenen? De uitkomst moet zijn 7.25741561530799x10^306 (doe ik even uit mn hoofd) wat naar mijn idee te groot is voor gamemaker om Łberhaupt in een integer te plaatsen.
Ik denk dat Game-Maker de berekening heeft overgeslagen of zo, want het spel liep niet vast, maar aangezien ik alleen dat in het create event had staan, heb ik ook de uitkomst niet gezien Grijns.
Dus ik ging het net nog even proberen:
GML:
show_message(string(factorial(20)))
Hier kreeg ik 2.432.902.008.176.640.000 uit. Als ik 21 doe, crasht ie Tong.

GML:
//factorial(number)
var number,i,n;
number = argument0;
n = 1;

for(i=0; i<argument0; i+=1;)
{ n = n * (argument0 - i); }

return n;
Ik snap nog steeds niet goed hoe die for-loop hier nou werkt. Ik kan for-loops wel redelijk gebruiken, maar ik weer niet precies hoe ze werken Grijns.

Dankzij joffysloffy heb ik een code kunnen maken die zo min mogelijk werkgeheugen van je computer eist (wat een rol zou gaan kunnen spelen als je iedere step het aantal mogelijkheden berekent dmv deze code). Bedankt hiervoor!
Yay, ik sta in de beginpost Grijns.
En graag gedaan Gemoedelijk.


Naar boven Gelogd

Marcoscosci
Oud-moderator


Offline Offline

Berichten: 1242


« Antwoord #8 Gepost op: 26 Januari 2009, 12:11:12 »

GML:
//factorial(number)
var number,i,n;
number = argument0;
n = 1;

for(i=0; i<argument0; i+=1;)
{ n = n * (argument0 - i); }

return n;

Dit is niet de handigste manier om een faculteit uit te rekenen. Er staat nu n * (n-1) * ... * 2 * 1. Daarbij is het logisch om number te gebruiken om vervolgens alsnog argument0 overal te gebruiken. Om net een paar rekenstappen te besparen kan je het beter andersom doen:

GML:
//factorial(number)
var number, i, n;
number = argument0;
n = 1;

for(i=2; i<=number; i+=1) n *= i;

return n;

Ik weet trouwens niet zeker of het nog nodig was de i te initializeren bij var. Daarvoor heb ik al iets te lang niet meer met gamemaker gewerkt. De i daar laten staan kan in ieder geval geen kwaad.


"De uitslag is bekend wanneer die klaar is, en hoe lang dat duurt weet niemand."
Naar boven Gelogd

Advertenties
« vorige volgende »
Pagina's: [1]
Print


Topic Informatie
0 geregistreerde leden en 1 gast bekijken dit topic.

Ga naar:  

Powered by SMF 1.1.21 | SMF © 2006-2007, Simple Machines
www.game-maker.nl © 2003-2019 Nederlandse Game Maker Community