Algoritmiek 2007

Op deze pagina staat wat informatie over de werkgroep Algoritmiek, het practicum en de programmeeropgaven. Als er iets mist of onduidelijk is, laat het mij weten. Zie ook de pagina voor het vak zelf.

Practicum

Het skeletprogramma staat hier. Volg de volgende stappen om te beginnen.

  • Gebruik tar -xzvf practicum.tgz om het skeletprogramma uit te pakken.
  • Type cd practicum.
  • Type make om het practicum te compileren.
  • Type sh test.sh | less om het practicum te draaien.
  • Gebruik de 'up' en 'down' pijltjestoetsen om te scrollen en 'q' om te stoppen.

De opgaven staan hier. Bewerk boom.cc om de opgaven in het practicum te verwerken. In dit bestand staat duidelijk aangegeven van waar tot waar aanpassingen gemaakt dienen te worden.

De liefhebbers kunnen ook zelf bomen maken om uit te proberen. Let er wel op dat de bomen niet hoger mogen zijn dan 6 en dat de invoer een geldige preordewandeling van een boom moet zijn. Het getal 0 is gereserveerd voor het aangeven van een NULL pointer.

De preordestring "a00" geeft dus een boom met 'a' als wortel en geen kinderen. De string "a0b00" geeft een boom met 'a' als wortel en 'b' als rechterkind.

De uitwerkingen zijn hier te vinden, als alles goed is, dan moet het programma een uitvoer hebben die sterk hierop lijkt.

Programmeeropgave 1

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 16 maart.

Hieronder is een tabel met een paar winnende zetten voor een m'' bij ''n chompbord. Te gebruiken om de werking van het te schrijven programma te controleren.

m n x y
1 2 0 1
2 4 1 3
2 5 1 4
2 2 1 1
3 3 1 1
4 4 1 1
3 4 1 2
3 5 2 3
4 5 2 2

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken.

Programmeeropgave 2

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 13 april.

Hieronder staan een paar voorbeelden van mogelijke ritten op een m bij n bord.

Een open rit op een 4x3 bord, beginpositie (3, 1).

5 8 3
2 11 6
7 4 9
10 1 12

Een open rit op een 3x9 bord, beginpositie (2, 2).

23 26 3 14 17 20 5 8 11
2 15 22 25 4 13 10 19 6
27 24 1 16 21 18 7 12 9

Een gesloten rit op een 8x8 bord, beginpositie n.v.t.

1 16 31 36 3 18 21 34
30 37 2 17 32 35 4 19
15 64 61 38 47 20 33 22
62 29 48 43 60 39 46 5
49 14 63 56 45 42 23 40
28 55 44 59 52 57 6 9
13 50 53 26 11 8 41 24
54 27 12 51 58 25 10 7

Een gesloten rit op een 19x6 bord, beginpositie n.v.t.

12 9 14 39 46 7
15 44 11 8 37 40
10 13 38 45 6 47
43 16 55 48 41 36
54 51 42 35 56 5
17 58 53 62 49 34
52 61 50 57 4 63
59 18 69 64 33 30
68 65 60 31 70 3
19 72 67 76 29 32
66 79 74 71 2 77
73 20 83 78 75 28
82 87 80 97 84 1
21 100 85 88 27 98
86 81 96 99 114 89
101 22 113 90 103 26
112 95 102 105 108 91
23 106 93 110 25 104
94 111 24 107 92 109

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken. Dit is een versie uit mijn eigen studie.

Programmeeropgave 3

De opgave is hier te vinden. Het inleveren moet zowel electronisch als op papier gebeuren. De papieren versie van het verslag met de code als bijlage kan in de daarvoor bestemde doos (met het opschrift algoritmiek) in de postkamer (kamer 156, 1e verdieping). De deadline is 21 mei.

Hieronder staan een aantal invoerbestanden en de antwoorden.

Naam Antwoord
Test 1 3
Test 2 6
Test 3 1
Test 4 2
Test 5 7
Test 6 4
Test 7 2
Test 8 0
Test 9 3
Test 10 100
Test 11 255
Test 12 50
Test 13 236
Test 14 401
Test 15 122
Test 16 324

Hier staat een werkende implementatie, deze is gebruikt bij het nakijken.