PO: Informatica Olympiade 2013-2014

PO: Informatica Olympiade 2013-2014
Wat is de Informatica Olympiade?
De Nederlandse Informatica Olympiade (NIO) is een programmeerwedstrijd voor de bovenbouw
van het Voortgezet onderwijs. Het is een onderdeel van de International Olympiad in
Informatics (IOI).
De eerste ronde van de NIO bestaat uit 4 onderdelen A, B, C en D:
De 100 inzendingen met de meeste punten (mits deze minimaal 200 punten hebben gehaald)
worden uitgenodigd voor de tweede ronde van de NIO in maart 2015 op de Technische
Universiteit Twente. Om mee te doen aan de olympiade moeten je uitwerkingen zijn ingeleverd
bij de NIO voor 15 januari.
De PO
Als PO voor Informatica gaan we de een deel van de opgaven van de eerste ronde van de NIO
maken, namelijk die van categorie A. Je bent zelf vrij om ook daadwerkelijk mee te doen aan de
Olympiade met je uitwerkingen (Met het maken van de PO ben je al een eind op weg , je kunt
dan zelf de opgaven van categorie B, C en D nog maken voor meer punten). Meer details over
hoe je meedoet en welke voorwarden er zijn, vind je in het document van de NIO op de
informaticasite (en op www.informaticaolympiade.nl). Wt helpt je natuulijk graag hiermee als je
besluit mee te doen.
Inleveren en beoordeling:
Je doet deze PO alleen of met zijn tweeën. ( Let op: De deelname aan de NIO zelf is individueel,
dus van een duo kan maar 1 persoon deelnemen, omdat je niet 2x dezelfde code in kunt
leveren. Als je toch allebei wilt deelnemen, zul je verschillende versies van je oplossingen
moeten maken.)
Elke volledig correcte opgave is 2 punten waard (de opgaven worden wel steeds moeilijker).
Deels correcte oplossingen van een opgave leveren een deel van de 2 punten op. Je zult dus alle
5 de opgaven perfect moeten maken voor een 10.
Je levert bij Wt je gemaakte Javaprogramma’s in. Daarnaast maak je een begeleidend verslagje
waarin je de code uitlegt. Hiermee help je mij jouw/jullie code te begrijpen en laat je zien dat je
Wt/2014
1
begrijpt wat je gedaan hebt (plagiaatcontrole). Tevens lever je een logboekje in met de bestede
tijd per persoon. Dit geeft mij inzicht in jullie tijdsbesteding en kan dienen als bewijsmateriaal bij
eventuele onenigheid binnen een duo.
Je levert alle onderdelen van de PO in in een .zip file bij de opdracht die openstaat in de ELO. Je
hoeft per groepje uiteraard maar 1 keer in te leveren.
Uiterlijke inleverdatum: Zondag 30 November om 22:00 uur
Zie de volgende bladzijden voor tips, hints en uitleg om je te helpen de opgaven te tackelen.
Wt/2014
2
Aanwijzingen bij de opgaven van de NIO 2014-2015
Hieronder volgen eerst wat algemene aanwijzingen om je programma’s geschikt te maken voor
de NIO opgaven. Daarna volgen specifieke tips voor opgaven A1 t/m A5. Opgaven C1 en C2 zul je
helemaal zelf moeten uitvogelen.
Een ‘kaal’ Java programma
We hebben al gewerkt met JavaEditor en met Greenfoot (dat is een uitbreiding van de
programmeertaal Java). Javacode ken je dus al en voor de NIO kun je gewoon JavaEditor
gebruiken. Voor de NIO opgaven werken we alleen niet met applets zoals we vorig jaar hebben
gedaan, maar met ‘kale’ Java programma’s.
Het grootste verschil is dat een ‘kaal’ javaprogramma geen grafische interface heeft (dus geen
knoppen en tekstvelden etc.). Het werkt slechts op de commandline (console/DOS venster). Via
dat console venster kan tekstuele invoer en uitvoer worden gedaan. ‘Kale’ Javaprogramma’s
hebben dus ook geen voorgedefinieerde objecten zoals Greenfoot die heeft.
Je maakt een kaal javaprogramma in JavaEditor door te kiezen
voor “Bestand”->”Nieuw“->”Console”:
Een leeg console Javaprogramma bevat een klein stukje
standaardcode:
Je programma bestaat slechts uit een public class <bestandsnaam> (De klasse waarin je hele
programma zit) en een methode: public static void main(String[] args) Deze methode wordt
standaard uitgevoerd als je programma start. Hier kun je dus je eigen code toevoegen.
Wt/2014
3
Invoer lezen en schrijven
Om ons Java programma geschikt te maken voor het lezen van invoer en het schrijven van
uitvoer, moeten we een paar dingen aan de code wijzigen. Deze code krijg je van mij cadeau,
zodat je alleen op het oplossen van de problemen zelf hoeft te focussen. Pas je code aan zodat
hij er zo uitziet (let op dat je de naam van de Class niet verandert (Bij mij heet hij
Olympiade_opdr1). Deze moet overeenkomen met de bestandsnaam van je programmacode!):
Er zijn een paar dingen bijgekomen/veranderd:
 Op de eerste regel importeren we een Java bibliotheek die het mogelijk maakt om met
invoer en uitvoer te werken
 We declareren een object van de klasse BufferedReader. We hebben deze de naam
“reader” gegeven. Deze reader kunnen we nu in ons programma gebruiken om regels in
te lezen uit de invoer van het toetsenbord.
 De main methode is uitgebreid met de code throws IOException. Dit is door Java
verplicht als je met invoer en uitvoer werkt. Hiermee kunnen eventuele fouten in deze
invoer en uitvoer worden afgehandeld.
 In de body van de main methode hebben we als voorbeeld een stukje invoer en uitvoer
gedaan.
Wt/2014
4
Als je nu je programma uitvoert (dat doe je met de groene “play” knop bovenaan weet je
nog?) opent er een command venster met een knipperende cursor. Je kunt nu een regel tekst
intypen gevolgd door een enter. De tekst wordt ingelezen in je programma (en opgeslagen in de
String variabele s).
Je ziet je invoer meteen nog een keer op het scherm verschijnen. Dat komt omdat we met
System.out.println(s) de inhoud van variabele s nog een keer op het scherm
afdrukken.
Je programma eindigt nu meteen (en vraagt je om een toets in te drukken om het console
scherm te sluiten).
Aanpak Olympiadeopdracht A1
Lees eerst goed de opdrachtomschrijving van NIO opgave A1. Maak (als je dat nog niet gedaan
hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de
aanwijzingen op de vorige bladzijden.
Bij lastigere programmeeropgaven is het altijd belangrijk het probleem in kleine stapjes te
tackelen. Test steeds elke stap voordat je naar de volgende gaat. Dan weet je zeker dat je
tussendoor geen fouten maakt. Zo werk je langzaam naar de oplossing toe. Hieronder een
suggestie van stappen die je naar de oplossing leiden:
-
Stap 1: Lees het invoer getal. Om te testen of het gelukt is, schrijf je het gelezen getal
meteen naar de uitvoer.
-
Stap 2: Converteer het invoergetal naar int en maak een loopje (while of for) die precies
evenveel stappen heeft als het invoergetal aangeeft. Test dit door in elke stap van je
loop een regel testuitvoer te geven. Als het goed is schrijft je programma nu precies
zoveel regels als het invoergetal aangeeft.
-
Stap 3: Dit is de lastigste stap en de uitdaging van deze opgave. Je moet nu de
kerstboom gaan “opbouwen”. Hier zit natuurlijk een patroon in en dat zul je moeten
gebruiken. Een paar hints om je op weg te helpen:
o
Wt/2014
Je hebt in stap 2 een loop gemaakt gelijk aan het aantal regels dat de kerstboom
hoog is. Dit noemen we de hoofdloop. Begin elke stap van de hoofdloop met
een lege String. Vul deze langzaam met het juiste aantal - en *. Hiervoor heb je
nog meer kleine loops nodig (zie volgende hint). Als je een regel zo gevuld hebt,
druk je hem af op het scherm en begint de volgende stap van de hoofdloop.
5
o
Om een aantal keer achter elkaar hetzelfde teken in een String te zetten kun je
het volgende doen:
String regel = "";
for (int i=0; i<10; i++) {
regel += "x";
}
Bovenstaande code heeft als resultaat dat de String regel gevuld is met
“xxxxxxxxxx” (10 keer “x”)
o
-
Het aantal - en * in elke regel van de kerstboom is afhankelijk van 2 dingen:
 Het invoergetal
 De hoeveelste regel is dit?
Gebruik deze info om de binnenste loops te maken.
Stap 4: Je hebt nu de “bovenkant” van de kerstboom gemaakt. Jehoeft nu alleen de
“stam” er nog onder te plakken. Dit is nu eenvoudig, want de stam is hetzelfde als de
eerste regel van de kerstboom.
Aanpak Olympiadeopdracht A2
Lees eerst goed de opdrachtomschrijving van NIO opgave A2. Maak (als je dat nog niet gedaan
hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de
aanwijzingen op de vorige bladzijden.
-
Stap 1: lees het invoergetal. Test dit weer door het getal meteen naar de uitvoer te
schrijven.
-
Stap 2: zorg dat je programma invoer blijft lezen net zolang tot er een 0 wordt
ingevoerd. Daarvoor kun je onderstaande code gebruiken:
// lees de eerste regel van de invoer:
String invoer = reader.readLine();
//zolang de invoer niet gelijk is aan 0:
while (!invoer.equals("0")) {
// doe iets met de invoer
...
...
// lees de volgende regel:
invoer = reader.readLine();
}
Wt/2014
6
-
Stap 3: Converteer steeds het invoer getal naar een int en gebruik een if om te
controleren of dit getal even of oneven is (gebruik modulo %). Druk nu steeds het woord
“even” of “oneven” af op het scherm om je code te testen. Als je niet meer weet hoe de
modulo (%) werkt, spiek in het Javaboek op bladzijde 65.
-
Stap 4: Je kunt nu herhaaldelijk invoer lezen en bepalen of deze even of oneven is. Het
zou nu eenvoudig moeten zijn om een totaal bij te houden van de kwadraten van alle
oneven invoer. Zodra je programma een 0 als invoer krijgt, kun je dit totaal op het
scherm afdrukken. Test het goed en controleer steeds of je uitvoer klopt.
Aanpak Olympiadeopdracht A3
Lees eerst goed de opdrachtomschrijving van NIO opgave A3. Maak (als je dat nog niet gedaan
hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de
aanwijzingen op de vorige bladzijden.
Deze opdracht zijn eigenlijk 4 opdrachten in een, die je los van elkaar kunt zien. Twee hiervan
hebben we letterlijk gedaan bij de Javalessen in klas 5. Laten we die eerst tackelen:
-
Stap 1: De eerste opdracht is het teruggeven van de lengte van de invoer. Dit is
gemakkelijk te doen met 1 enkel javacommando. Check hoe je de lengte van een String
opvraagt in het Javaboek pagina 70.
-
Stap 2: We slaan de tweede en derde opdracht even over, omdat we de vierde opdracht
ook bijna letterlijk uit het Javaboek kunnen overnemen. Kijk op pagina 70 van het
Javaboek om te kijken hoe je een String omdraait.
-
Stap 3: We gaan verder met opdracht 2, omdat deze het makkelijkst is. Je zult net als bij
de vorige stap met een loop langs alle letters van de invoer moeten. Java heeft een
ingebouwd commando om van een teken te kijken of het een hoofdletter is. Die kunnen
we goed gebruiken:
Character.isUpperCase()
Deze methode heeft 1 nadeel: hij werkt op variabelen van het type char en niet op
String. Een char is een Java type dat we nog niet kennen. Het bevat 1 enkel ASCII
teken. Gelukkig is er ook een commando om een char uit een String te halen:
String mijnString = "Ik ben een voorbeeld";
char letter = mijnString.charAt(3);
In het voorbeeld bevat de variabele letter nu het teken op positie 3 uit
mijnString, dus een ‘b’ (let op we beginnen te tellen bij 0, dus positie 3 is de 4e
letter!)
Wt/2014
7
We zouden nu kunnen doen om te checken of het een hoofdletter is:
if (Character.isUpperCase(letter)) {
...
}
Zorg nu dus dat je 1 voor 1 alle letters uit de invoer haalt en kijkt of het een hoofdletter
is. Houd in een teller bij hoeveel hoofdletter je tegenkomt en druk deze uiteindelijk op
het scherm af.
-
Stap 4: Tot slot moeten we het aantal verschillende letters tellen.
o
Java heeft een commando om op te vragen of een String een bepaald teken
bevat. Die kunnen we goed gebruiken. Een voorbeeld om dat commando te
illusteren:
String mijnString = "Ik ben een voorbeeld";
if (mijnString.contains("q")) {
...
}
In het voorbeeld vragen we in een if of mijnString de letter q bevat.
o
Een naieve manier om dit probleem te tackelen is om van elk mogelijk teken te
vragen of deze in de invoer zit en zo alle verschillende tekens te tellen. Dit is erg
omslachtig en je weet niet precies welke tekens zijn toegestaan (er zijn ook
namen met trema’s erin bijvoorbeeld, zoals Daniël). Dat zijn wel erg veel ifs...
o
Een slimmere manier is als volgt:
 Maak een lege String aan met de naam uniekString
 Doorloop letter voor letter de invoer (zoals bij stap 2)
 Kijk steeds of de huidige letter van de invoer al voorkomt in
uniekString. Zo nee: voeg de huidige letter toe aan
uniekString.
 Als je alle letters van de invoer hebt gehad, bevat uniekString
alleen maar verschillende letters
 Je hoeft nu alleen maar de lengte van uniekString op te vragen
voor het goede antwoord.
Aanpak Olympiadeopdracht A4
Lees eerst goed de opdrachtomschrijving van NIO opgave A4. Maak (als je dat nog niet gedaan
hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de
aanwijzingen op de vorige bladzijden.
Wt/2014
8
De invoer voor deze opdracht bestaat uit 4 regels van 4 tekens (de tekens 0 of 1). Na het
accepteren van deze invoer, moet je horizontaal en verticaal gaan zoeken in deze invoer. Dat
lukt je alleen als je de invoer op de juiste manier opslaat: in een array. Een tweedimensionaal
array om precies te zijn.
Hoe zat dat ook alweer met die arrays? Misschien is dit een goed moment om de stof daarover
nog eens te bekijken. Lees Wt’s stof over arrays van vorig jaar en dan met name pagina 4 over
2D arrays.
Een opmerking over deze opgave: Als je goed naar het voorbeeld kijkt dat bij de opgave staat, zie
je dat grotere reeksen voor gaan op kleinere. Dat wil zeggen als op een regel staat 0111, dan is
dat een reeks van 3 x 1 en niet 2 reeksen van 2 x 1. Het is dus belangrijk om per regel de grote
reeksen eerst te checken. Pas als een grote reeks niet gevonden is, ga je kijken of er misschien
een kleinere reeks te vinden is.Houd dit in je achterhoofd bij het stappenplan
Een stappenplan om deze opgave te tackelen:
-
Stap 1: Zoals gezegd zal de invoer in een 2D array moeten worden opgeslagen. Omdat
elk “vakje” van de invoer uit 1 teken bestaat (0 of 1) ligt het voor de hand om een array
van het type char te gebruiken:
char[][] matrix = new char[4][4];
Zo creer je een 2D char array, met 4 elementen in beide richtingen. Precies groot
genoeg om de 4x4 invoer in op te slaan. Gebruik een loop om de 4 regels van de invoer
1 voor 1 te accepteren en de losse tekens (gebruik .charAt() ) op te slaan op de
juiste plek in het array.
Om te testen of het goed is gegaan kun je het beste (met weer een loop) de inhoud van
je array op het scherm afdrukken. Deze zou dan dus identiek moeten zijn aan de
gegeven invoer.
-
Stap 2: Maak 6 int tellers aan die je elk op 0 initialiseert. Deze 6 tellers houden bij
hoeveel reeksen van elke soort (2x0, 2x1, 3x0, 3x1, 4x0, 4x1) je tot nu toe hebt
gevonden. Met slimme loops gaan we zometeen door de invoer heen. Als we een reeks
vinden, verhogen we de juiste teller. Als we dan klaar zijn met de invoer bekijken,
bevatten de 6 tellers het goede antwoord en kunnen we deze op het scherm afdrukken.
-
Stap 3: Begin met checken op reeksen van 4 x 0 of 4 x 1. Dit moet natuurlijk zowel
horizontaal als verticaal gecheckt worden. Om horizontaal te kijken of er een reeks van
4 x 0 is. Moeten we simpelweg kijken of alle 4 de elementen van een regel gelijk zijn aan
0. Zoiets als dit:
Wt/2014
9
if (matrix[0][0]=='0' && matrix[0][1]=='0' && matrix[0][2]=='0' && matrix[0][3]=='0') {
…
…
}
Met deze voorbeeldcode checken we of de eerste horizontale rij (rij 0) uit allemaal 0en
bestaat. Dit moeten we natuurlijk checken voor elk van de 4 rijen. Dit kan slim met een
loop. Op een vergelijkbare manier check je de verticale kolommen.
Om te testen of je het goed hebt gedaan, zou ik na het checken het aantal gevonden
reeksen afdrukken. JE kunt makkelijk op het oog natellen of je antwoord (en daarmee je
code) klopt.
-
Stap 4: Als je een rij of kolom hebt gecheckt op een reeks van 4 en deze niet hebt
gevonden, dan moet je gaan checken op een reeks van 3. Dit gaat natuurlijk
vergelijkbaar met checken op een reeks van 4. Let op det er op 2 manieren een reeks
van 3 kan zijn, namelijk aan het begin of aan het eind van een rij of kolom
-
Stap 5: Als je een rij of kolom hebt ook hebt gecheckt op een reeks van 3 en deze niet
hebt gevonden, rest nog om te checken op reeksen van 2. Dit gaat wederom
vergelijkbaar. Let op dat er op 3 manieren een reeks van 2 in een rij of kolom kan zitten.
Namelijk aan het begin, in het midden en op het einde.
Verzin een paar testcases en check of je programma het goede antwoord geeft bij alle cases.
Aanpak Olympiadeopdracht A5
Lees eerst goed de opdrachtomschrijving van NIO opgave A5. Maak (als je dat nog niet gedaan
hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de
aanwijzingen op de vorige bladzijden.
Opgave 5 is met afstand de pittigste. Je hebt in ieder geval de volgende arrays nodig:
- Een (2D) array om de uitgebrachte stemmen per deelnemer op te slaan
- Een array om per stemronde te turven hoeveel stemmen elke kandidaat krijgt
- Een array om bij te houden welke kandidaten nog verkiesbaar zijn (zodat je weet hoe je
de stemmen moet tellen in elke ronde
Al deze arrays moeten variabel van lengte zijn, omdat je van te voren niet weet hoeveel
kandidaten en deelnemers er zijn.
Je zult vervolgens met een slimme loop net zoveel stemrondes moeten doorlopen als nodig is
om een winnaar te kiezen. Per ronde waarin geen winnaar gevonden is, moet je de verliezer af
laten vallen ,zodat deze niet meer meetelt in de volgende ronde.
Voor nu zijn dit alle hints. Op verzoek kan Wt de uiteg bij deze opgave nog uitbreiden.
Wt/2014
10
Nuttige links
Olympiade site: http://www.informaticaolympiade.nl
Uitleg over arrays: http://www.stedgymdenbosch.nl/subsites/informatica/data/veilig/Wt%20%20Arrays%20en%20sorteren.pdf
Java voor beginners met goede tutorials: http://www.homeandlearn.co.uk/java/java.html
Goede site om Java dingen op te zoeken: http://www.leepoint.net/notes-java/index.html
Enigma Java informatieboek:
http://www.sgdb.nl/subsites/informatica/data/veilig/deel1/infboek/4%20VisProg%20infboek.p
df
Enigma Java werkboek:
http://www.sgdb.nl/subsites/informatica/data/veilig/deel1/verwboek/4%20VisProg%20verwbo
ek.pdf
Wt uitleg Java arrays: http://www.sgdb.nl/subsites/informatica/data/veilig/Wt%20%20Arrays%20en%20sorteren.pdf
Wt/2014
11

Download Report