 |
||||
|
Programmeermethoden 2020
Vierde programmeeropgave: Grote getallen
De vierde programmeeropgave van het vak
Programmeermethoden
in het najaar van 2020
heet Grote getallen;
zie ook het
elfde werkcollege,
en lees geregeld deze pagina op WWW.
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
(je kunt een array met drie grote getallen gebruiken).
De gebruiker kan voor elk van de drie een getal invoeren,
twee ervan optellen of vermenigvuldigen naar de derde,
of een Fibonacci-getal in een ervan laten uitrekenen.
Bijvoorbeeld: stop 123056007008 in B, het 567-e Fibonacci-getal in C
en hun som in A.
Steeds worden de drie getallen afgedrukt.
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 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; let op de nullen)
- leesin: lees groot getal in vanaf toetsenbord (wat er gebeurt als iemand niet een k-voud aan cijfers geeft, mag je zelf beslissen, maar het moet wel redelijk werken)
- 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)
- fibonacci(n): het grote getal wordt het n-de Fibonacci-getal (met n<10000); het eerste en tweede Fibonacci-getal zijn 1, en de som van het i-de en het i+1-de is het i+2-de; gebruik herhaald telop
- vermenigvuldig(gg1,gg2): het grote getal moet het product worden van
de grote getallen gg1 en gg2
(als deze optie ontbreekt, kost dat één punt)
================ hulpfuncties (private) ===================
- voegvoor(x): voeg een cijfervakje met een gegeven getal x erin vooraan het reeds gebouwde grote getal toe (pas op als dit het eerste cijfervakje is!)
- voegachter(x): voeg een cijfervakje met een gegeven getal x erin achteraan het reeds gebouwde grote getal toe (pas op als dit het eerste cijfervakje is!)
- vernietig: gooi alle door het grote getal gebruikte cijfervakjes weg
- kopieer(gg): kopieert gg naar het grote getal: met A.kopieer (B) wordt A een kopie van B
Als k > 4 is, kan bij het vermenigvuldigen een productje van twee int's boven INT_MAX uit komen. Gebruik voor dat productje tijdelijk een long of long long, dat zal wel helpen.
Maak ook een stapel. Deze onthoudt het derde grote getal, zeg C, steeds als dat verandert. De gebruiker kan hiermee naar keuze (herhaald) een stap terug doen.
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 voor de stapel,
en de derde (zeg gg.cc) bevat de functies uit die klassen.
Maak ook een makefile, zie later.
Tip: splits vanaf het begin in drie files!
In Code::Blocks
open je een nieuw project via
"File -- New project -- Empty project", vul wat in,
en voeg de files toe via "Project -- Add files",
en daarna het project compileren op de gebruikelijke manier.
Of, op eigen risco, lees
over projecten.
Nieuw: video (5 minuten) over projecten in Code::Blocks.
Liefhebbers: Compileer de files ook op een Linux-machine
(bijvoorbeeld in Windows 10 met Windows Subsystem for Linux (WSL)), en maak een makefile. Op een Mac moet dat laatste ook, trouwens.
Opmerkingen
Gebruik geschikte (member)functies.
Bij deze opgave mogen wederom bij
elke functie (ook main) tussen begin-{ en
eind-} hooguit circa 30 niet al te volle regels staan!
De menu-functie mag eventueel wat langer zijn.
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. Er mogen geen strings gebruikt worden.
Zeer ruwe indicatie voor de lengte van de gezamenlijke C++-files: 600 regels.
Denk aan het infoblokje.
Uiterste inleverdatum: maandag 7 december 2020, 17:00 uur.
Manier van inleveren:
- Digitaal de C++-code en het verslag (in PDF)
inleveren: stuur een email met de vier attachments naar
pm@liacs.leidenuniv.nl.
Stuur geen executable's, Noem de file gg.cc hier bij voorkeur zoiets als garfunkelsimongg.cc, dit voor de opdracht van het duo Simon-Garfunkel, en analoog de andere files. De laatst voor de deadline ingeleverde versie wordt nagekeken.
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 referentie betreffende Fibonacci-getallen (niet Dan Brown). En een grafiek (zie het bijbehorende werkcollege voor tips, met name over gnuplot) met door het programma uitgerekende getallen: hoe snel groeien Fibonacci-getallen?
