| 1 |
|
|---|
| 2 | Beste allemaal,
|
|---|
| 3 |
|
|---|
| 4 | Bij de tweede opgave Datastructuren najaar 2005 (implementeer een Fibonacci
|
|---|
| 5 | rij) hebben jullie al een hele beschrijving op papier gekregen. Toch valt er
|
|---|
| 6 | nog meer te zeggen en dat wil ik bij deze doen. Eerst zal ik ingaan op deel A)
|
|---|
| 7 | van de opgave, dan kort op deel B) en ten slotte heb ik nog enkele algemene
|
|---|
| 8 | mededelingen.
|
|---|
| 9 |
|
|---|
| 10 | ********************************************************************************
|
|---|
| 11 | ******
|
|---|
| 12 | 2A: *
|
|---|
| 13 | ******
|
|---|
| 14 | Voor opdracht 2A) krijgen jullie een aantal bestanden cadeau, die het (goed)
|
|---|
| 15 | maken van de opgave moeten vergemakkelijken. Ik zal eerst uitleggen waar deze
|
|---|
| 16 | bestanden voor dienen, vervolgens geef ik nog enkele algemene aanwijzingen
|
|---|
| 17 | voor bij het programmeren.
|
|---|
| 18 |
|
|---|
| 19 | * Voor deel A) van de opgave hoef je alleen bestanden `fiboqueue.cc'
|
|---|
| 20 | en `fiboqueue.h' te maken die de Fibonacci rij implementeren. Om te kunnen
|
|---|
| 21 | testen of die een beetje doen wat je mag verwachten, is een eerste
|
|---|
| 22 | testprogramma `test.cc' bijgeleverd. Jullie wordt aangeraden om ook het
|
|---|
| 23 | commentaar bovenin dat programma te lezen.
|
|---|
| 24 | * Tijdens het testen van het programma is het prettig als je de boom die
|
|---|
| 25 | je in de loop van de tijd hebt opgebouwd kunt afbeelden op het scherm.
|
|---|
| 26 | Daarvoor is een methode `Show' voor de klasse `FiboQueue' geschreven,
|
|---|
| 27 | samen met enkele bijbehorende functies. Deze functies vind je in
|
|---|
| 28 | de bestanden `fiboqueue.cc' en `fiboqueue.h' (dat wil zeggen: ik heb
|
|---|
| 29 | deze bestanden voor de zekerheid maar even `fiboqueue0.cc' en `fiboqueue0.h'
|
|---|
| 30 | genoemd; stel namelijk dat je zelf al met het implementeren van de
|
|---|
| 31 | Fibonacci rij was begonnen in eigen bestanden `fiboqueue.cc' en
|
|---|
| 32 | `fiboqueue.h', dan worden die niet meteen overschreven door mijn bestanden).
|
|---|
| 33 | Het is dus de bedoeling dat je deze functies in je eigen implementatie
|
|---|
| 34 | kopieert.
|
|---|
| 35 | De functies maken gebruik van een datastructuur die in `showlist.cc' en
|
|---|
| 36 | `showlist.h' is ge-implementeerd. Daarom moet je `showlist.h' in je eigen
|
|---|
| 37 | `fiboqueue.h' include-n.
|
|---|
| 38 |
|
|---|
| 39 | Om de werking van de methode `Show' te demonstreren, bekijk de volgende
|
|---|
| 40 | uitvoer:
|
|---|
| 41 | 124 363 225
|
|---|
| 42 | 171 176 308 969 491 274
|
|---|
| 43 | 514 533 698 385
|
|---|
| 44 | 943
|
|---|
| 45 | Deze Fibonacci rij bestaat uit drie bomen, een met wortel 124, een met
|
|---|
| 46 | wortel 363 en een met wortel 225. De wortels staan dus op het bovenste
|
|---|
| 47 | niveau. De eerst genoemde wortel is het minimum van de Fibonacci rij.
|
|---|
| 48 |
|
|---|
| 49 | De kinderen van een knoop x0 staan een niveau lager dan x0 zelf.
|
|---|
| 50 | Het eerste kind staat onmiddellijk onder x0; het tweede kind staat daar
|
|---|
| 51 | rechts van, het derde kind daar weer rechts van, enz. totdat je voorbij
|
|---|
| 52 | de broer van x0 loopt. De kinderen van 124 in ons voorbeeld zijn 171, 176
|
|---|
| 53 | en 308. Knoop 969 is het enige kind van 363. Knoop 225 heeft weer twee
|
|---|
| 54 | kinderen: 491 en 274.
|
|---|
| 55 |
|
|---|
| 56 | Om het allemaal van de andere kant te bekijken: 943 is een kind van 698,
|
|---|
| 57 | 698 is een kind van 308 en 308 is een kind van 124.
|
|---|
| 58 |
|
|---|
| 59 | Uiteraard is deze vorm van presenteren slechts overzichtelijk bij een
|
|---|
| 60 | beperkt aantal knopen. Als je te veel knopen hebt, kan een niveau meerdere
|
|---|
| 61 | regels beslaan en is het niet meer eenvoudig na te gaan hoe de vader-kind
|
|---|
| 62 | relaties lopen.
|
|---|
| 63 | * Om `test.cc' te compileren is er `Makefile1'. Deze moet je even naar
|
|---|
| 64 | `Makefile' copyeren, waarna met het commando `make' het compileren begint.
|
|---|
| 65 | Vervolgens kun je het testprogramma aanroepen met `Test'
|
|---|
| 66 |
|
|---|
| 67 |
|
|---|
| 68 | Door met de bovenstaande programma's te testen, kun je denken dat je
|
|---|
| 69 | implementatie van de Fibonacci rij correct is. Juich echter niet te vroeg.
|
|---|
| 70 | Voordat je de bestanden `fiboqueue.cc' en `fiboqueue.h' inlevert, is het
|
|---|
| 71 | verstandig om ze eerst ook te testen met het tweede testprogramma. Dit kan
|
|---|
| 72 | teleurstellingen voorkomen. Voor de tweede test zijn meegestuurd:
|
|---|
| 73 | * Negen C++ bestanden (`storelist.h', `storelist.cc', `standaard.h',
|
|---|
| 74 | `standaard.cc', `leestekst.h', `leestekst.cc', `communiceer.h',
|
|---|
| 75 | `communiceer.cc' en `test2.cc').
|
|---|
| 76 | * Om deze bestanden samen met je implementatie van de Fibonacci rij te
|
|---|
| 77 | compileren, is er `Makefile2'. Even naar `Makefile' kopieren en je kunt
|
|---|
| 78 | compileren. Ook nu kun je het testprogramma aanroepen met `Test'.
|
|---|
| 79 | /***********/
|
|---|
| 80 | /* LET OP: */
|
|---|
| 81 | /***********/
|
|---|
| 82 | - Om een succesvolle compilering uit te kunnen voeren, moet het veld
|
|---|
| 83 | `Min' van de klasse `FiboQueue' (de wijzer naar de FiboNode met de
|
|---|
| 84 | laagste waarde) publiek gedeclareerd zijn. Dit is weliswaar strijdig
|
|---|
| 85 | met het concept van informatie-verhulling, maar dat moet dan maar.
|
|---|
| 86 | - Verder dient het bestand `fiboqueue.h' omgeven te zijn door een `ifndef'-
|
|---|
| 87 | constructie. Anders wordt het namelijk dubbel ge-include in `test2.cc'
|
|---|
| 88 | en krijg je een foutmelding.
|
|---|
| 89 | Zo'n constructie ziet er als volgt uit
|
|---|
| 90 |
|
|---|
| 91 | ifndef FiboQueueVar
|
|---|
| 92 | #define FiboQueueVar
|
|---|
| 93 |
|
|---|
| 94 | // de normale code
|
|---|
| 95 |
|
|---|
| 96 | #endif
|
|---|
| 97 |
|
|---|
| 98 | Om het jullie gemakkelijk te maken, is met deze twee zaken al rekening
|
|---|
| 99 | gehouden in het meegeleverde bestand `fiboqueue0.h'
|
|---|
| 100 | * Het testprogramma leest enkele parameters uit het bestand `test.dat'.
|
|---|
| 101 | - Als de parameter `InterActief=1', verwacht het programma invoer van de
|
|---|
| 102 | gebruiker. Het is aan te raden om dat eerst een paar keer te proberen.
|
|---|
| 103 | - Met `InterActief=0', wordt de invoer uit een bestand gelezen, in het
|
|---|
| 104 | bijzonder uit het bestand dat op de volgende regel staat (in principe is
|
|---|
| 105 | dat `test1.inv'). In dat geval wordt de uitvoer behalve naar het scherm
|
|---|
| 106 | ook naar een bestand `test1.uit' geschreven.
|
|---|
| 107 | - Als dan de parameter `Controleren=0', gebeurt er niets met dit
|
|---|
| 108 | uitvoerbestand.
|
|---|
| 109 | - Met `Controleren=1' wordt echter gekeken of het uitvoerbestand gelijk is
|
|---|
| 110 | aan het controlebestand `test1.con'. Zo ja, dan wordt er `GELIJK' op
|
|---|
| 111 | het scherm afgedrukt. Zo nee, dan wordt aangegeven waar het verschil zit.
|
|---|
| 112 |
|
|---|
| 113 | Het tweede testprogramma heeft de volgende werking:
|
|---|
| 114 | er worden twee Fibonacci rijen tegelijkertijd bijgehouden. Op ieder moment
|
|---|
| 115 | is een van de twee actief.
|
|---|
| 116 | - Met behulp van `Switch' uit het menu kun je de andere rij actief maken.
|
|---|
| 117 | - De optie `Merge' zorgt ervoor dat de niet-actieve Fibonacci rij bij de
|
|---|
| 118 | actieve Fibonacci rij gevoegd wordt.
|
|---|
| 119 | - Met `Reset' kun je opnieuw beginnen, met twee nieuwe, lege Fibonacci
|
|---|
| 120 | rijen.
|
|---|
| 121 | - Ten slotte is er de optie `Empty'. Die is een beetje listig. In hoofdzaak
|
|---|
| 122 | bestaat die eruit dat de actieve Fibonacci rij element voor element wordt
|
|---|
| 123 | leeggemaakt. Er gebeuren echter ook nog wat andere dingen. Wat precies,
|
|---|
| 124 | dat merk je wel bij het testen.
|
|---|
| 125 |
|
|---|
| 126 |
|
|---|
| 127 | Het is mogelijk dat je implementatie van de Fibonacci rij niet door deze
|
|---|
| 128 | test heenkomt. Wellicht kunnen de volgende aanwijzingen dan nog wat helpen:
|
|---|
| 129 | - houd bij de methodes van de Fibonacci rij die je implementeert rekening met
|
|---|
| 130 | randgevallen. Zo kan een Fibonacci rij waarop of waarmee je een operatie
|
|---|
| 131 | wilt uitvoeren, leeg zijn. In dat geval kun je (bijvoorbeeld) niet zomaar
|
|---|
| 132 | de inhoud van de `Min'-pointer inspecteren.
|
|---|
| 133 | Misschien dat dit door het meegeleverde testprogramma `test.cc' al keurig
|
|---|
| 134 | werd afgevangen, maar van `test2.cc' kan ik dat niet beloven ...
|
|---|
| 135 | - op blz. 3 van de specificatie staat als uitleg bij de methode `Merge':
|
|---|
| 136 | "Verplaatst alle elementen van *Fqptr naar de huidige queue."
|
|---|
| 137 | Dat betekent dus dat de Fibonacci rij aangeduid met Fqptr, leeg wordt.
|
|---|
| 138 | - controleer of je overal waar nodig de velden `Mark' en `Degree' aanpast.
|
|---|
| 139 | Door de fixatie op de pointer structuur van de Fibonacci rij, zou je deze
|
|---|
| 140 | velden namelijk gemakkelijk over het hoofd kunnen zien.
|
|---|
| 141 |
|
|---|
| 142 | Los van de testprogramma's is er nog een andere, veelgemaakte fout.
|
|---|
| 143 | Die bestaat eruit dat je geheugen reserveert met `new', maar dat je het niet
|
|---|
| 144 | (op tijd) weer vrijgeeft met `delete'. Hierdoor zou het geheugen van de
|
|---|
| 145 | computer vol kunnen lopen.
|
|---|
| 146 |
|
|---|
| 147 | Je zult merken dat veel van de meegeleverde programma's enigszins
|
|---|
| 148 | versleuteld zijn. De reden hiervoor is dat het eigenlijk niet de bedoeling
|
|---|
| 149 | is dat je je in die bestanden gaat verdiepen, laat staan dat je ze gaat
|
|---|
| 150 | wijzigen. De uitvoer die de bestanden produceren, zou voldoende moeten zijn.
|
|---|
| 151 |
|
|---|
| 152 | Wanneer je implementatie van de Fibonacci rij de tweede test overleeft,
|
|---|
| 153 | heb je een goede kans dat ie goed is, hoewel ik het niet bij voorbaat wil
|
|---|
| 154 | garanderen. Het is dan wel de moeite om de bestanden `fiboqueue.cc' en
|
|---|
| 155 | `fiboqueue.h' in te leveren. Je kunt dit doen met behulp van het commando:
|
|---|
| 156 |
|
|---|
| 157 | tar cvzf - fiboqueue.cc fiboqueue.h | uuencode opdracht2A.gz |
|
|---|
| 158 | elm -s 'opdracht2A' svhaastr@liacs.nl
|
|---|
| 159 | (dit alles op een regel)
|
|---|
| 160 |
|
|---|
| 161 | Een print van de programma's is niet nodig.
|
|---|
| 162 | Stuur alsjeblieft geen executables of zelfs maar object-bestanden mee !!!!!
|
|---|
| 163 |
|
|---|
| 164 | ********************************************************************************
|
|---|
| 165 | ******
|
|---|
| 166 | 2B: *
|
|---|
| 167 | ******
|
|---|
| 168 |
|
|---|
| 169 | Jullie zullen merken dat jullie oplossing voor deel A) van de opdracht
|
|---|
| 170 | aan hoge eisen moet voldoen, wil die door het tweede testprogramma
|
|---|
| 171 | heenkomen, wat toch wel een vereiste lijkt voor goedkeuring.
|
|---|
| 172 |
|
|---|
| 173 | Bij deel B) zullen we minder streng zijn bij de beoordeling. Hoewel we het
|
|---|
| 174 | leuk zou vinden als jullie oplossing voor deel B) met alle mogelijke
|
|---|
| 175 | invoerbestanden (grafen, die aan de opgegeven specificatie voldoen) rekening
|
|---|
| 176 | houdt, zullen we haar niet afkeuren als ze op een randgeval faalt.
|
|---|
| 177 | Het is echter wel de bedoeling dat jullie het algoritme van Dijkstra op een
|
|---|
| 178 | fatsoenlijk manier implementeren.
|
|---|
| 179 |
|
|---|
| 180 | Bij dit onderdeel krijg je twee hulpbestanden mee:
|
|---|
| 181 | * `fibo.grf', dat een graaf van 500 knopen bevat
|
|---|
| 182 | * `fibo.con', de gewenste uitvoer bij `fibo.grf' (uitgaande van beginknoop 1)
|
|---|
| 183 | Hiermee kun je je implementatie van het algoritme van Dijkstra een beetje
|
|---|
| 184 | testen. Bedenk echter dat de nakijker de beschikking heeft over nog veel
|
|---|
| 185 | meer testinstanties. Dus als je programma de juiste uitvoer geeft voor
|
|---|
| 186 | `fibo.grf', zou het nog best verkeerd kunnen werken voor een andere
|
|---|
| 187 | instantie.
|
|---|
| 188 |
|
|---|
| 189 | In te leveren: alle bestanden die je nodig hebt om het programma te kunnen
|
|---|
| 190 | draaien. Testinstanties zijn echter niet nodig. Zoals gezegd, die hebben we
|
|---|
| 191 | zelf genoeg.
|
|---|
| 192 | Zorg ervoor dat je een directory hebt waarin alle benodigde bestanden staan
|
|---|
| 193 | en ga in deze directory staan. Stel dat je alleen `.cc' en `.h' bestanden
|
|---|
| 194 | en een Makefile nodig hebt, dan kun je met de volgende opdracht alles
|
|---|
| 195 | naar de corrector sturen:
|
|---|
| 196 |
|
|---|
| 197 | tar cvzf - *.cc *.h Makefile | uuencode opdracht2B.gz |
|
|---|
| 198 | elm -s 'opdracht2B' svhaastr@liacs.nl
|
|---|
| 199 |
|
|---|
| 200 | Ook nu is een print van de programma's niet nodig en stuur ook nu geen
|
|---|
| 201 | executables en object-bestanden mee !!!
|
|---|
| 202 |
|
|---|
| 203 | ********************************************************************************
|
|---|
| 204 |
|
|---|
| 205 | Ten slotte: niemand is verplicht de opdrachten op de universiteit te maken.
|
|---|
| 206 | Het is echter wel de bedoeling dat jullie oplossingen gecompileerd kunnen
|
|---|
| 207 | worden (en werken) met g++ op de `beast' of op een Linux-pc in de
|
|---|
| 208 | computerzalen beneden. Dan hoeft de nakijker niet eerst het meest geschikte
|
|---|
| 209 | C++ platform uit te zoeken.
|
|---|
| 210 | Daarom, voordat jullie iets inleveren, kijk even of het hier op de `beast'
|
|---|
| 211 | of op een Linux-pc net zo goed werkt als (eventueel) thuis.
|
|---|
| 212 |
|
|---|
| 213 | Omdat opdracht 2B) voortbouwt op 2A) is het aan te raden om eerst 2A)
|
|---|
| 214 | netjes af te ronden en in te leveren (als je denkt dat ie goed is) en
|
|---|
| 215 | dan pas aan 2B) te beginnen. Als er namelijk fouten in de implementatie
|
|---|
| 216 | van de kale Fibonacci rij zitten, hoef je die niet dubbel te verbeteren.
|
|---|
| 217 |
|
|---|
| 218 | ********************************************************************************
|
|---|
| 219 |
|
|---|
| 220 | Mochten jullie na deze uitleg nog vragen hebben, dan kun je die uiteraard
|
|---|
| 221 | altijd stellen. Voor vragen over de bedoeling van de opdracht (of over deze
|
|---|
| 222 | uitleg zelf), kun je je wenden tot mij, Robert Brijder (kamer 156a,
|
|---|
| 223 | telefoonnummer 071-527 7143, rbrijder@liacs.nl). Voor vragen over je eigen
|
|---|
| 224 | programma, kun je je wenden tot Sven van Haastregt.
|
|---|
| 225 |
|
|---|
| 226 | Succes
|
|---|
| 227 |
|
|---|
| 228 | Robert Brijder
|
|---|
| 229 |
|
|---|
