 |
||||
|
Programmeermethoden 2023
Tweede programmeeropgave: DeCoderen
De tweede programmeeropgave van het vak
Programmeermethoden
in het najaar van 2023
heet DeCoderen;
zie ook het
vierde werkcollege,
vijfde werkcollege
(de betreffende WWW-bladzijde bevat handige
tips)
en
zesde werkcollege,
en lees geregeld deze pagina op WWW.
We gaan een file coderen en decoderen met behulp van een eenvoudig coderingsschema. En we controleren het Collatz-vermoeden voor getallen in de invoerfile.
De compressietechnieken
GIF en
JPEG
dreigen steeds
duurder te worden. We gaan het nu dus maar zelf doen.
Voor de tweede programmeeropgave moet een programma worden
geschreven dat een file kan coderen en decoderen.
Aan de gebruiker wordt gevraagd of het
om coderen of decoderen gaat en hoe de originele (bestaande) file en de
"doelfile" heten. De veranderde invoerfile komt in deze doelfile terecht;
de invoerfile zelf blijft onveranderd.
Stel eenvoudige vragen om deze gegevens van de gebruiker te
weten te komen.
Het programma leest dan eenmalig de opgegeven invoerfile,
en schrijft de uitvoer symbool voor symbool weg naar de uitvoerfile.
Elk symbool uit de invoerfile mag en moet precies
één maal (met invoer.get (...)) gelezen worden.
Het coderen geschiedt regel voor regel, en gaat als volgt.
Iedere directe opeenvolging van k (groter dan of gelijk aan 2)
dezelfde karakters binnen een regel
wordt vervangen door dat karakter onmiddellijk gevolgd door het
getal k.
Een enkel karakter blijft gewoon zichzelf,
evenals regelovergangen.
Zo wordt de te coderen regel
Eet meer zeeegels gecodeerd als Eet me2r 10ze3gels
(in de originele zin staan blijkbaar tien spaties tussen meer en zeeegels).
Om later te kunnen decoderen hadden we moeten aannemen dat er
geen cijfers in de regel staan,
immers wat zou anders de codering e434 betekenen —
vier e's en vier 3-en of 434 e's?
Om dat probleem op te lossen
worden gecodeerde cijfers voorafgegaan door
een \ (backslash).
De backslash zelf wordt met twee backslashes gecodeerd.
Zo moet ABC11123ddd\efG\\\1
gecodeerd worden als
ABC\13\2\3d3\\efG\\3\1.
Deze codering heet officieel run-length encoding.
Na het coderen wordt op het scherm afgedrukt hoeveel karakters de originele file en de gecodeeerde file bevatten, en wat de "compressie-ratio" is: de verhouding tussen deze twee getallen, als geheeltallig percentage. Er moet op de gebruikelijk manier worden afgerond; het percentage kan groter dan 100 zijn. Bij het decoderen hoeft dit niet.
Voor elk geheel getal > 0 uit de invoerfile moet worden gekeken of het
Collatz-vermoeden waar is
voor dat getal;
zie ook sheet 17 van het derde college.
Op het scherm wordt afgedrukt wat het aantal iteraties is bij 1 te komen, of het nummer van de iteratie waarvan het resultaat
boven INT_MAX (gebruik include <climits>) uitkomt. Als dit laatste gebeurt, wordt dit erbij vermeld.
Elke directe opeenvolging van cijfers in de invoerfile wordt als
een geheel getal opgevat. Neem aan dat ze alle kleiner dan of gelijk aan
INT_MAX zijn. Zo bevat 123abcd-"qqq 5"+++uvw-77.88ddd//vb5656
de gehele getallen 123, 5, 77, 88 en 5656.
Bij het decoderen hoeft dit niet te worden gecontroleerd.
Ter verdere inspiratie, zie het vijfde werkcollege, en een tweetal voorbeelden:
- Eenvoudige testinvoer: simpel2023.txt met bijbehorende uitvoerfile simpel2023uit.txt. Grootte invoerfile 704 karakters, uitvoerfile 499 karakters, compressie-ratio 71%; 20 regels.
- Moeilijke testinvoer: moeilijk2023.txt met bijbehorende uitvoerfile moeilijk2023uit.txt. Grootte invoerfile 348 karakters, uitvoerfile 373 karakters, compressie-ratio 107%; 15 regels. En 6171 vergt 261 iteraties, en 270271 gaat bij de 121ste door INT_MAX.
Opmerkingen
- We nemen aan dat de gebruiker zo vriendelijk is verder geen fouten te maken bij het invoeren van gegevens. Als een getal gevraagd wordt, geeft hij/zij een getal.
- Gebruik de regelstructuur: elke regelovergang in een bestand bestaat uit een LineFeed (\n) (in UNIX) of een CarriageReturn gevolgd door een LineFeed (\r\n) (in Windows). Normaal gesproken gaat dit "vanzelf" goed. We nemen aan dat er voor het EndOfFile-symbool (wat dat ook moge zijn) een regelovergang staat.
-
Alleen voor de namen van de files
mag een array (of string) gebruikt worden;
voor het lezen
en verwerken van de tekst is slechts het huidige karakter en
enige kennis over de voorgaande karakters nodig — zie boven.
Alleen de headerfiles iostream en fstream
mogen gebruikt worden (en string
voor de filenamen; denk in dat geval wellicht aan het gebruik
van c_str en climits voor INT_MAX).
Uit een file mag alleen met invoer.get (...) gelezen
worden, vergelijk Hoofdstuk 3.7 uit het dictaat,
gedeelte "aantekeningen bij de hoorcolleges".
Binnen de hoofdloop van het programma staat bij voorkeur maar
één keer een get-opdracht,
vergelijk het voorbeeldprogramma uit dit hoofdstuk
(daar staat twee keer get, één maal
vóór de loop, uiteraard).
Karakters mogen niet worden teruggezet in de
oorspronkelijke file.
Schrijf zelf functies die testen of een karakter een cijfer is, etcetera. Er mogen geen andere functies dan die uit fstream gebruikt worden, en wellicht c_str. - Denk aan het infoblokje dat aan begin op het scherm verschijnt. Gebruik enkele geschikte functies, bijvoorbeeld voor infoblokje, inlezen gegevens van de gebruiker, aantal cijfers van een getal, Collatz-controle, coderen en decoderen van een file; zie de tips bij het vijfde werkcollege. Globale variabelen zijn streng verboden. Ruwe indicatie voor de lengte van het C++-programma: circa 250 regels.
Uiterste inleverdatum: maandag 16 oktober 2023, 18:00 uur.
Manier van inleveren (één exemplaar per koppel, dat — ter herinnering — uit maximaal twee personen bestaat) is als volgt:
- Digitaal de C++-code inleveren via Brightspace > Course Tools > Assignments. Stuur geen executable's, LaTeX-files of PDF-files, lever alleen één C++-file digitaal in!
- En ook een papieren versie van het verslag
(inclusief de C++-code) deponeren
in de speciaal daarvoor bestemde doos "Programmeermethoden"
bij kamer 159 van het Snellius-gebouw.
Overal duidelijk datum en namen van de (maximaal twee) makers vermelden, in het bijzonder als commentaar in de eerste regels van de C++-code. Lees bij het zesde werkcollege hoe het verslag eruit moet zien en wat er in moet staan.
