Institutionen för Datavetenskap ThomasH Övning

VT-94 INN01-b 13/4-94

Programmering for naturvetare, del 2 Övningsuppgifter

1 Modula-program, biblioteksmoduler, kommandon, uttryck och typer

Uppgift 1: (a) Vilka av följande teckensträngar är korrekta Modula-2 identifierare:

            MODULE      Module     module     mODULE
            A12A        321        A321       321A
            String      STRING     REAL       CARDINAL
            ML namn     f          f'         f''

(b) Vilka är olämpliga att använda?

Uppgift 2: Om en identifierare finns i ett Modula program måste den då vara deklarererad i programmet? Vilka möjligheter finns det att deklarera en identifierare i Modula?

Uppgift 3: I biblioteksmodulerna InOut och RealIO finns procedurer för att skriva ut värden av olika slag. Vad heter procedurerna? Hur många parametrar? Vad betyder parametrarna?

Uppgift 4: Gör ett Modula-2 program som beräknar (löp)hastigheten i min.sek/km givet en distans och en (löp)tid. Till exempel så skall 5(km) och 18.40(min.sek) ge resultatet 3.44(min.sek). Hur skall en funktion se ut som gör samma sak?

Uppgift 5: Ge ett värde och ett uttryck av följande typer:

        INTEGER     CARDINAL     REAL     CHAR
        BOOLEAN     STRING

Uppgift 6: Antag r är en variabel av typ REAL, i av typ INTEGER och c av typ CARDINAL. Skriv om följande tilldelningssatser så att de blir korrekta

        (a) r:=i/c  (b) i:=i+c
        (c) r:=c  (d) r:=c+l

Uppgift 7: Antag att vi har följande indata:

   24.7     -33E10      0.075

Vilken effekt har då följande satser (med lämpliga variabeldeklarationer för de ingående variablerna):

Institutionen för Datavetenskap ThomasH Övning

VT-94 INN01-b 13/4-94

 (a) ReadReal(r1,s);ReadReal(r2,s);ReadReal(r3,s)
 (b) ReadReal(r1,s);ReadInt(i1);Read(c);ReadReal(r2,s)

Uppgift 8: Beskriv i ord ett sätt att räkna antalet förekomster av bokstaven x i en text. Översätt till ett Modula-2 program.

Uppgift 9: (a) Skriv ett program som efter en lämplig utskrift på terminalen läser ett tal n från terminalen. Sedan läses ytterligare n tal och det minsta och det största skrivs sedan ut.

(b) Vilka andra metoder finns det att läsa ett godtyckligt antal tal från terminalen?

(c) Skriv ett program som läser ett antal tal från terminalen och beräknar medelvärdet. Går det enkelt att modifiera programmet så att man beräknar medianvärdet istället. (m är medianvärde till a_{1}, … a_{n} om det finns lika många värden som är större än m som det finns värden som är mindre än m)

Uppgift 10: (a) Skriv ett program som beräknar summan ∑_{i=2}^{40} i^{2} + 2i + 5 (b) Skriv ett program som avgör hur många gånger man måste iterera formeln

x_{n+1} = (x_{n} + \frac{2}{x_{n}})/2.

från startvärdet 1 för att komma så nära \sqrt{2} som bestäms av ett värde som läses från terminalen.

Uppgift 11: Skriv ett Modula program som läser en text skriven med bara stora bokstäver och skriver ut den med små bokstäver förutom efter punkt, utropstecken och frågetecken då det ska vara en stor bokstav.

Uppgift 12: Som ni sett finns proceduren ReadInt i biblioteksmodulen InOut. Om den inte fanns hur skulle man skriva den? Skriv också en procedur ReadReal.

Uppgift 13: Skriv ett program som läser en sekvens av tal på formen DDDD DD.DD (som betecknar artikelnummer och priser) och skriver ut en likadan lista men med priserna uppräknande med 8 procent. Vad händer om indata plötsligt får formen DDDD DD:DD? Hur skall man modifiera programmet så att det fortfarande fungerar?

Uppgift 14: I Unix finns ett program wc som räknar tecken, ord och rader i en fil. Skriv ett liknande program i Modula.

Uppgift 15: Skriv ett Modula program som upprepade gånger läser en rad från terminalen och översätter den till rövarspråket.

(a) Konsonanter dubbleras och får ett ’o’ mellan sig.

(b) Vokaler och blanktecken förblir oförändrade.

(c) Övovrorigoga totecockokenon foförorsosvovinonnoneror.

Institutionen för Datavetenskap ThomasH Övning

VT-94 INN01-b 13/4-94

2 Funktioner, procedurer, fält och moduler (abstrakta data typer)

Uppgift 1: Skriv en funktion som bestämmer om ett tal är ett primtal eller inte.

Uppgift 2: Skriv en procedur swap som skiftar två variablers värde. Programsnutten:

               x:=10; y:=20;
               swap(x,y);
               WriteCard(x,5); WriteCard(y,5);

skall ge upphov till utskriften

                  20   10

Uppgift 3: Skriv procedurer eller funktioner som beräknar följande operationer på (öppna) fält:

(a) summan av elementen i ett givet fält

(b) elementvis addition av två fält

(c) innerprodukten av två fält

(d) index till det största och det minsta värdet i ett fält

Uppgift 4: Definiera följande operationer på strängar.

(a) längden av en sträng

(b) konkatenering (sammanslagning av två strängar)

(c) likhet

(d) borttagning av tecknet från en position till en annan position i strängen

(e) kopiering av ett antal tecken från en sträng till en annan

Uppgift 5: Skriv en procedur som givet ett fält av heltal ordnar om dessa så att de kommer i ordning.

Uppgift 6: Skriv en funktion som letar efter ett tal i ett fält med heltal. Går det att göra en bättre funktion om man vet att elementen i fältet är ordnade (sorterade)?

Uppgift 7: Skriv ett program som beräknar medianvärdet av ett antal indata värden (maximalt 25 stycken). Medianvärdet skall beräknas av en funktion.

Uppgift 8: Skriv en modul som implementerar en abstrakt data typ för listor av heltal (med maximal längd 25) med operationerna cons, head, tail och length.

Uppgift 9: Gör samma sak med en kö. I denna stoppar man in element i en ända och tar ut dem i den andra (first in – first out). Det ska finnas motsvarande operationer som för listor ovan.

Institutionen för Datavetenskap ThomasH Övning

VT-94 INN01-b 13/4-94

3 Poster, programmeringsmetodik

Uppgift 1: Definiera en datatyp för att representera en bildskärmsyta (fönster). Om man vill göra en modul för fönster vilka operationer kan man tänka sig?

Uppgift 2: Skriv en (funktions)procedur som tar ett fält av heltal som argument och ger det största värdet samt hur många gånger det förekommer i fältet.

Uppgift 3: Definiera en abstrakt data typ (en modul som exporterar en typ) för tabeller av strängar med operationerna insert, find, empty och delete. Skriv först definitionsmodulen och sedan implementeringsmodulen.

Uppgift 4: I en MODULA lärobok finns följande typdefinition:

          TYPE Statustype = (grad, undergrad)
               Person     = RECORD
                               name : String;
                               CASE status : statustype
                               OF  grad :       age : CARDINAL;
                               |   undergrad:   weight : REAL;
                               END;
                            END;
          VAR  kent, ann  : Person;

Inititera variablerna kent och ann så att en beskriver en person med examen (GRADuated) och en utan.

Uppgift 5: Gör de första programutvecklingsstegen för att konstruera ett program som indenterar Modula program. Fundera först på problemet, sedan på en översiktlig lösning och slutligen på en mer detaljerad lösning.

4 Dynamiska datastrukturer, abstrakta datatyper

Uppgift 1: (a) Skriv en procedur som sätter in element i sorterad lista.

(b) Skriv en funktion som beräknar längden på en länkad lista.

(c) Skriv en funktion som samsorterar två sorterade listor.

(d) Skriv en procedur som lägger till en lista i slutet på en annan.

(e) Skriv en procedur som skriver ut en lista baklänges.

Uppgift 2: Skriv en modul som implementerar en \underline{abstrakt} datatyp för heltalsstack. Operationer:

init: nollställer stacken. empty: undersöker om stacken är tom. push: sätter in ett element först i stacken.

Institutionen för Datavetenskap ThomasH Övning

VT-94 INN01-b 13/4-94

pop: tar bort det första elementet från stacken.

top: ger det första elementet på stacken.

Stacken ska representeras med länkad lista.

Uppgift 3: Samma sak fast med fältrepresentation.

5 Dynamiska datastrukturer, filter.

Uppgift 1: (a) Skriv en funktion som beräknar höjden på ett binärt träd. (Höjden kan definieras som antalet noder i den längsta vägen från roten till ett löv.)

(b) Skriv en funktion som beräknar antalet löv i ett binärt träd.

Uppgift 2: Skriv en procedur som skriver ut informationen i noderna i ett binärt träd med besöksordningen inorder/postorder.

Uppgift 3: Samma sak fast radvis. (Först roten, sen rotens barn, sen rotens barnbarn, osv) Tips: En kö för träd kan vara bra att ha. (Detta är en svår uppgift.)

Uppgift 4: Skriv en funktion som jämför om två träd är lika, dvs samma struktur och samma värden i noderna.

Uppgift 5: Skriv ett program som (a) kopierar en textfil.

(b) kopierar en binärfil.

(c) lägger till ett element till en sorterad binärfil.