Tölvunarfræði 2 - Vor 2012


Verkefni 6 - Sýnislausn


Dæmi 1 (2 stig)


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.


Lausn - FindSum.java


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);
	}
}

Prófun - Helmingunarleit


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$ 

Prófun - Línuleg leit


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$ 

Dæmi 2 (2 stig)


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.


Lausn - PrintEqual.java


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);
	}
}

Prófun


hhg@hhg:~/t2/V6/d2$ java PrintEqual
Expected output: 1 2 4 4 10
1
2
4
4
10
hhg@hhg:~/t2/V6/d2$ 

Dæmi 3 (3 stig)


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.


Lausn fyrir Java - Bisect.java


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));
	}
}

Prófun


hhg@hhg:~/t2/V6$ javac Bisect.java
hhg@hhg:~/t2/V6$ java Bisect
sqrt(2) = 1.4142
hhg@hhg:~/t2/V6$ 

Lausn fyrir C - bisect.c


#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));
}

Prófun


hhg@hhg:~/t2/V6$ make bisect
clang     bisect.c   -o bisect
hhg@hhg:~/t2/V6$ ./bisect
sqrt(2) = 1.4142
hhg@hhg:~/t2/V6$ 

Dæmi 4 (3 stig)


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.


Beinagrind fyrir Java - ScrabbleCheck.java


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);
	}
}

Prófun - Helmingunarleit


hhg@hhg:~/t2/V6/d4$ java ScrabbleCheck < words 
36516 words found, 62052 words missing
203.00 milliseconds
hhg@hhg:~/t2/V6/d4$ 

Prófun - Línuleg leit


hhg@hhg:~/t2/V6/d4$ java ScrabbleCheck < words
36516 words found, 62052 words missing
17153.65 milliseconds
hhg@hhg:~/t2/V6/d4$