 |
||||
|
Programmeermethoden 2020
Tweede programmeeropgave: DeCoderen
De tweede programmeeropgave van het vak
Programmeermethoden
in het najaar van 2020
heet DeCoderen;
zie ook het
vierde werkcollege,
vijfde werkcollege
en
zesde werkcollege voor tips en meer,
en lees geregeld deze pagina op WWW.
Kijk ook de video.
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.
En staan er "Lychrel-getallen" in de file?
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 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.
Verder moet het programma van elk geheel getal ongelijk nul dat bij het coderen in de invoerfile
voorkomt controleren of dit wellicht een Lychrel-getal is.
Op het scherm wordt het desbetreffende getal afgedrukt, en daarnaast wat het aantal iteraties is om tot
een palindroom te komen (voor 545 is dit 0, voor 113 is dit 1), of het nummer van de iteratie waarvan het resultaat
boven INT_MAX (gebruik zonodig <climits>) uitkomt
(voor 196 is dit (waarschijnlijk) 18). Als dit laatste gebeurt, wordt dit erbij vermeld.
Let op: dit kan bij het omkeren gebeuren, en ook bij het optellen!
De tekst 123abcd-"qqq 5"+++uvw-77.88ddd//vb5656 bevat
de gehele getallen 123, 5, 77, 88 en 5656; deze moeten dus gecontroleerd worden.
Neem aan dat de getallen in de tekst zelf hooguit INT_MAX zijn.
Ter verdere inspiratie, zie het vijfde werkcollege, en een tweetal voorbeelden:
- Eenvoudige testinvoer: test2020.txt met bijbehorende uitvoerfile test2020uit.txt.
- Moeilijke testinvoer: moeilijk2020.txt met bijbehorende uitvoerfile moeilijk2020uit.txt.
Opmerkingen
- We nemen aan dat de gebruiker zo vriendelijk is verder geen fouten te maken bij het invoeren van gegevens.
- Gebruik zonodig 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 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, fstream, string (alleen voor de twee filenamen) en climits (voor INT_MAX) mogen en moeten gebruikt worden. 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.
- Denk aan het infoblokje dat aan begin op het scherm verschijnt. Gebruik enkele geschikte functies, bijvoorbeeld voor infoblokje, openen van de files, sluiten van de files, omkeren van het getal, testen Lychrel-getal, coderen van een file 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 200 regels.
Uiterste inleverdatum: maandag 12 oktober 2020, 17:00 uur.
Manier van inleveren:
- Digitaal de C++-code en het verslag (in PDF)
inleveren: stuur een e-mail met deze twee attachments naar
pm@liacs.leidenuniv.nl.
Stuur geen executable's! Noem het C++-programma bij voorkeur zoiets als klaverrutte2.cc, dit voor de tweede opdracht van het duo van Rutte-de Klaver. 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. Lees bij het zesde werkcollege hoe het verslag eruit moet zien en wat er in moet staan.
