Labb 3Deadline 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 SyntaxanalysUppgift 3.1.1: Minir�knare (1p)Skriv en metod som kan evaluera uttryck med +, - (un�rt och bin�rt) , *, /, (, ). F�rslag till API: Problem-id hos Kattis: calculator. 3.2 Rationella talUppgift 3.2.1: klass f�r rationella tal (1p)Implementera en klass f�r rationella tal. Klassen ska �tminstone ha st�d f�r:
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 aritmetikUppgift 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 ekvationssystemL�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:
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 restsatsenL�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) 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�llUppgift 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. |