8 koninginnen op een schaakbord

Jaarvak op 7 studiepunten
Forumregels
Misschien werd je vraag al vorig jaar gesteld? Gebruik dus eerst de zoekoptie!

Er zijn formularia/samenvattingen aanwezig op de volgende link: viewtopic.php?f=19&t=93
Karolien Verelst
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 28 dec 2010, 16:02

8 koninginnen op een schaakbord

Berichtdoor Karolien Verelst » 19 jan 2011, 16:30

Zou iemand me aub kunnen helpen met deze vraag (van de vele) waarvan ik niksen snap?

"Volgend (onvolledig) programma poogt 8 koninginnen op een schaakbord te plaatsen zonder dat ze elkander zouden bedreigen. Hoeveel geheugen is er nodig om de gegevens om de gegevens tijdens de uitvoering te bewaren , wetend dat de variabelen en adressen 4 bytes lang zijn , behalve booleans variabelen die maar 1 byte lang zijn. U kunt het hoofdprogramma als een gewone procedure beschouwen en rekening houden dat de procedure PrintSolution in het totaal 40 bytes nodig heeft. Verklaar bondig u antwoord. Bepaal ook nog een ruwe bovenlimiet voor het aantal keer dat free wordt uitgevoerd."


MODULE Queens;

. . .

VAR Board : ARRAY [ -6..15] , [1..8] OF BOOLEAN;

r: [ -6..15] ; l : [1..8] ;

. . .

PROCEDURE Try (line: CARDINAL) ;
VAR row: CARDINAL;
PROCEDURE Free(r, l: INTEGER) : BOOLEAN;
VAR i: INTEGER ; f: BOOLEAN;

BEGIN

f:= TRUE;
FOR
i:= 1 TO l – 1 DO

f := f AND Board [r,i]
AND Board [r+l-i ,i]
AND Board [r-l+i ,i]
END;

RETURN f
END Free;

BEGIN

FOR
row := 1 TO 8 DO
IF Free (row, line) THEN
Board (row, line) := FALSE;
IF line < 8 THEN Try (line + 1)
ELSE PrintSolution

END;

END
END Try;

BEGIN


FOR r : = -6 TO 15 DO
FOR l := 1 TO 8 DO
Board[ r , l ] := TRUE

END
END;

Try(1) ;
END Queens.
Gebruikersavatar
AdamCooman
The IRW God
The IRW God
Berichten: 2376
Lid geworden op: 28 nov 2007, 18:19
Locatie: Aalst
Contacteer:

Re: 8 koninginnen op een schaakbord

Berichtdoor AdamCooman » 19 jan 2011, 17:34

de oplossingsmethode die in een ander topic staat, geschreven door de geniale wim

wim schreef:Speciaal voor de laat-avond-studenten zal ik het ook eens proberen uit te leggen (gebaseerd op de uitleg van Tibi).
Verbeteringen zijn altijd welkom.

Hij zegt in zijn vraag dat een adres en een CARDINAL elk 4 bytes groot zijn. Op de volgende manier bereken je dan het geheugen nodig voor de verschillende procedures:

Search:
Return address, static & dynamic links: 3 * 4 bytes (dit zijn 3 adressen die moeten bijgehouden worden)
VAR parameter: 4 bytes (een VAR parameter is ook een adres)
CARDINAL parameter: 4 bytes
CARDINAL terugkeerwaarde: 4 bytes
2 lokale variabelen Min en Max: 2 * 4 bytes
TOTAAL: 32 bytes

Src:
Return address, static & dynamic links: 3 * 4 bytes
2 CARDINAL parameters: 2 x 4 bytes
TOTAAL: 20 bytes

Het gaat hier om het binary search algoritme, waarvan er gezegd is dat die log2(n) keer Src aanroept. n is hier 1000000.
Het totaal aantal bytes nodig voor het aanroepen van Search is dus:
32 + 20 * log2(1000000) bytes
= 32 + 20 * log2(10^6)
= 32 + 120 * log2(10)
= 32 + 120 * 4 (<- eerste gehele getal groter dan log2(10) )
= 512 bytes

Eigenlijk is dit het aantal extra bytes nodig voor de aanroep van Search.
Bij de grootte van het beschikbare geheugen dat nodig is om dit programma te draaien moet dan nog dat van de module Test10 geteld worden. In de vraag staat dat de module Test10 gezien mag worden als een procedure en heeft dus deze hoeveelheid geheugen nodig:

Test10:
Return address, static & dynamic links: 3 * 4 bytes
ARRAY[0..1000000] OF CARDINAL: 1000001 x 4 bytes (vergeet de 0 niet)
2 CARDINALs: 2 x 4 bytes
TOTAAL: 4000024 bytes

TOTAAL van het TOTAAL:
4000024 + 512 = 4000536 bytes

Eerlijk gezegd ben ik het niet eens met deze berekening, want ik heb nog geen enkel besturingssysteem gezien waar programma's zo in het geheugen staan, maar ik zal toch maar meedoen met wat onze professor zegt
AdamCooman The IRW God
Als een link niet meer werkt, bezoek mijn site om het bestand te vinden
Afbeelding

Mooiste avatar: AdamCooman
Beste moderator: AdamCooman
Tom
Doctor in de forumwetenschappen
Doctor in de forumwetenschappen
Berichten: 3851
Lid geworden op: 05 okt 2008, 08:11
Locatie: Vilvoorde

Re: 8 koninginnen op een schaakbord

Berichtdoor Tom » 19 jan 2011, 17:37

De oplossing hierboven is denk ik van een andere opgave, maar het concept en de uitleg blijven natuurlijk hetzelfde



Maar een examen bij Tiberghien is echt niet moeilijk, Ok dit examen is niet heel eenvoudig,maar voor dit vak is het toch redelijk moeilijk om te buizen
Karolien Verelst
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 28 dec 2010, 16:02

Re: 8 koninginnen op een schaakbord

Berichtdoor Karolien Verelst » 19 jan 2011, 17:53

Okidak allesisns een grote merciii :D
globe
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 06 aug 2009, 17:01

Re: 8 koninginnen op een schaakbord

Berichtdoor globe » 20 jan 2011, 12:26

Tom schreef:De oplossing hierboven is denk ik van een andere opgave, maar het concept en de uitleg blijven natuurlijk hetzelfde



Maar een examen bij Tiberghien is echt niet moeilijk, Ok dit examen is niet heel eenvoudig,maar voor dit vak is het toch redelijk moeilijk om te buizen

voor u was het misschien gemakkelijk
Gebruikersavatar
Tom V
Master in de forumwetenschappen
Master in de forumwetenschappen
Berichten: 2996
Lid geworden op: 28 nov 2007, 20:09
Contacteer:

Re: 8 koninginnen op een schaakbord

Berichtdoor Tom V » 20 jan 2011, 12:57

globe schreef:
Tom schreef:De oplossing hierboven is denk ik van een andere opgave, maar het concept en de uitleg blijven natuurlijk hetzelfde



Maar een examen bij Tiberghien is echt niet moeilijk, Ok dit examen is niet heel eenvoudig,maar voor dit vak is het toch redelijk moeilijk om te buizen

voor u was het misschien gemakkelijk

Nee hoor, hij heeft echt wel gelijk. Op het tweede theorie-examen haal je zonder al te veel moeite een 16. Tiberghien is het type prof dat niet echt zin heeft om veel studenten te zien in de zomer.
Dit bericht kreeg een Chuck Norris quality label:

Afbeelding
Gebruikersavatar
Ruben
Doctor in de forumwetenschappen
Doctor in de forumwetenschappen
Berichten: 4848
Lid geworden op: 20 dec 2007, 21:15
Locatie: Steenhuffel

Re: 8 koninginnen op een schaakbord

Berichtdoor Ruben » 20 jan 2011, 14:25

Het tweede semester viel heel goed mee. Mr in januari vond ik het examen toch moeilyk hoor. Deels dr de saaie leerstof...
Ruben - Delivering awesomeness since 1989
Belle
heeft den knop voor het posten van berichten gevonden!
heeft den knop voor het posten van berichten gevonden!
Berichten: 9
Lid geworden op: 17 dec 2010, 17:51

Re: 8 koninginnen op een schaakbord

Berichtdoor Belle » 20 jan 2011, 16:35

Mja, Karolien & ik zijn arme architectjes hé, wij zien Tibi alleen in januari (en misschien augustus) ;)
Gebruikersavatar
AdamCooman
The IRW God
The IRW God
Berichten: 2376
Lid geworden op: 28 nov 2007, 18:19
Locatie: Aalst
Contacteer:

Re: 8 koninginnen op een schaakbord

Berichtdoor AdamCooman » 20 jan 2011, 16:49

haha, gepoept!

nee, die vraag die ge daar stelt is inderdaad het moeilijkste van het examen en eigenlijk te vroeg om te krijgen. ge zou een beetje assembler moeten kunnen programmeren om ze op te lossen en ze te snappen, maar laat het u niet afschrikken!
zorg ervoor dat de meerkeuzevragen goed zijn, hij vraagt bijna altijd dezelfde en er staan er veel op het forum. dan zit ge al bijna aan de helft van de punten. en dan gewoon goed concentreren bij de open vragen, ge geraakt er wel door, zelf al zijt ge maar arme architecten
AdamCooman The IRW God
Als een link niet meer werkt, bezoek mijn site om het bestand te vinden
Afbeelding

Mooiste avatar: AdamCooman
Beste moderator: AdamCooman
Gebruikersavatar
Tom V
Master in de forumwetenschappen
Master in de forumwetenschappen
Berichten: 2996
Lid geworden op: 28 nov 2007, 20:09
Contacteer:

Re: 8 koninginnen op een schaakbord

Berichtdoor Tom V » 20 jan 2011, 20:39

AdamCooman schreef:haha, gepoept!

nee, die vraag die ge daar stelt is inderdaad het moeilijkste van het examen en eigenlijk te vroeg om te krijgen. ge zou een beetje assembler moeten kunnen programmeren om ze op te lossen en ze te snappen, maar laat het u niet afschrikken!
zorg ervoor dat de meerkeuzevragen goed zijn, hij vraagt bijna altijd dezelfde en er staan er veel op het forum. dan zit ge al bijna aan de helft van de punten. en dan gewoon goed concentreren bij de open vragen, ge geraakt er wel door, zelf al zijt ge maar arme architecten

Het merendeel van die open vragen waren niet zo moeilijk, als ge goed kunt programmeren tenminste. Vooral het doorgeven van variabelen by value en bij variable (ik dacht toch dat het zo was) moet ge heel goed begrijpen.

Wat Adam zegt over de meerkeuzevragen klopt wel, maar het grote nadeel is dat de giscorrectie onfair is (foute antwoorden worden zwaarder afgestraft dan goeie beloond worden, zodat ge een negatieve score zou krijgen als ge alles gokt). Ge moet dus echt wel zeker zijn van uw antwoorden daar. Goed voorbereiden is de boodschap.

Arme architectjes toch, ik heb echt wel medelijden met jullie omdat jullie geen mondeling examen mogen doen in juli!
Dit bericht kreeg een Chuck Norris quality label:

Afbeelding

Terug naar “Informatica”

Wie is er online

Gebruikers op dit forum: Geen geregistreerde gebruikers en 2 gasten

cron