bild
Skolan för
elektroteknik
och datavetenskap

Labb 3

Deadline f�r labb 3 framg�r av schemat.

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 Syntaxanalys

Uppgift 3.1.1: Minir�knare (1p)

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

F�rslag till API:
double eval(string)

Problem-id hos Kattis: calculator.

3.2 Rationella tal

Uppgift 3.2.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.3 Modul�r aritmetik

Uppgift 3.3.2: 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.4: 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.4.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.4.2: System utan unik l�sning (2p)

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.5: 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.5.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.5.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.6: Primtalss�ll

Uppgift 3.6.1: Implementera primtalss�llning (1p)

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.

Copyright © Sidansvarig: Douglas Wikstr�m <dog@kth.se>
Uppdaterad 2008-10-21