Programmeermethoden 2011
Vierde programmeeropgave: Grote getallen
De
vierde programmeeropgave van het vak
Programmeermethoden
in het najaar van 2011
heet
Grote getallen;
zie ook het
twaalfde werkcollege,
en lees geregeld deze pagina op WWW.
Spreekuur in zalen 302 ... 309:
dinsdag 22, woensdag 23, donderdag 24,
dinsdag 29, woensdag 30 november, donderdag 1,
dinsdag 6, woensdag 7, donderdag 8 en vrijdag 9 december 2011, van circa
15.30 tot 17.00 uur.
De opgave
Het is de bedoeling om een C++-programma te maken dat de gebruiker
in staat stelt met grote getallen te rekenen via een eenvoudig menu.
De grote getallen worden gerepresenteerd door
dubbelverbonden pointer-lijstjes (rijtjes): met
pointers dus!
Ieder vakje uit de rij (een "cijfervakje") bevat een
int
waarin
k cijfers van het getal zitten opgeslagen;
hierbij is
k een constante, met waarde tussen 1 en 9.
In feite werken we in het
10k-tallig stelsel.
Zo wordt, als
k=2, het getal 23056007008
opgeslagen in 6 cijfervakjes: 2 30 56 0 70 8.
In het menu kan de gebruiker een drietal grote getallen,
zeg A, B en C, manipuleren;
tip: gebruik een array met drie grote getallen. De gebruiker kan voor elk van de drie een getal invoeren,
ze afdrukken, twee ervan optellen naar de derde,
of het "3n+1 vermoeden" (oftewel het
Collatz-probleem) laten doorrekenen.
Bijvoorbeeld: stop 123056007008 in B, 47040880760786750267 in C
en hun som in A. Laat daarna voor dit laatste getal bepalen
of het 3n+1 vermoeden klopt.
De menu-structuur is verder vergelijkbaar met die van de derde
programmeeropgave. Zo kan
de functie leesgetal opnieuw gebruikt worden!
De bedoeling is een klasse (class) grootgetal te maken,
met member-variabelen:
- een pointer begin naar het begin van de rij met cijfervakjes;
- een pointer einde naar het eind van de rij met cijfervakjes;
- een int met het aantal gebruikte cijfervakjes.
De cijfervakjes (een
struct met twee pointers en een
int)
zijn dubbelverbonden: ieder cijfervakje heeft een pointer
vorige naar
het vorige cijfervakje en
volgende naar het volgende cijfervakje.
De klasse heeft in ieder geval de volgende functies:
- print: druk groot getal af op het beeldscherm
(loop het getal af via de begin-pointer,
langs de volgende-pointers)
- leesin: lees groot getal in vanaf toetsenbord
(wat er gebeurt als iemand niet een k-voud aan cijfers geeft,
mag je zelf beslissen)
- telop(gg1,gg2): het grote getal moet de som worden van
de grote getallen gg1 en gg2
(loop de getallen af via hun einde-pointers,
langs de vorige-pointers)
- drienplus1(...): voor het grote getal wordt het
3n+1 vermoeden doorgerekend: na hoeveel stappen wordt 1 bereikt?
Druk steeds het resultaat van elke zoveelste
(bijvoorbeeld 100ste; de gebruiker mag dit bepalen) af
- voegachter: voeg een cijfervakje met een gegeven getal erin achteraan
het reeds gebouwde grote getal toe (pas op als dit het eerste cijfervakje is!)
- maaknullen(m):
maak een "groot getal" bestaande uit m cijfervakjes met 0 erin
(handig bij optellen)
- vernietig: gooi alle door het grote getal gebruikte cijfervakjes weg
De eerste functies staan gegeven in volgorde van moeilijkheid.
Maak ook snel de laatste (hulp)functies; andere hulpfuncties,
zoals
kopieer, kunnen ook nuttig zijn.
Denk ook aan een constructor.
Het is de bedoeling om een drietal files te produceren:
de eerste bevat main en het menu,
de tweede (zeg gg.h) bevat de klasse-definitie voor grote getallen,
en de derde (zeg gg.cc) bevat de functies uit die klasse.
Maak ook een makefile.
Dev-C++-gebruikers: Maak een nieuw leeg ("empty") project aan.
Voeg daaraan de drie files toe, en compileer het project.
Dev-C++ maakt nu zelf een makefile, makefile.win geheten.
Opmerkingen
Gebruik geschikte (member)functies.
Bij deze opgave mogen wederom bij
elke functie (zelfs main) tussen begin-{ en
eind-} hooguit circa 20 niet al te volle regels staan!
Elke functie dient van commentaar voorzien te zijn.
Let op goed parametergebruik: alle parameters, met uitzondering van membervariabelen, in de heading doorgeven, en de
variabele-declaraties zowel bij main als bij de
andere functies aan het begin.
De enige te gebruiken headerfile is in principe
iostream.
Zeer ruwe indicatie voor de lengte van het C++-programma: 400 regels.
Denk aan het infoblokje.
Uiterste inleverdatum: vrijdag 9 december 2011, 17.00 uur.
Haagse studenten: maandagochtend 12 december 2011, 11.00 uur.
Manier van inleveren:
- Digitaal de C++-code
inleveren: stuur een email naar
pm@liacs.nl.
Stuur geen executable's,
lever alleen de drie C++-files en de makefile digitaal in! Noem deze bij voorkeur zoiets als
simongarfunkelgg4.cc, dit voor de opdracht van het duo Simon-Garfunkel.
De laatst voor de deadline ingeleverde versie wordt nagekeken.
- En ook een papieren versie van het verslag
(inclusief de C++-code) deponeren
in de speciaal daarvoor bestemde doos "Programmeermethoden" in de postkamer
van Informatica, kamer 156 van het Snellius-gebouw.
Haagse studenten: bij de docent.
Overal duidelijk datum en namen van de (maximaal twee) makers vermelden,
in het bijzonder als commentaar in de eerste regels van de C++-code.
Het verslag (uiteraard weer in LaTeX,
zie de eerdere opgaven) moet het volgende bevatten: een zeer korte
beschrijving van het programma,
een beschrijving van punten waarop het programma faalt (indien van toepassing),
en een tabel met gewerkte uren, uitgesplitst per week en per persoon.
En een onderzoekje over een interval waarvoor het 3n+1 vermoeden is
gecontroleerd, waarbij het benodigde aantal stappen wordt geplot.
Tip: gebruik gnuplot.
Te gebruiken compiler: als hij maar C++ vertaalt;
het programma moet in principe zowel op een Linux-machine
(met
g++) als onder Visual C++ of Dev-C++ draaien.
Test dus in principe op beide systemen!
Het programma wordt doorgaans nagekeken met behulp van de compiler
die (uiteraard) in het commentaar bovenin het programma vermeld staat.
Normering: layout 1; commentaar 2; modulariteit (OOP, functies) 3;
werking 4.
Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde:
www.liacs.nl/home/kosters/pm/op4pm.php.