bild
Skolan för
elektroteknik
och datavetenskap

Labb 3

Deadline för labb 3 är fredag 17 november kl. 08:00.

Läs igenom labbinstruktionerna innan ni börjar.

Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För mer detaljer se Labb 1.

3.1 Rationella tal

Uppgift 3.1.1: klass för rationella tal (1p)

Implementera en klass för rationella tal. Klassen ska åtminstone ha stöd för:

  • Vanliga aritmetiska operationer: addition, subtraktion, multiplikation, division.
  • Jämförelser.
  • Inläsning och utskrift

Klassen blir mer användbar om man kan välja heltalstyp för täljare och nämnare med hjälp av templates/generics, men det är inte ett krav att implementera detta.

Ett tips är att se till att lagra de rationella talen i en normaliserad form.

Problem-id hos Kattis: rationalarithmetic.

3.2 Modulär aritmetik

Uppgift 3.2.1: Implementera modulär aritmetik (1p)

Implementera modulär aritmetik, d.v.s. addition, subtraktion, multiplikation och division mod n. Det är inte tillåtet att använda färdiga paket eller klasser, exempelvis java.math.BigInteger som tillhandahåller en färdig implementation.

Tänk på att %-operatorn inte beter sig som man vill för negativa tal.

Problem-id hos Kattis: modulararithmetic.

3.3: Linjära ekvationssystem

Lösningarna i detta avsnitt blir mer användbara om man kan välja koefficienttyp, exempelvis rationella tal, flyttal eller heltal modulo p, med hjälp av templates/generics, men det är inte ett krav att implementera detta.

3.3.1: Lösa system med unik lösning (1p)

Implementera en rutin för att lösa linjära ekvationssystem. Med andra ord: lös ekvationen A · x = b, där A är en n×n-matris och b är en n×1-vektor.

Om ekvationssystemet saknar unik lösning (d.v.s. om matrisen A är singulär) ska detta detekteras. Det finns två fall att skilja på: system med mer än en lösning och system som saknar lösning.

Problem-id hos Kattis: equationsolver.

3.3.1: System utan unik lösning (1p)

Lös ut så många variabler som möjligt, även om ekvationssystemet är underbestämt. T.ex., givet systemet:

x1 -2·x2 = 3
x1 -4·x2 = 6
x1 -2·x2 +x3 = 4

kan vi lösa ut x3 = 1, emedan x1 och x2 inte kan lösas ut. Om systemet saknar lösning ska det detekteras.

Problem-id hos Kattis: equationsolverplus.

3.4: Kinesiska restsatsen

Lösningarna i detta avsnitt blir mer användbara om man kan välja heltalstyp med hjälp av templates/generics, men det är inte ett krav att implementera detta.

Uppgift 3.4.1: Relativt prima moduli (1p)

Implementera en funktion som löser ekvationssystemet

x = a (mod m)
x = b (mod n)

där m och n är relativt prima. Lösaren ska returnera den unika lösning x som uppfyller 0 ≤ x < n · m.

Problem-id hos Kattis: chineseremainder.

Uppgift 3.4.2: Moduli med gemensamma faktorer (1p)

Implementera en funktion som löser ekvationssystemet ovan även när m och n inte nödvändigtvis är relativt prima. Observera att det i detta fall kan vara så att det saknas en lösning; detta ska hanteras.

Det x som hittas ska uppfylla 0 ≤ x < n · m / gcd(m,n).

Problem-id hos Kattis: generalchineseremainder.

3.5: Primtalssåll

Uppgift 3.5.1: Implementera primtalssållning (2p)

Implementera Erathostenes såll för att hitta alla primtal upp till en gräns n. Sållet kan t.ex. implementeras som en klass där konstruktorn tar n som parameter, och som sedan i konstant tid kan svara på frågor om huruvida ett tal mellan 0 och n är ett primtal eller inte.

Obs, er implementation måste vara både minnes- och tidseffektiv!

Problem-id hos Kattis: primesieve.

3.6 Syntaxanalys

Uppgift 3.6.1: Miniräknare (1p)

Skriv en metod som kan evaluera utryck med +, - (unärt och binärt) , *, /, (, ).

Förslag till API:
double eval(string)

Problem-id hos Kattis: calculator.

Copyright © Sidansvarig: Mikael Goldmann <migo@kth.se>
Uppdaterad 2006-11-02