source: liacs/da/fibo_queue/examples/readme05.txt@ 351

Beste allemaal,

Bij de tweede opgave Datastructuren najaar 2005 (implementeer een Fibonacci
rij) hebben jullie al een hele beschrijving op papier gekregen. Toch valt er
nog meer te zeggen en dat wil ik bij deze doen. Eerst zal ik ingaan op deel A)
van de opgave, dan kort op deel B) en ten slotte heb ik nog enkele algemene
mededelingen.

********************************************************************************
******
2A:  *
******
Voor opdracht 2A) krijgen jullie een aantal bestanden cadeau, die het (goed)
maken van de opgave moeten vergemakkelijken. Ik zal eerst uitleggen waar deze
bestanden voor dienen, vervolgens geef ik nog enkele algemene aanwijzingen
voor bij het programmeren.

* Voor deel A) van de opgave hoef je alleen bestanden `fiboqueue.cc'
  en `fiboqueue.h' te maken die de Fibonacci rij implementeren. Om te kunnen
  testen of die een beetje doen wat je mag verwachten, is een eerste
  testprogramma `test.cc' bijgeleverd. Jullie wordt aangeraden om ook het
  commentaar bovenin dat programma te lezen.
* Tijdens het testen van het programma is het prettig als je de boom die
  je in de loop van de tijd hebt opgebouwd kunt afbeelden op het scherm.
  Daarvoor is een methode `Show' voor de klasse `FiboQueue' geschreven,
  samen met enkele bijbehorende functies. Deze functies vind je in
  de bestanden `fiboqueue.cc' en `fiboqueue.h' (dat wil zeggen: ik heb
  deze bestanden voor de zekerheid maar even `fiboqueue0.cc' en `fiboqueue0.h'
  genoemd; stel namelijk dat je zelf al met het implementeren van de
  Fibonacci rij was begonnen in eigen bestanden `fiboqueue.cc' en
  `fiboqueue.h', dan worden die niet meteen overschreven door mijn bestanden).
  Het is dus de bedoeling dat je deze functies in je eigen implementatie
  kopieert.
  De functies maken gebruik van een datastructuur die in `showlist.cc' en
  `showlist.h' is ge-implementeerd. Daarom moet je `showlist.h' in je eigen
  `fiboqueue.h' include-n.

  Om de werking van de methode `Show' te demonstreren, bekijk de volgende
  uitvoer:
  124                 363  225
  171  176  308       969  491  274
       514  533  698            385
                 943
  Deze Fibonacci rij bestaat uit drie bomen, een met wortel 124, een met
  wortel 363 en een met wortel 225. De wortels staan dus op het bovenste
  niveau. De eerst genoemde wortel is het minimum van de Fibonacci rij.

  De kinderen van een knoop x0 staan een niveau lager dan x0 zelf.
  Het eerste kind staat onmiddellijk onder x0; het tweede kind staat daar
  rechts van, het derde kind daar weer rechts van, enz. totdat je voorbij
  de broer van x0 loopt. De kinderen van 124 in ons voorbeeld zijn 171, 176
  en 308. Knoop 969 is het enige kind van 363. Knoop 225 heeft weer twee
  kinderen: 491 en 274.

  Om het allemaal van de andere kant te bekijken: 943 is een kind van 698,
  698 is een kind van 308 en 308 is een kind van 124.

  Uiteraard is deze vorm van presenteren slechts overzichtelijk bij een
  beperkt aantal knopen. Als je te veel knopen hebt, kan een niveau meerdere
  regels beslaan en is het niet meer eenvoudig na te gaan hoe de vader-kind
  relaties lopen.
* Om `test.cc' te compileren is er `Makefile1'. Deze moet je even naar
  `Makefile' copyeren, waarna met het commando `make' het compileren begint.
  Vervolgens kun je het testprogramma aanroepen met `Test'


Door met de bovenstaande programma's te testen, kun je denken dat je
implementatie van de Fibonacci rij correct is. Juich echter niet te vroeg.
Voordat je de bestanden `fiboqueue.cc' en `fiboqueue.h' inlevert, is het
verstandig om ze eerst ook te testen met het tweede testprogramma. Dit kan
teleurstellingen voorkomen. Voor de tweede test zijn meegestuurd:
* Negen C++ bestanden (`storelist.h', `storelist.cc', `standaard.h',
  `standaard.cc', `leestekst.h', `leestekst.cc', `communiceer.h',
  `communiceer.cc' en `test2.cc').
* Om deze bestanden samen met je implementatie van de Fibonacci rij te
  compileren, is er `Makefile2'. Even naar `Makefile' kopieren en je kunt
  compileren. Ook nu kun je het testprogramma aanroepen met `Test'.
  /***********/
  /* LET OP: */
  /***********/
  - Om een succesvolle compilering uit te kunnen voeren, moet het veld
    `Min' van de klasse `FiboQueue' (de wijzer naar de FiboNode met de
    laagste waarde) publiek gedeclareerd zijn. Dit is weliswaar strijdig
    met het concept van informatie-verhulling, maar dat moet dan maar.
  - Verder dient het bestand `fiboqueue.h' omgeven te zijn door een `ifndef'-
    constructie. Anders wordt het namelijk dubbel ge-include in `test2.cc'
    en krijg je een foutmelding.
    Zo'n constructie ziet er als volgt uit

      ifndef FiboQueueVar
      #define FiboQueueVar

        // de normale code

      #endif
  
  Om het jullie gemakkelijk te maken, is met deze twee zaken al rekening
  gehouden in het meegeleverde bestand `fiboqueue0.h'
* Het testprogramma leest enkele parameters uit het bestand `test.dat'.
  - Als de parameter `InterActief=1', verwacht het programma invoer van de
    gebruiker. Het is aan te raden om dat eerst een paar keer te proberen.
  - Met `InterActief=0', wordt de invoer uit een bestand gelezen, in het
    bijzonder uit het bestand dat op de volgende regel staat (in principe is
    dat `test1.inv'). In dat geval wordt de uitvoer behalve naar het scherm
    ook naar een bestand `test1.uit' geschreven.
  - Als dan de parameter `Controleren=0', gebeurt er niets met dit
    uitvoerbestand.
  - Met `Controleren=1' wordt echter gekeken of het uitvoerbestand gelijk is
    aan het controlebestand `test1.con'. Zo ja, dan wordt er `GELIJK' op
    het scherm afgedrukt. Zo nee, dan wordt aangegeven waar het verschil zit.

Het tweede testprogramma heeft de volgende werking: 
  er worden twee Fibonacci rijen tegelijkertijd bijgehouden. Op ieder moment
  is een van de twee actief.
  - Met behulp van `Switch' uit het menu kun je de andere rij actief maken.
  - De optie `Merge' zorgt ervoor dat de niet-actieve Fibonacci rij bij de
    actieve Fibonacci rij gevoegd wordt.
  - Met `Reset' kun je opnieuw beginnen, met twee nieuwe, lege Fibonacci
    rijen.
  - Ten slotte is er de optie `Empty'. Die is een beetje listig. In hoofdzaak
    bestaat die eruit dat de actieve Fibonacci rij element voor element wordt
    leeggemaakt. Er gebeuren echter ook nog wat andere dingen. Wat precies,
    dat merk je wel bij het testen.


Het is mogelijk dat je implementatie van de Fibonacci rij niet door deze
test heenkomt. Wellicht kunnen de volgende aanwijzingen dan nog wat helpen:
- houd bij de methodes van de Fibonacci rij die je implementeert rekening met
  randgevallen. Zo kan een Fibonacci rij waarop of waarmee je een operatie
  wilt uitvoeren, leeg zijn. In dat geval kun je (bijvoorbeeld) niet zomaar
  de inhoud van de `Min'-pointer inspecteren.
  Misschien dat dit door het meegeleverde testprogramma `test.cc' al keurig
  werd afgevangen, maar van `test2.cc' kan ik dat niet beloven ...
- op blz. 3 van de specificatie staat als uitleg bij de methode `Merge':
  "Verplaatst alle elementen van *Fqptr naar de huidige queue."
  Dat betekent dus dat de Fibonacci rij aangeduid met Fqptr, leeg wordt.
- controleer of je overal waar nodig de velden `Mark' en `Degree' aanpast.
  Door de fixatie op de pointer structuur van de Fibonacci rij, zou je deze
  velden namelijk gemakkelijk over het hoofd kunnen zien.

Los van de testprogramma's is er nog een andere, veelgemaakte fout.
Die bestaat eruit dat je geheugen reserveert met `new', maar dat je het niet
(op tijd) weer vrijgeeft met `delete'. Hierdoor zou het geheugen van de
computer vol kunnen lopen.

Je zult merken dat veel van de meegeleverde programma's enigszins
versleuteld zijn. De reden hiervoor is dat het eigenlijk niet de bedoeling
is dat je je in die bestanden gaat verdiepen, laat staan dat je ze gaat
wijzigen. De uitvoer die de bestanden produceren, zou voldoende moeten zijn.

Wanneer je implementatie van de Fibonacci rij de tweede test overleeft,
heb je een goede kans dat ie goed is, hoewel ik het niet bij voorbaat wil
garanderen. Het is dan wel de moeite om de bestanden `fiboqueue.cc' en
`fiboqueue.h' in te leveren. Je kunt dit doen met behulp van het commando:

tar cvzf - fiboqueue.cc fiboqueue.h | uuencode opdracht2A.gz |
  elm -s 'opdracht2A' svhaastr@liacs.nl
(dit alles op een regel)

Een print van de programma's is niet nodig.
Stuur alsjeblieft geen executables of zelfs maar object-bestanden mee !!!!!

********************************************************************************
******
2B:  *
******

Jullie zullen merken dat jullie oplossing voor deel A) van de opdracht
aan hoge eisen moet voldoen, wil die door het tweede testprogramma
heenkomen, wat toch wel een vereiste lijkt voor goedkeuring.

Bij deel B) zullen we minder streng zijn bij de beoordeling. Hoewel we het
leuk zou vinden als jullie oplossing voor deel B) met alle mogelijke
invoerbestanden (grafen, die aan de opgegeven specificatie voldoen) rekening
houdt, zullen we haar niet afkeuren als ze op een randgeval faalt.
Het is echter wel de bedoeling dat jullie het algoritme van Dijkstra op een
fatsoenlijk manier implementeren.

Bij dit onderdeel krijg je twee hulpbestanden mee:
* `fibo.grf', dat een graaf van 500 knopen bevat
* `fibo.con', de gewenste uitvoer bij `fibo.grf' (uitgaande van beginknoop 1)
Hiermee kun je je implementatie van het algoritme van Dijkstra een beetje
testen. Bedenk echter dat de nakijker de beschikking heeft over nog veel
meer testinstanties. Dus als je programma de juiste uitvoer geeft voor
`fibo.grf', zou het nog best verkeerd kunnen werken voor een andere
instantie.

In te leveren: alle bestanden die je nodig hebt om het programma te kunnen
draaien.  Testinstanties zijn echter niet nodig. Zoals gezegd, die hebben we
zelf genoeg.
Zorg ervoor dat je een directory hebt waarin alle benodigde bestanden staan
en ga in deze directory staan. Stel dat je alleen `.cc' en `.h' bestanden
en een Makefile nodig hebt, dan kun je met de volgende opdracht alles
naar de corrector sturen:

tar cvzf - *.cc *.h Makefile | uuencode opdracht2B.gz |
  elm -s 'opdracht2B' svhaastr@liacs.nl

Ook nu is een print van de programma's niet nodig en stuur ook nu geen
executables en object-bestanden mee !!!

********************************************************************************

Ten slotte: niemand is verplicht de opdrachten op de universiteit te maken.
Het is echter wel de bedoeling dat jullie oplossingen gecompileerd kunnen
worden (en werken) met g++ op de `beast' of op een Linux-pc in de
computerzalen beneden. Dan hoeft de nakijker niet eerst het meest geschikte
C++ platform uit te zoeken.
Daarom, voordat jullie iets inleveren, kijk even of het hier op de `beast'
of op een Linux-pc net zo goed werkt als (eventueel) thuis.

Omdat opdracht 2B) voortbouwt op 2A) is het aan te raden om eerst 2A)
netjes af te ronden en in te leveren (als je denkt dat ie goed is) en
dan pas aan 2B) te beginnen.  Als er namelijk fouten in de implementatie
van de kale Fibonacci rij zitten, hoef je die niet dubbel te verbeteren.

********************************************************************************

Mochten jullie na deze uitleg nog vragen hebben, dan kun je die uiteraard
altijd stellen. Voor vragen over de bedoeling van de opdracht (of over deze
uitleg zelf), kun je je wenden tot mij, Robert Brijder (kamer 156a,
telefoonnummer 071-527 7143, rbrijder@liacs.nl). Voor vragen over je eigen
programma, kun je je wenden tot Sven van Haastregt.

Succes

         Robert Brijder