Tölvunarfræði 2 - Vor 2012


Verkefni 12 - Sýnislausn

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 10. apríl fyrir kl 16:00

Dæmi 1 (2 stig) - Tætitafla með keðjum


Leysið dæmi 3.4.1 í bókinni.

Insert the keys E A S Y Q U T I O N in that order into an initially empty table of M = 5 lists, using separate chaining. Use the hash function 11*k % M to transform the kth letter of the alphabet into a table index.

Lausn:


i value
0 E, Y, T, O
1 A, U
2 Q
3
4 S, I, N

Dæmi 2 (1 stig) - Tætitafla með línulegri könnun


Leysið dæmi 3.4.10 í bókinni.

Insert the keys E A S Y Q U T I O N in that order into an initially empty table of size M = 16 using linear probing. Use the hash function 11*k % M to transform the kth letter of the alphabet into a table index. Redo this exercise for M = 10.

Hjálparforrit:


#include <stdio.h>
#include <string.h>

int main(void)
{
	char s[] = "EASYQUTION";
	int n = strlen(s);
	int M = 10;
	int i;

	for (i = 0; i < n; i++)
	{
		int h = s[i] - 'A' + 1;

		printf("%c = %-2d, index = %d\n", s[i], h, 11*h % M);
	}
}

Lausn fyrir M=16:


i value
0  
1 S
2  
3 Y
4 I
5 O
6  
7 E
8 U
9  
10 N
11 A
12 Q
13 T
14  
15  

Lausn fyrir M=10:


i value
0 T
1 A
2 U
3 I
4 N
5 E
6 Y
7 Q
8 O
9 S

Dæmi 3 (2 stig) - R-way trie


Leysið dæmi 5.2.3 í bókinni.

Draw the R-way trie that results when the keys: 

now is the time for all good people to come to the aid of
are inserted in that order into an initially empty trie (do not draw null links)

Lausn:


Dæmi 4 (2 stig) - Ternary search tries (TST)


Leysið dæmi 5.2.4 í bókinni.

Draw the TST that results when the keys: 

now is the time for all good people to come to the aid of
are inserted in that order into an initially empty TST.

Lausn:


Dæmi 5 (3 stig) - Verðtafla fyrir símaforskeyti


Úthlutun símanúmera til landa byggist á forskeytum. Til dæmis hefur Ísland forskeytið 354 en Svíþjóð forskeytið 46. Öll símanúmer sem byrja á 354 tilheyra Íslandi, en öll símanúmer sem byrja á 46 tilheyra Svíþjóð.

Úthlutun símanúmera innan landa byggist einnig á forskeytum. Þannig tilheyrir, til dæmis, 354558 Vodafone, 354560 Símanum, og 354770 Nova.

Eitt forskeyti getur líka verið undirforskeyti fyrir annað forskeyti. Til dæmis hefur USA alþjóðlega forskeytið 1 en Bermuda eyjarnar hafa forskeytið 1441. Símanúmerið 1-441-12345 tilheyrir því Bermuda en ekki USA.

Til að finna rétt forskeyti fyrir gefið númer þá þarf að finna lengsta forskeytið sem passar við númerið. Þetta heitir á ensku "longest prefix match" (lengsta forskeyti sem passar).

Hröð uppfletting á lengsta forskeyti er mikilvægt verkefni í fjarskiptum og kemur til dæmis fyrir í leiðarvísun (routing) í símstöðvum, gjaldfærslu símtala, leiðarvísun (routing) í IP netum og fleiru.

Símanetið byggist upp á mörgum samtengdum netum. Símafyrirtæki rekur sitt net og samtengist öðrum símafyrirtækjum sem reka sín net. Símtöl eru síðan send á milli fyrirtækja eftir þörfum.

Símafyrirtæki gefa út verðskrár fyrir öll forskeyti sem þeir eru tilbúnir að taka á móti. Þið eigið að skrifa forrit sem les slíka skrá og getur flett upp lengsta forskeyti fyrir símanúmer sem eru lesin af aðalinntaki.

Sækið eftirfarandi skrá: rates.csv, sem inniheldur uþb. 14 þúsund alþjóðleg forskeyti á eftirfarandi sniði:

  • forskeyti (prefix)
  • :
  • landskóði (country code)
  • :
  • símafyrirtæki (operator)
  • :
  • verð per mínútu í USD (rate per minute)

(Þetta er alvöru verðskrá frá stóru alþjóðlegu símafyrirtæki.)

Skrifið forrit sem virkar á eftirfarandi hátt. Það byrjar á því að lesa rates.csv inn í TST. Síðan les það símanúmer af aðalinntaki (eitt símanúmer per línu) og prentar út upplýsingar um lengsta forskeyti sem passar.

Dæmi um keyrslu: 

hhg@hhg:~/t2/V12$ java Rating
3548967121
35489 -> 354 : Iceland : Telecom Mobile : 0.1100
18008474096
1800 -> 1 : Usa : North America 8xx Term. : 0.0150
442084332000
44208 -> 44 : United Kingdom : London : 0.0060
3545885522
354 -> 354 : Iceland : Other : 0.0148
999999999
999999999 - Not found

Lausn - Rating.java


import java.util.Scanner;
import java.io.File;

public class Rating
{
	private static class Destination
	{
		String prefix;
		String countryCode;
		String countryName;
		String operator;
		double rate;

		public Destination(String prefix, String cc, String cn, String opname, double rate)
		{
			this.prefix = prefix;
			this.countryCode = cc;
			this.countryName = cn;
			this.operator = opname;
			this.rate = rate;
		}
	}

	public static void main(String[] args) throws Exception
	{
		TST<Destination> st = new TST<Destination>();

		Scanner scan = new Scanner(new File("./rates.csv"));

		while (scan.hasNextLine())
		{
			String line = scan.nextLine();
			String[] fields = line.split(":");

			double rate = Double.parseDouble(fields[4]);
			st.put(fields[0], new Destination(fields[0], fields[1], fields[3], fields[2], rate));
		}

		scan = new Scanner(System.in);

		while (scan.hasNext())
		{
			String dstnum = scan.next();

			String prefix = st.longestPrefixOf(dstnum);

			if (prefix == null || prefix.length() == 0)
			{
				System.out.printf("%s - Not found\n", dstnum);
				continue;
			}

			Destination dn = st.get(prefix);

			System.out.printf("%s -> %s : %s : %s : %.4f\n", dn.prefix, dn.countryCode, dn.countryName, dn.operator, dn.rate);
		}
	}
}