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: k = search(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
public static int search(int[] f, int i, int j, int x)
{
for (int k = i; k < j; k++)
{
if (f[k] >= x)
return k;
}
return j;
}
// Notkun: k = bsearch(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
public static int bsearch(int[] f, int i, int j, int 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;
}
// 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)
{
int found = 0;
for (int i = 0; i < A.length; i++)
{
int diff = s - A[i];
// Línuleg leit
//int k = search(B, 0, B.length, diff);
// Helmingunarleit
int k = bsearch(B, 0, B.length, diff);
while (k < B.length && B[k] == diff)
{
System.out.printf("%d %d\n", A[i], B[k]);
found++;
k++;
}
}
return found;
}
// 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);
}
}
hhg@hhg:~/t2/V6/d1$ java FindSum -467361 479706 -85591 97936 1815772 -1803427 324566 -312221 -1340997 1353342 1241995 -1229650 276593 -264248 1295098 -1282753 -972729 985074 -350068 362413 [...] 380155 -367810 -1096531 1108876 1179331 -1166986 286419 -274074 286419 -274074 -440184 452529 656460 -644115 656460 -644115 Found 25135 pairs Search took 2557.01 ms hhg@hhg:~/t2/V6/d1$
hhg@hhg:~/t2/V6/d1$ java FindSum -467361 479706 -85591 97936 1815772 -1803427 324566 -312221 [...] 286419 -274074 286419 -274074 -440184 452529 656460 -644115 656460 -644115 Found 25135 pairs Search took 28673.92 ms hhg@hhg:~/t2/V6/d1$
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.
public class PrintEqual
{
// Notkun: printEqual(A, B);
// Fyrir: A og B eru í vaxandi röð
// Eftir: Búið að prenta út allar heiltölur
// sem koma fyrir í báðum fylkjunum í
// vaxandi röð.
// Ef sama heiltalan kemur fyrir oftar
// en einu sinni í báðum fylkjunum þá
// er hún prentuð út eins oft og hún
// kemur fyrir í þeim báðum.
public static void printEqual(int[] A, int[] B)
{
int i = 0;
int j = 0;
while (i < A.length && j < B.length)
{
if (A[i] == B[j])
{
System.out.println(A[i]);
i++;
j++;
}
else if (A[i] < B[j])
i++;
else if (A[i] > B[j])
j++;
}
}
public static void main(String[] args)
{
int[] A = {1,2,4,4,10,15};
int[] B = {0,1,2,4,4,10};
System.out.println("Expected output: 1 2 4 4 10");
printEqual(A, B);
}
}
hhg@hhg:~/t2/V6/d2$ java PrintEqual Expected output: 1 2 4 4 10 1 2 4 4 10 hhg@hhg:~/t2/V6/d2$
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)
{
double a = p, b = q;
while (b-a >= eps)
{
// p <= a <= b <= q
// f(a)*f(b) <= 0
double m = (a+b)/2.0;
if (f.evaluate(a)*f.evaluate(m) <= 0)
b = m;
else
a = m;
}
return a;
}
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 a = p, b = q;
while (b-a >= eps)
{
// p <= a <= b <= q
// f(a)*f(b) <= 0
double m = (a+b)/2.0;
if (f(a)*f(m) <= 0)
b = m;
else
a = m;
}
return a;
}
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: k = search(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
public static int search(ArrayList<String> f, int i, int j, String x)
{
for (int k = i; k < j; k++)
{
if (f.get(k).compareTo(x) >= 0)
return k;
}
return j;
}
// Notkun: k = bsearch(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
public static int bsearch(ArrayList<String> f, int i, int j, String x)
{
int p=i, q=j;
while (p != q)
{
// | < x | óþekkt | >= x |
// i p q j
int m = (p+q)/2;
if (f.get(m).compareTo(x) < 0)
p = m+1;
else
q = m;
}
// Fastayrðing gildir og p==q:
//
// | < x | >= x |
// i p j
// q
return p;
}
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();
// Línuleg leit
// int k = bsearch(whitelist, 0, whitelist.size(), word);
// Helmingunarleit
int k = bsearch(whitelist, 0, whitelist.size(), word);
if (k >= 0 && k < whitelist.size() && whitelist.get(k).equals(word))
found++;
else
missing++;
}
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$
hhg@hhg:~/t2/V6/d4$ java ScrabbleCheck < words 36516 words found, 62052 words missing 17153.65 milliseconds hhg@hhg:~/t2/V6/d4$