Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 21. febrúar fyrir kl 16:00
Skrifið forrit í C eða Java sem les A.txt (100.000 heiltölur í engri sérstakri röð) og B.txt (milljón heiltölur í vaxandi röð) og finnur öll pör af heiltölum úr sitthvorri skránni sem hafa summuna 12345.
Þið ættuð að finna nákvæmlega 25135 pör. Látið forritið skrifa út eina línu fyrir hvert par.
Dæmi:
hhg@hhg:~/t2/V6/d1$ java FindSum -467361 479706 -85591 97936 1815772 -1803427 324566 -312221 -1340997 1353342 1241995 -1229650 276593 -264248 1295098 -1282753 [...] -1096531 1108876 1179331 -1166986 286419 -274074 286419 -274074 -440184 452529 656460 -644115 656460 -644115 hhg@hhg:~/t2/V6/d1$
Skrifið tvær útgáfur. Eina útgáfu sem gengur línulega í gegnum A og leitar línulega í B og aðra útgáfu sem gengur línulega í gegnum A og leitar með helmingunarleit í B. Keyrið báðar útgáfurnar og látið tímamælinguna í lokin fylgja með kóðanum sem þið skilið. Munið að láta notkunarlýsingar fylgja með föllunum sem þið notið, þ.m.t. leitarföllunum.
Þið þurfið ekki að skila öllum kóðanum fyrir báðar útgáfurnar. Kóðinn sem þið skilið ætti að innihalda bæði leitarföllin og eini munurinn á útgáfunum ætti að vera á hvort fallið er kallað. Leitarföllin ættu semsagt að hafa sömu notkunarlýsingu og allur annar kóði ætti að vera eins.
Athugið: forritið á að telja tvítekningar. Þegar þið leitið í B þá nægir ekki að finna bara fyrstu töluna sem passar, þið verðið að skrifa og telja öll pör sem passa. Þið þurfið að velja afbrigði af helmingunarleit sem hentar í það verkefni.
Athugið: virknin í tengslum við að telja fjölda para ætti að vera alfarið í findSum fallinu og ekki í search/bsearch. Leitarföllin eiga bara að leita og skila leitarniðurstöðu, þau eiga ekki að telja fjölda para eða innihalda sértæka virkni sem tengist þessu eina verkefni.
import java.util.Scanner;
import java.util.Arrays;
import java.io.File;
import java.io.IOException;
public class FindSum
{
// Notkun: ?
// Fyrir: ?
// Eftir: ?
public static int search(int[] f, int i, int j, int x)
{
// Línuleg leit
}
// Notkun: ?
// Fyrir: ?
// Eftir: ?
public static int bsearch(int[] f, int i, int j, int x)
{
// Helmingunarleit
}
// Notkun: k = findSum(A, B, s);
// Fyrir: B er í vaxandi röð.
// Eftir: Búið er að prenta út öll pör
// (a,b) þar sem a \in A, b \in B
// og a + b = s.
// k er fjöldi para sem voru prentuð út.
public static int findSum(int[] A, int[] B, int s)
{
}
// Notkun: f = readInts(path, n);
// Fyrir: n > 0, path er slóð á læsilega skrá
// sem inniheldur heiltölur, eina per línu
// Eftir: Búið er að lesa n heiltölur úr skránni
// sem liggur undir slóðinni path og þær
// eru í fylkinu f í lesröð.
public static int[] readInts(String path, int n) throws IOException
{
Scanner scan = new Scanner(new File(path));
int[] f = new int[n];
int i = 0;
while (scan.hasNextInt())
{
f[i++] = scan.nextInt();
}
return f;
}
public static void main(String[] args) throws Exception
{
int[] A = readInts("A.txt", 100000);
int[] B = readInts("B.txt", 1000000);
long start = System.nanoTime();
int found = findSum(A, B, 12345);
long stop = System.nanoTime();
double duration = (stop-start) / 1000000.0;
System.out.printf("Found %d pairs\n", found);
System.out.printf("Search took %.2f ms\n", duration);
}
}
public class Vaxandi
{
// ------------------
// VAXANDI RÖÐ
// ------------------
// Notkun: k = leita1a(f,i,j,x);
// Fyrir: f[i..j-1] er í vaxandi röð
// Eftir: f[i..j-1] er óbreytt, i <= k <= j, og
// f[i..k-1] <= x < f[k..j-1]
//
// Ath. f[k] er fyrsta talan sem er > x,
// f[k-1] er síðasta talan sem er <= x.
static int leita1a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | <= x | óþekkt | > x |
// i p q j
int m = (p+q)/2;
if (f[m] <= x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | <= x | > x |
// i p j
// q
return p;
}
static int leita1b(double[] f, int i, int j, double x)
{
if (i == j) return i;
int m = (i+j)/2;
if (f[m] > x)
return leita1b(f,i,m,x);
else
return leita1b(f,m+1,j,x);
}
// ---
// Notkun: k = leita2a(f,i,j,x);
// Fyrir: f[i..j-1] er í vaxandi röð
// Eftir: f[i..j-1] er óbreytt, i-1 <= k <= j, og
// f[i..k] <= x < f[k+1..j-1]
//
// Ath. f[k+1] er fyrsta talan sem er > x,
// f[k] er síðasta talan sem er <= x.
static int leita2a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | <= x | óþekkt | > x |
// i p q j
int m = (p+q)/2;
if (f[m] <= x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | <= x | > x |
// i p j
// q
return p-1;
}
static int leita2b(double[] f, int i, int j, double x)
{
if (i == j) return i-1;
int m = (i+j)/2;
if (f[m] > x)
return leita2b(f,i,m,x);
else
return leita2b(f,m+1,j,x);
}
// ---
// Notkun: k = leita3a(f,i,j,x);
// Fyrir: f[i..j-1] er í vaxandi röð
// Eftir: f[i..j-1] er óbreytt, i <= k <= j, og
// f[i..k-1] < x <= f[k..j-1]
//
// Ath. f[k] er fyrsta talan í fylkinu sem er >= x,
// f[k-1] er síðasta talan sem er < x
static int leita3a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | < x | óþekkt | >= x |
// i p q j
int m = (p+q)/2;
if (f[m] < x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | < x | >= x |
// i p j
// q
return p;
}
static int leita3b(double[] f, int i, int j, double x)
{
if (i == j) return i;
int m = (i+j)/2;
if (f[m] >= x)
return leita3b(f,i,m,x);
else
return leita3b(f,m+1,j,x);
}
// ---
// Notkun: k = leita4a(f,i,j,x);
// Fyrir: f[i..j-1] er í vaxandi röð
// Eftir: f[i..j-1] er óbreytt, i-1 <= k <= j, og
// f[i..k] < x <= f[k+1..j-1]
//
// Ath. f[k+1] er fyrsta talan sem er >= x,
// f[k] er síðasta talan sem er < x
static int leita4a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | < x | óþekkt | >= x |
// i p q j
int m = (p+q)/2;
if (f[m] < x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | < x | >= x |
// i p j
// q
return p-1;
}
static int leita4b(double[] f, int i, int j, double x)
{
if (i == j) return i-1;
int m = (i+j)/2;
if (f[m] >= x)
return leita4b(f,i,m,x);
else
return leita4b(f,m+1,j,x);
}
public static void main(String[] args)
{
double[] f = {1,1,1,3,5};
assert leita1a(f,0,f.length,0.5) == 0;
assert leita1a(f,0,f.length,1) == 3;
assert leita1a(f,0,f.length,1.5) == 3;
assert leita1a(f,0,f.length,3) == 4;
assert leita1a(f,0,f.length,6) == 5;
assert leita1b(f,0,f.length,0.5) == 0;
assert leita1b(f,0,f.length,1) == 3;
assert leita1b(f,0,f.length,1.5) == 3;
assert leita1b(f,0,f.length,3) == 4;
assert leita1b(f,0,f.length,6) == 5;
assert leita2a(f,0,f.length,0.5) == -1;
assert leita2a(f,0,f.length,1) == 2;
assert leita2a(f,0,f.length,1.5) == 2;
assert leita2a(f,0,f.length,3) == 3;
assert leita2a(f,0,f.length,6) == 4;
assert leita2b(f,0,f.length,0.5) == -1;
assert leita2b(f,0,f.length,1) == 2;
assert leita2b(f,0,f.length,1.5) == 2;
assert leita2b(f,0,f.length,3) == 3;
assert leita2b(f,0,f.length,6) == 4;
assert leita3a(f,0,f.length,0.5) == 0;
assert leita3a(f,0,f.length,1) == 0;
assert leita3a(f,0,f.length,1.5) == 3;
assert leita3a(f,0,f.length,3) == 3;
assert leita3a(f,0,f.length,6) == 5;
assert leita3b(f,0,f.length,0.5) == 0;
assert leita3b(f,0,f.length,1) == 0;
assert leita3b(f,0,f.length,1.5) == 3;
assert leita3b(f,0,f.length,3) == 3;
assert leita3b(f,0,f.length,6) == 5;
assert leita4a(f,0,f.length,0.5) == -1;
assert leita4a(f,0,f.length,1) == -1;
assert leita4a(f,0,f.length,1.5) == 2;
assert leita4a(f,0,f.length,3) == 2;
assert leita4a(f,0,f.length,6) == 4;
assert leita4b(f,0,f.length,0.5) == -1;
assert leita4b(f,0,f.length,1) == -1;
assert leita4b(f,0,f.length,1.5) == 2;
assert leita4b(f,0,f.length,3) == 2;
assert leita4b(f,0,f.length,6) == 4;
}
}
public class Minnkandi
{
// ------------------
// MINNKANDI RÖÐ
// ------------------
// Notkun: k = leita1a(f,i,j,x);
// Fyrir: f[i..j-1] er í minnkandi röð
// Eftir: f[i..j-1] er óbreytt, i <= k <= j, og
// f[i..k-1] >= x > f[k..j-1]
//
// Ath. f[k] er fyrsta talan í fylkinu sem er < x,
// f[k-1] er síðasta talan sem er >= x.
static int leita1a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | >= x | óþekkt | < x |
// i p q j
int m = (p+q)/2;
if (f[m] >= x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | >= x | < x |
// i p j
// q
return p;
}
static int leita1b(double[] f, int i, int j, double x)
{
if (i == j) return i;
int m = (i+j)/2;
if (f[m] < x)
return leita1b(f,i,m,x);
else
return leita1b(f,m+1,j,x);
}
// ---
// Notkun: k = leita2a(f,i,j,x);
// Fyrir: f[i..j-1] er í minnkandi röð
// Eftir: f[i..j-1] er óbreytt, i-1 <= k <= j, og
// f[i..k] >= x > f[k+1..j-1]
//
// Ath. f[k+1] er fyrsta talan sem er < x,
// f[k] er síðasta talan sem er >= x.
static int leita2a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | >= x | óþekkt | < x |
// i p q j
int m = (p+q)/2;
if (f[m] >= x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | >= x | < x |
// i p j
// q
return p-1;
}
static int leita2b(double[] f, int i, int j, double x)
{
if (i == j) return i-1;
int m = (i+j)/2;
if (f[m] < x)
return leita2b(f,i,m,x);
else
return leita2b(f,m+1,j,x);
}
// ---
// Notkun: k = leita3a(f,i,j,x);
// Fyrir: f[i..j-1] er í minnkandi röð
// Eftir: f[i..j-1] er óbreytt, i <= k <= j, og
// f[i..k-1] > x >= f[k..j-1]
//
// Ath. f[k] er fyrsta talan sem er <= x,
// f[k-1] er síðasta talan sem er > x.
static int leita3a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | > x | óþekkt | <= x |
// i p q j
int m = (p+q)/2;
if (f[m] > x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | > x | <= x |
// i p j
// q
return p;
}
static int leita3b(double[] f, int i, int j, double x)
{
if (i == j) return i;
int m = (i+j)/2;
if (f[m] <= x)
return leita3b(f,i,m,x);
else
return leita3b(f,m+1,j,x);
}
// ---
// Notkun: k = leita4a(f,i,j,x);
// Fyrir: f[i..j-1] er í minnkandi röð
// Eftir: f[i..j-1] er óbreytt, i-1 <= k <= j, og
// f[i..k] > x >= f[k+1..j-1]
//
// Ath. f[k+1] er fyrsta talan sem er <= x,
// f[k] er síðasta talan sem er > x.
static int leita4a(double[] f, int i, int j, double x)
{
int p=i, q=j;
while (p != q)
{
// | > x | óþekkt | <= x |
// i p q j
int m = (p+q)/2;
if (f[m] > x)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | > x | <= x |
// i p j
// q
return p-1;
}
static int leita4b(double[] f, int i, int j, double x)
{
if (i == j) return i-1;
int m = (i+j)/2;
if (f[m] <= x)
return leita4b(f,i,m,x);
else
return leita4b(f,m+1,j,x);
}
public static void main(String[] args)
{
double[] f = {5,3,1,1,1};
assert leita1a(f,0,f.length,0.5) == 5;
assert leita1a(f,0,f.length,1) == 5;
assert leita1a(f,0,f.length,1.5) == 2;
assert leita1a(f,0,f.length,3) == 2;
assert leita1a(f,0,f.length,6) == 0;
assert leita1b(f,0,f.length,0.5) == 5;
assert leita1b(f,0,f.length,1) == 5;
assert leita1b(f,0,f.length,1.5) == 2;
assert leita1b(f,0,f.length,3) == 2;
assert leita1b(f,0,f.length,6) == 0;
assert leita2a(f,0,f.length,0.5) == 4;
assert leita2a(f,0,f.length,1) == 4;
assert leita2a(f,0,f.length,1.5) == 1;
assert leita2a(f,0,f.length,3) == 1;
assert leita2a(f,0,f.length,6) == -1;
assert leita2b(f,0,f.length,0.5) == 4;
assert leita2b(f,0,f.length,1) == 4;
assert leita2b(f,0,f.length,1.5) == 1;
assert leita2b(f,0,f.length,3) == 1;
assert leita2b(f,0,f.length,6) == -1;
assert leita3a(f,0,f.length,0.5) == 5;
assert leita3a(f,0,f.length,1) == 2;
assert leita3a(f,0,f.length,1.5) == 2;
assert leita3a(f,0,f.length,3) == 1;
assert leita3a(f,0,f.length,6) == 0;
assert leita3b(f,0,f.length,0.5) == 5;
assert leita3b(f,0,f.length,1) == 2;
assert leita3b(f,0,f.length,1.5) == 2;
assert leita3b(f,0,f.length,3) == 1;
assert leita3b(f,0,f.length,6) == 0;
assert leita4a(f,0,f.length,0.5) == 4;
assert leita4a(f,0,f.length,1) == 1;
assert leita4a(f,0,f.length,1.5) == 1;
assert leita4a(f,0,f.length,3) == 0;
assert leita4a(f,0,f.length,6) == -1;
assert leita4b(f,0,f.length,0.5) == 4;
assert leita4b(f,0,f.length,1) == 1;
assert leita4b(f,0,f.length,1.5) == 1;
assert leita4b(f,0,f.length,3) == 0;
assert leita4b(f,0,f.length,6) == -1;
}
}
Leysið dæmi 1.4.12 í bókinni.
Write a program that, given two sorted arrays of N int values, prints all elements that appear in both arrays, in sorted order. The running time of your program should be proportional to N in the worst case.
Ef sama talan kemur fyrir oftar en einu sinni í báðum fylkjunum þá á að prenta hana út eins oft og hún kemur fyrir í báðum fylkjunum. Ef það er kallað á fallið fyrir listana [1,2,2,3] og [1,2,2,2] þá ætti það að prenta út tölurnar 1, 2, 2.
Þið megið leysa verkefnið í C eða Java. Skrifið einnig prófunartilvik og sannfærið ykkur um að forritið sé að virka rétt. Látið notkunarlýsingar fylgja með öllum föllunum sem þið skrifið. Sýnið dæmi um keyrslu og úttak.
Skrifið forrit sem notar helmingunaraðferðina (e. bisection method) til að nálga lausn á f(x) = 0 fyrir eitthvað uppgefið fall f(x).
Nægjanlegt skilyrði fyrir því að það sé til núllstöð á bili [a,b] er að fallsgildið hafi mismunandi formerki í a og b, og að fallið sé samfellt á bilinu.
Klárið að útfæra beinagrindina í C eða Java. Notið lykkju til að leysa verkefnið og skrifið fastayrðingu fyrir hana. Sýnið dæmi um keyrslu og úttak.
interface Function
{
double evaluate(double x);
}
public class Bisect
{
// Notkun: r = bisect(f,p,q,eps);
// Fyrir: p<q, f(p)*f(q) <= 0, eps > 0.
// f er samfellt á bilinu [p,q]
// Eftir: p <= r <= q, til er z þ.a. |r-z| < eps
// og f(z)=0.
public static double bisect(Function f, double p, double q, double eps)
{
}
public static void main(String[] args)
{
Function f = new Function()
{
public double evaluate(double x)
{
return x*x - 2;
}
};
System.out.printf("sqrt(2) = %.4f\n", bisect(f, 1, 2, 0.0001));
}
}
hhg@hhg:~/t2/V6$ javac Bisect.java hhg@hhg:~/t2/V6$ java Bisect sqrt(2) = 1.4142 hhg@hhg:~/t2/V6$
#include <stdio.h>
// Notkun: r = bisect(f,p,q,eps);
// Fyrir: p<q, f(p)*f(q) <= 0, eps > 0.
// f er samfellt á bilinu [p,q]
// Eftir: p <= r <= q, til er z þ.a. |r-z| < eps
// og f(z)=0.
double bisect(double (*f)(double x), double p, double q, double eps)
{
}
double ft(double x)
{
return x*x - 2;
}
int main(void)
{
printf("sqrt(2) = %.4f\n", bisect(ft, 1, 2, 0.0001));
}
hhg@hhg:~/t2/V6$ make bisect clang bisect.c -o bisect hhg@hhg:~/t2/V6$ ./bisect sqrt(2) = 1.4142 hhg@hhg:~/t2/V6$
Skrifið forrit í C eða Java sem les orð af aðalinntaki og athugar hvort það er leyfilegt orð í Scrabble skv. ospd.txt (Official Scrabble Player's Dictionary)
Skrifið tvær útgáfur. Eina útgáfu sem notar línulega leit og aðra sem notar helmingunarleit. Keyrið báðar útgáfurnar með words.txt sem inntak og látið tímamælinguna í lokin fylgja með kóðanum sem þið skilið.
Þið þurfið ekki að skila öllum kóðanum fyrir báðar útgáfurnar. Kóðinn sem þið skilið ætti að innihalda bæði leitarföllin og eini munurinn á útgáfunum ætti að vera á hvort fallið er kallað. Leitarföllin ættu semsagt að hafa sömu notkunarlýsingu og allur annar kóði ætti að vera eins.
Látið forritið prenta út heildarfjölda orða sem það fann og fann ekki (sjá prófun fyrir neðan).
Klárið að útfæra beinagrindina í Java (eða skrifið hliðstætt forrit í C). Sýnið dæmi um keyrslu og úttak. Munið að láta notkunarlýsingar fylgja með föllunum sem þið notið, þ.m.t. leitarföllunum.
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Collections;
import java.io.IOException;
import java.io.File;
public class ScrabbleCheck
{
// Notkun: f = readLines(path);
// Fyrir: path er slóð á læsilega skrá
// Eftir: Búið er að lesa allar línur úr
// skránni sem liggur undir slóðinni
// path og þær eru í f í lesröð.
public static ArrayList<String> readLines(String path) throws IOException
{
ArrayList<String> lines = new ArrayList<String>();
Scanner scan = new Scanner(new File(path));
while (scan.hasNextLine())
{
String line = scan.nextLine().toLowerCase();
lines.add(line);
}
return lines;
}
// Notkun: ?
// Fyrir: ?
// Eftir: ?
public static int search(ArrayList<String> f, int i, int j, String x)
{
// Línuleg leit
}
// Notkun: ?
// Fyrir: ?
// Eftir: ?
public static int bsearch(ArrayList<String> f, int i, int j, String x)
{
// Helmingunarleit
}
public static void main(String[] args) throws Exception
{
ArrayList<String> whitelist = readLines("./ospd.txt");
Collections.sort(whitelist);
long start = System.nanoTime();
Scanner scan = new Scanner(System.in);
int found = 0;
int missing = 0;
while (scan.hasNext())
{
String word = scan.next().toLowerCase();
// ...
}
long stop = System.nanoTime();
double duration = (stop-start) / 1000000.0;
System.out.printf("%d words found, %d words missing\n", found, missing);
System.out.printf("%.2f milliseconds\n", duration);
}
}
hhg@hhg:~/t2/V6/d4$ java ScrabbleCheck < words 36516 words found, 62052 words missing 203.00 milliseconds hhg@hhg:~/t2/V6/d4$