Informatica H8

  •  Programmeren nader bekeken
  • Opdracht 1 Programmeertalen

    Geen standaarduitwerking. Het gaat erom, dat de leerlingen begrippen rondom programmeertalen, programmeren en toepassingsprogramma's 'ontdekken' en beschrijven in eigen bewoordingen door de verschillende voorbeelden die ze vinden nader te beschouwen.

    Opdracht 2 Programmavoorbeelden

    Geen standaarduitwerking. Het gaat erom, dat leerlingen het begrippenkader van opdracht 1 nu verder uitbreiden en verdiepen door te kijken naar voorbeelden van toepassingsprogramma's. De daarop betrokken begrippen komen vervolgens in dit hoofdstuk aan de orde.

    Opdracht 3 Bekende termen en begrippen

    Geen standaarduitwerking.

    Opdracht 4 Leerdoelen

    Geen standaarduitwerking.

    Opdracht 5 Aanpak

    Geen standaarduitwerking.

    Opdracht 6 Machinetaal

    De leerlingen zullen concluderen, dat de kans op fouten het grootst is in opgave a, b en c. Zowel de voorleesfouten als de schrijffouten tellen daarbij mee. Het vierde voorbeeld (d) zal de minste fouten opleveren en is ook sneller te controleren op juistheid. In het laatste vorbeeld (e) kunnen diverse interpretatiefouten optreden als de schrijfwijze van zijde (zyde), = (is), 30 (dertig) en puntkomma (;) niet eenduidig en correct bekend is voor de schrijvende leerling. De nauwkeurigheid van voorlezen en noteren moet feitelijk voor elk teken en vooral elke spatie gedicteerd worden. Want ook het spatiegebruik kan in een programmeertaal tot fouten leiden.

    Opdracht 7 4-bits demo-computer Extra

    Er is geen standaarduitwerking voor deze practicumopdracht.

    Opdracht 8 Assembleertaal

    a invoeren = load (in laden)

    onthouden = move (plaats in geheugen)

    optellen = add (telop)

    uitvoeren = load (uit laden)

    vergelijken = compare (vergelijk)

    kiezen = jump (spring)

    herhalen = repeat (herhaal)

    b Ja, elke basisinstructie komt in principe in elke assembleertaal voor.

    Opdracht 9 Gereserveerde codewoorden in Basic en Java

    a In literatuur over specifieke programmeertalen (en op Internet) zijn de volledige specificaties (syntax-beschrijvingen) van vele verschillende programmeertalen (o.a. Basic en Java ) te vinden. In het theorieboek zijn de 35 Pascalcodewoorden beschreven. Die kunnen als referentie dienen om te bepalen of die codewoorden ook in andere talen op dezelfde wijze voorkomen en dezelfde betekenis hebben. Er zijn in Basic en Java 'dialecten' met afwijkingen van de standaard, daarom is het van belang dat de leerling de geraadpleegde bron vermeld.

     

    b De mogelijke Basic-codewoorden (Qbasic van Microsoft) zijn:

    base, call, case, clear, cls, close, const, com, csrlin, data, declare, dim, do, else, end, eof, erase, exit, for, fre, function, get, gosub, goto, if, input, key, line, locat, lock, lof, loop, lpos, lprint, next, on, open, option, out, peek, poke, pos, print, put, read, redim, rem, restore, return, run, seek, select, shared, shell, spc, static, stop, sub, swap, system, then, type, unlock, until, using, wait, with, write

    c De 35 Pascal-codewoorden (ANSI-standaard) zijn

    and, array, begin, case, const, div, do, downto, else, end, file, for, function, goto, if, in, label, mod, nil, not, of, or, packed, procedure, program, record, repeat, set, then, to, type, until, var, while, with

    c Er zijn 12 overeenkomende woorden in Pascal en (Q)Basic zijn:

    case, const, do, else, end, for, function, goto, if, then, until, with

    Het aantal verschillende woorden bedraagt enkele tientallen. Bovenstaande zelfde woorden kunnen mogelijk een verschillende betekenis hebben in beide programmeertalen.

    d De mogelijke Java-codewoorden (versie 1.1) zijn:

    abstract, boolean, break, byte, case, catch, char, class, const, continue, default, do, double, else, extends, final, finally, float, for, goto, if, implements, import, instanceof, int, interface, long, native, new, null, package, private, protected, public, return, short, static, super, switch, synchronized, this, throw, throws, transient, try, void, volatile, while.

    Ook in Pascal en Java zijn er een beperkt aantal (10x) codewoorden hetzelfde de meerderheid (enkele tientallen zijn verschillend. De 8 overeenkomende codewoorden in Pascal en Java zijn:

    case, const, do, else, for, goto, if, while

    Opdracht 10 Een Basicprogramma aanvullen

    a Nee, want er verschijnt slechts een vraagteken op het beeldscherm.

    b De toe te voegen regels zijn:

    5 PRINT "Ik bereken voor u het drievoud van een getal."

    6 PRINT "Type achter het vraagteken een getal."

    25 PRINT "Het drievoud van het ingevoerde getal is:"

    c De toe te voegen regel is:

    1 REM Dit programma berekent het drievoud van een ingevoerd getal.

    Opdracht 11 Een Basicprogramma wijzigen Extra

    a 10 REM Dit programma berekent het kwadraat van een getal.

    20 PRINT "Ik bereken voor u het kwadraat van een getal."

    30 PRINT "Typ achter het vraagteken een getal."

    40 INPUT Getal

    50 LET Kwadraat = Getal * Getal

    60 PRINT "Het kwadraat van het getal is:"

    70 PRINT Kwadraat

    80 END

    b De schermafdruk ziet er als volgt uit:

    Ik bereken voor u het kwadraat van een getal.

    Typ achter het vraagteken een getal.

    ? 5

    Het kwadraat van het ingevoerde getal is:

    25

    Opdracht 12 Een Pascalprogramma aanvullen

    a {Dit programma berekent het drievoud van een getal.}

    b writeln("Ik bereken voor u het drievoud van een getal.")

    writeln("Voer nu een getal in:");

    c write("Het drievoud van het getal is:");

    Opdracht 13 Een Pascalprogramma wijzigen

    a program BerekenKwadraat (input, output);

    {Dit programma berekent het kwadraat van een ingevoerd getal}

    var: getal : real;

    kwadraat : real;

    begin

    writeln("Ik bereken voor u het kwadraat van een getal.");

    writeln("Voer nu een getal in:");

    read (getal);

    kwadraat := getal * getal;

    writeln("Het kwadraat van het ingevoerde getal is:");

    write (kwadraat);

    end.

    b De schermafdruk ziet er als volgt uit:

    Ik bereken voor u het kwadraat van een getal.

    Voer nu een getal in:

    6

    Het kwadraat van het ingevoerde getal is:

    36

    Opdracht 14 Een Pascalprogramma coderen Extra

    a program BerekenWortel (input, output);

    {Dit programma berekent de Wortel van een ingevoerd getal}

    var: getal : real;

    wortel : real;

    begin

    writeln("Ik bereken voor u de wortel van een getal.");

    writeln("Voer nu een getal in:");

    read (getal);

    wortel := sqrt(getal);

    writeln("De wortel van het ingevoerde getal is:");

    write (wortel);

    end.

    b De schermafdruk ziet er als volgt uit:

    Ik bereken voor u de wortel van een getal.

    Voer nu een getal in:

    49

    De wortel van het ingevoerde getal is:

    7

    Opdracht 15 Een probleem logisch aanpakken

    b Je veronderstelt dat je op Schiphol in het vliegtuig stapt. Door bijvoorbeeld in Windows bij Instellingen, Configuratiescherm, Datum en Tijd te kijken, kun je er achter komen dat het in Amsterdam 1 uur later is dan in Greenwich en dat het dan in Tokio - en dus ook in Nagano - 9 uur later is dan in Greenwich. Dat wil zeggen dat het in Tokio 8 uur later is dan in Amsterdam. Op het moment dat je vanaf Schiphol vertrekt is het dus in Tokio 16.00 uur op 1 januari. Hoe lang je reis duurt, is afhankelijk van de route, de maatschappij waarmee je vliegt en dergelijke. Laten we voor het gemak aannemen dat je reis 36 uur duurt. Van die 36 uur worden 8 uur gebruikt om 1 januari af te sluiten. Je houdt dan nog 28 uur over. Dat is 1 dag en 4 uur. Je komt dus op 3 januari om 4 uur in de ochtend in Nagano aan.

    c Hetzelfde algoritme (stappenschema) is geldig als in opgave 15b. met de positie van Hawaii in plaats van Nagano. Als schatting van de vliegtijd mag ook (met stop-overs) 36 uur worden genomen). De draaiing van de aarde speelt voor de aankomstijd geen rol.

    Opdracht 16 Een algoritme verfijnen

    Bij deze vraag is er geen standaarduitwerking. De details van de uitwerking kunnen sterk verschillen afhankelijk van de inschatting van de kennis en vaardigheid van de medeleerling m.b.t. theezetten.

    Een voorbeeld van een detailverfijning van het koken van het water kan er als volgt uit zien:

    (Pak het pannetje)

    Ga naar het aanrecht

    Pak het kleinste pannetje van het pannenrek boven het aanrecht

    (Vul het pannetje met water)

    Zet het pannetje in de gootsteen onder de kraan

    Draai de kraan open

    Draai de kraan dicht als het pannetje vol is

    (Zet het pannetje op het gas)

    Pak het pannetje op

    Loop naar het gasfornuis

    Zet het pannetje op de rechts achteraan gelegen gaspit

    (Steek het gas aan)

    Pak de gasaansteker die naast het fornuis ligt

    Draai de meest rechtse gaskraan open

    Houd de gasaansteker bij de gaspit waar het pannetje op staat

    Ontsteek de gasaansteker

    Herhaal het ontsteken van de gasaansteker

    Totdat het gas aan is of 5 keer geprobeerd

    Als het gas na 5 keer proberen niet aan:

    Dan draai de rechter gaskraan dicht en haal er iemand anders bij
    Leg de gasaansteker terug
    (Wacht tot het water kookt)

    Wacht net zo lang tot het water begint te borrelen

    (Doe het gas uit)

    Draai de meest rechtse gaskraan dicht

    (Haal het pannetje van het gas)

    Pak de twee pannenlappen naast het gasfornuis

    Pak het pannetje met de pannenlappen beet

    Neem het pannetje op

    Zet het pannetje op het aanrecht

    ......

    Opdracht 17 Een algoritme uitwerken Extra

    a Bij deze vraag is er geen standaarduitwerking. De details van de uitwerking kunnen sterk verschillen afhankelijk van de inschatting van de kennis en vaardigheid van de medeleerling m.b.t. het bakken en serveren van een uitsmijter met ham en kaas.

    b Het bakken moet nu t.o.v. de beschrijving in opdracht 17a verder in detail met mogelijk een volgend (lager) niveau worden uitgewerkt.

    Opdracht 18 Een algoritme doorlopen

    Bij deze vraag is er geen standaarduitwerking. De leerling ervaart, dat het 'droog testen' van een algoritme nodig is om het volledig in alle details te begrijpen en de correcte werking vast te stellen.

    Opdracht 19 Geheugenplaatsen vullen

    Achtereenvolgens zit in de geheugenplaats kleinste:

    {7} onbekend, {8} onbekend, {9} 4, {10} 4, {11} 2, {12} 2, {13} 2, {14} 2

    Opdracht 20 Een programma aanpassen

    a De aan te passen regels (wijzigingen cursief) zijn:

    {lees 5 getallen en bepaal het minimum}

    getal4, getal5, kleinste : real {2}

    {inlezen van 5 getallen}

    read (getal3); read (getal4); read(getal5); {6}

    if getal5 < kleinste {13a}

    then kleinste := getal5; {13b}

    De andere regels blijven ongewijzigd.

    b Vervang overal waar kleinste voorkomt de naam door grootste en wijzig in alle if-opdrachten het teken < (kleiner dan) door > (groter dan).

    Opdracht 21 Een Basicprogramma met herhalingsstructuur

    a Door de regel wordt een lijst met aantal (=20) geheugenplaatsen voor te verwerken namen gereserveerd.

    b De herhalingslus wordt aantal (=20) maal doorlopen onafhankelijk of de naam al eerder gevonden wordt.

    De geheugenplaats aantal wordt niet gewijzigd en bevat steeds de waarde 20 ook nadat regel 90 voor de laatste keer is afgewerkt.

    Opdracht 22 Pascalprogramma TafelDrie

    b program TafelDrie (input,output);

    var i, product : integer;

    begin

    writeln("Ik bereken voor u de tafel van 3 af.");

    for i:=1 to 10 do

    begin

    product := i * 3;

    writeln(i, " X ", 3, " = ", product);

    end;

    end.

    b program BerekenTafel (input,output);

    var i, product, tafel : integer;

    begin

    writeln("Ik bereken voor u de tafel van een getal.");

    writeln("Geef getal tussen 1 en 10");

    read(tafel);

    writeln("De tafel van ", tafel, " is.");

    for i:=1 to 10 do

    begin

    product := i * tafel;

    writeln(i, " X ", tafel, " = ", product);

    end;

    end.

    Opdracht 23 Basicprogramma DrukMachten Extra

    a 10 REM Dit programma berekent de machten van 2.

    20 PRINT "Ik bereken voor u de machten van 2."

    30 LET Macht = 1

    40 FOR Teller = 1 TO 10

    50 LET Macht = Macht * 2

    60 PRINT 2; "tot de macht"; Teller; " = " Macht

    70 NEXT Teller

    80 END

    Het PSD is eenvoudig af te leiden uit bovenstaand programma.

    b 10 REM Dit programma berekent de machten van een grondtal.

    20 PRINT "Ik bereken voor u de machten van een grondtal."

    30 PRINT "Typ achter het vraagteken een getal."

    40 INPUT Grondtal

    50 LET Macht = 1

    60 FOR Teller = 1 TO 10

    70 LET Macht = Macht * Grondtal

    80 PRINT Grondtal; "tot de macht"; Teller; " = "; Macht

    90 NEXT Teller

    100 END

    c Wijzig in de uitwerking van opdracht 23b regel 60 en regel 70 als volgt:

    60 FOR Teller = 10 TO 1 STEP -1

    70 LET Macht = Grondtal ^ Teller

    Regel 50 kan bovendien vervallen.

    Opdracht 24 Pascalprogramma DrukMachten Extra

    program DrukMachten (input,output);

    var i, macht , grondtal : integer;

    begin

    writeln("Ik bereken voor u machten van een getal.");

    writeln("Geef een getal kleiner dan 10: ");

    read(grondtal);

    writeln("De machten van ", grondtal, " zijn:");

    macht := 1;

    for i:=1 to 20 do

    begin

    macht := macht * grondtal;

    writeln(grondtal, " tot de macht ", i, " = ", macht);

    end;

    end.

    {Het PSD is eenvoudig af te leiden uit bovenstaand programma.}

    Opdracht 25 Onbepaalde herhaling

    a De herhalingslus staat in de volgende regels:

    repeat

    teller := teller + 1;

    until lijst[teller]=naam or lijst[teller]=‘stop’;

    b Dan zou de herhalingslus niet stoppen en oneindig lang doorgaan. Het Pascal vertaalprogramma kan constateren, dat de teller-index groter wordt dan is toegestaan (maximaal 100) en geeft dan een foutmelding, omdat het gereserveerde geheugengebied wordt overschreden.

    Het is een logische fout, omdat de programmeur ook rekening moet houden met die mogelijke foutsituatie. Dat kan door in de until-test toe te voegen 'or teller = 100'.

    c De herhalingslus wordt dan 3 maal doorlopen, omdat bij de derde keer de gezochte naam wordt gevonden en de until-test 'lijst[teller]=naam' de herhaling stopt.

    Opdracht 26 Onbepaalde herhaling met test vooraf

    a De rij bevat maximaal 25 namen, maar het aantal werkelijk in te voeren namen kan door de gebruiker worden opgegeven in de variabele aantal. De bijbehorende geheugenplaastsen heten Lijst[1], Lijst[2], Lijst[3], enzovoort tot en met Lijst[aantal]. In het programma is bij de invoer van aantal geen test opgenomen of de waarde van maxaantal (250) is overschreden. Daartoe zou direct na read(aantal) een extra programmaregel kunnen worden opgenomen met de instructie:

    if aantal > maxaantal then aantal:=maxaantal;

    b Als een regel teller := 1 ontbreekt dan wordt de herhalingslus niet goed gestart. Immers de waarde van teller is dan bij aanvang onbepaald. Dan is het zeer waarschijnlijk dat de lijst niet vanaf het begin wordt doorzocht. Dat is zeker het geval als de lijst al een keer doorlopen is.

    Bij elke nieuw zoekactie moet de lijst vanaf de eerste naam worden doorlopen. Er volgt geen syntax foutmelding, maar het resultaat van het zoeken is onbetrouwbaar.

    c Dan heeft teller de waarde 26 gekregen. Als de naam is gevonden krijgt teller de waarde van maxaantal (=25), maar daarna volgt nog het statement teller:= teller + 1 en wordt die waarde van teller nog met 1 opgehoogd.

    d Dan heeft teller de waarde van aantal + 1. De waarde van aantal wordt door de gebruiker ingevoerd om het aantal in te voeren namen te bepalen.

    Opdracht 27 Een Pascalprogramma analyseren

    a Er zijn twee herhalingslussen. Een voor het inlezen van de namen en een voor het zoeken. Ze zijn beide gecodeerd als: while teller >= aantal do met een begin-end-block voor de te herhalen statements.

    b De eerste lus wordt 7 maal doorlopen en de tweede lus 4 maal.

    c Als de naam niet in de lijst staat wordt de herhalingslus na 7 (aantal namen) zoekacties verlaten en het programma eindigt. De gebruiker krijgt hiervan geen melding.

    d Als voor aantal een waarde groter dan maxaantal wordt ingevoerd, dan zal in de eerste herhalingslus bij de invoer van de namen de teller-index groter worden dan is toegestaan (maxaantal). De Pascalcompiler zorgt voor een foutmelding als dat gebeurt. Het programma moet dan worden aangepast om het overschrijden van de indexwaarde boven maxaantal te voorkomen.

    Er is hier sprake van een logische fout van de programmeur. Om deze fout te herstellen zou direct na read(aantal) een extra programmaregel kunnen worden opgenomen met de instructie:

    if aantal > maxaantal then aantal:=maxaantal;

    Opdracht 28 Een Pascalprogramma aanpassen

    a De volgende regel kan worden toegevoegd voor de opdracht read(aantal);

    writeln ("Er kunnen maximaal", maxaantal, "namen worden ingevoerd.");

    b Als de naam niet voorkomt in de lijst kan dat ogenschijnlijk eenvoudig worden gemeld door voor het laaste end-statement toe te voegen:

    if teller < maxaantal + 1 then writeln("Naam niet gevonden in de lijst.");

    Deze opdracht werkt echter niet correct als aantal de waarde van maxaantal heeft en de laatst ingevoerde naam ook de gezochte naam is. Daarom moet een andere oplossing worden gekozen. Bijvoorbeeld door toevoegen van een hulpvariabele waarin de te vinden naam wordt geplaatst. Dat kan door de opdracht:

    writeln(naam,"in de lijst");

    te vervangen door

    vindnaam := naam

    vooraf moet dan de variabele vindnaam worden gedeclareerd en met een waarde worden gevuld door:

    Var vindnaam := string;

    vindnaam := "Naam niet gevonden"

    Nu kan voor het laatste end-statement de afdruk-opdracht worden geplaatst:

    writeln( vindnaam, "in de lijst.");

    De toekenningsopdracht vindnaam := naam binnen de herhalingslus zorgt voor de juiste afdrukwaarde.

    Opdracht 29 Een Pascalprogramma met test achteraf Extra

    In het programma NaamZoeken2 worden de twee while-herhalingstructuren met het bijbehorende begin-end-block vervangen door:

    repeat

    {begin-end-block}

    until teller > aantal;

    Het bijbehorende PSD is eenduidig afleidbaar uit het gewijzigde programma.

    Opdracht 30 Een rekenkundig programma Extra

    a Het PSD is eenduidig afleidbaar uit de programmacode

    b Om een beginwaarde van deler te bepalen. De opdracht deler:= getal1 + getal2 kan gebruikt worden in plaats van de if-opdracht, maar dan wordt de while-lus veel vaker (en overbodig) doorlopen.

    c Door de opdracht deler :=0 wordt de while-lus de eerstvolgende keer beeindigd.

    d De lus wordt 7 maal doorlopen (resp. met de waarden 12, 11, 10, 9, 8, 7 en 6) de waarde 6 is tevens de gevonden grootste gemene deler. Immers 12 en 18 zijn beide deelbaar door 6 en niet door een groter getal. In de geheugenplaats deler staat dan dus de waarde 6.

    Opdracht 31 Getallen rangschikken met twee lijsten

    De ingevulde tabel vanaf de eerste keer sorteren wordt als volgt:

    elementnr: [1] [2] [3] [4]

    getallijst 2 5=G 3 4 bepaal grootste

    sorteerlijst 5 0 0 0 zet in sorteerlijst

    getallijst 2 0 3 4 maak nul

    getallijst 2 0 3 4=G bepaal grootste

    sorteerlijst 5 4 0 0 zet in sorteerlijst

    getallijst 2 0 3 0 maak nul

    getallijst 2 0 3=G 0 bepaal grootste

    sorteerlijst 5 4 3 0 zet in sorteerlijst

    getallijst 2 0 0 4 maak nul

    getallijst 2=G 0 0 0 bepaal grootste

    sorteerlijst 5 4 3 2 zet in sorteerlijst

    getallijst 0 0 0 0 maak nul

    sorteerlijst druk 5 4 3 2 druk sorteerlijst[1]

    .....

    sorteerlijst 5 4 3 druk 2 druk sorteerlijst[4]

    Opdracht 32 Een vast aantal getallen sorteren

    a De regel: maxnr = 200.

    b De inleesprocedure wordt:
    Procedure GetallenInlezen;

    begin

    for telA := 1 to maxnr do

    begin

    writeln("voer getal", telA, " in:");

    read getallijst[telA];

    end;

    end;

    Opdracht 33 Sorteerprogramma

    a Als de sorteerroutine is afgelopen bevatten de geheugenplaatsen getallijst[1], getallijst[2] en getallijst[3] alle drie de waarde 0.

    b In het voorbeeldprogramma wordt telkens de grootst gevonden waarde in getallijst[grootste] op nul gezet om in de volgende lus niet meer mee te doen. Dat is nodig omdat anders in elke herhaling telkens dezelfde waarde als grootste wordt gevonden.

    c In de regel grootste := telB wordt de index van het grootste getal bewaard bij het doorlopen van de binnenste lus. In de buitenste herhalingsstructuur wordt in de regel sorteerlijst[telA] := getallijst[grootste] de grootste waarde zelf overgezet naar de sorteerlijst.

    De index van het grootste getal wordt telkens onthouden in grootste en de gevonden waarde zelf wordt elke keer onthouden in het volgende element van sorteerlijst[].

    Opdracht 34 Getallen rangschikken met het verwisselalgoritme

    De ingevulde tabel vanaf de eerste keer wisselen wordt als volgt:

    elementnr: [1] [2] [3] [4]

    getallijst 5w 6w 3 4 test/wissel [1] en [2]

    getallijst 5 3w 6w 4 test/wissel [2] en [3]

    getallijst 5 3 4w 6w test/wissel [3] en [4]

    getallijst 3w 5w 4 6 test/wissel [1] en [2]

    getallijst 3 4w 5w 6 test/wissel [2] en [3]

    getallijst 3 4 5w 6w test/wissel [3] en [4]

    getallijst 2w 4w 5 6 test/wissel [1] en [2]

    getallijst 2 4w 5w 6 test/wissel [2] en [3]

    getallijst 2 4 5w 6w test/wissel [4] en [4]

    De laatste drie acties lijken overbodig, omdat er geen wisseling plaatsvindt, maar ze zijn toch nodig om de herhalingslus volledig te doorlopen. Dat is van belang om ook in de laatste ronde nog een verwisseling te kunnen uitvoeren. Laat zonodig voor de volgorde 6, 5, 4, 3 als invoerwaarden ook een stappenlijst maken.

    Opdracht 35 Bubble Sort

    a Door de aanroep van de procedure VerwisselGetallen.

    b Door het einde van procedure VerwisselGetallen

    c Dit kan door een stappenlijst zoals in opdracht 34 op te stellen en de herhalingslussen te doorlopen:

    [1] [2] [3] if lijst[telB] > lijst[telA] VerwisselGetallen

    lijst[ ] 2 1 3 If lijst[1] > lijst[1] VerwisselGetallen

    lijst[ ] 1w 2w 3 If lijst[1] > lijst[2] VerwisselGetallen

    lijst[ ] 1 2 3 If lijst[1] > lijst[3] VerwisselGetallen

    lijst[ ] 1 2 3 If lijst[2] > lijst[2] VerwisselGetallen

    lijst[ ] 1 2 3 If lijst[2] > lijst[3] VerwisselGetallen

    d De stappenlijst voor de invoer 3,2,1 wordt als volgt:

    [1] [2] [3] if lijst[telB] > lijst[telA] VerwisselGetallen

    lijst[ ] 3 2 1 If lijst[1] > lijst[1] VerwisselGetallen

    lijst[ ] 2w 3w 1 If lijst[1] > lijst[2] VerwisselGetallen

    lijst[ ] 1w 3 2w If lijst[1] > lijst[3] VerwisselGetallen

    lijst[ ] 1 3 2 If lijst[2] > lijst[2] VerwisselGetallen

    lijst[ ] 1 2w 3w If lijst[2] > lijst[3] VerwisselGetallen

    Er vinden drie verwisselingen plaats.

    Uit de stappenlijsten zien we een mogelijke optimalisatie van het algoritme. We kunnen immers de test overslaan waarin telB en telA gelijk zijn. Daardoor wordt het aantal herhalingen in de binnenlus met 1 verminderd. Het programma kan worden aangepast door telA:=telB te wijzigen in telA:= telB+1

    Opdracht 36 Alfabetisch sorteren van een vast aantal namen Extra

    a Er is geen standaarduitwerking voor deze opdracht. Er zijn diverse goede uitwerkingen mogelijk.

    b Een uitwerking van het programma (afgeleid van BubbleSort voor getallen) ziet er als volgt uit:

    program NAAMLIJSTSORTEREN (input,output);

    const aantal = 100;

    type naamrij = array[1..aantal] of string;

    var lijst : naamrij;

    hulpnaam : string ;

    telR, telA, telB, telW: integer;

    procedure NamenInvoeren;

    begin

    for telR := 1 to aantal do

    readln (lijst[telR]);

    end;

    Procedure NamenSorteren;

    Procedure VerwisselNamen;

    begin

    hulpnaam:= lijst[telA];

    lijst[telA]:= lijst[telA+1];

    lijst[telA+1]:= hulpnaam;

    end;

    begin {procedure NamenSorteren}

    for telB:=1 to aantal do

    for telA:= 1 to aantal-1 do

    if lijst[telA] > lijst[telA+1]

    then VerwisselNamen;

    end;

    Procedure NamenAfdrukken;

    begin

    for telW := 1 to aantal do

    writeln(lijst[telW]);

    end;

    BEGIN {Hoofdprogramma NAAMLIJSTSORTEREN}

    NamenInvoeren;

    NamenSorteren;

    NamenAfdrukken;

    END.

    c Wijzig 1(!) regel: const aantal = 200 ;

    d Wijzig 1(!) regel: if lijst [telA] < lijst[telA + 1]

    Opdracht 37 Uitvoeringstijd van algoritmen

    a De werking van het algoritme. Het aantal opdrachten in een algoritme. Het aantal herhalingsstructuren in het algoritme en vooral het aantal herhalingen in de herhalingsstructuren. De snelheid van de computer is niet bepalend, omdat elk algoritme in principe op elke computer kan werken. Een niet-efficient algoritme zal ook op een snelle computer veel meer tijd in beslag nemen dan een efficienter en sneller algoritme.

    b De dubbele lijst en grootste bepaling is minder efficient (kost meer tijd) dan de enkele lijst en de verwisselprocedure.

    c Proefondervindelijke vaststelling is mogelijk door de programma's dezelfde sorteerlijsten aan te bieden en de tijd op te nemen. Dat kan door gebruik te maken van time-functies in de gebruikte programmeertaal.

    'Meten' met een stopwatch is mogelijk maar niet erg praktisch zeker voor een relatief kleine sorteerlijsten.

    d De uitvoeringstijd van sorteeralgoritmen neemt niet lineair toe met het aantal te sorteren elementen, omdat er een geneste herhalingsstructuur in elk sorteeralgoritme voorkomt. De verschillen in efficientie van algoritmen nemen dus ook meer dan lineair toe bij toenemende aantallen te sorteren lijstelementen. Er is nog steeds onderzoek naar optimalisatie van (sorteer)algoritmen.

    e Versnellingen in de algoritmen zijn uitsluitend mogelijk door in detail te bekijken of het aantal opdrachten of het aantal herhalingen kan worden beperkt. Vooral bij de initiatie van de herhaling en de beeindiging van de herhaling. Optimalisatie (in procenten) door specifieke kennis en gebruik van de hardware, de programmeertaal en het vertaalprogramma laten we hier buiten beschouwing.

    f Via internet zijn bij het onderwerp sorteer(algoritmen) nog vele toelichtingen en varianten op de gepresenteerde algoritmen te vinden.

    Opdracht 38 Terminologie

    Geen standaarduitwerking.

    Opdracht 39 Evaluatie van het plan van aanpak

    Geen standaarduitwerking.