Lösungsvorschlag MiniKlausur 16/17

Bachelor Algorithmen und Datenstrukturen
1

Bitte gegenchecken und in die Klausursammlung übernehemen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Lösungsvorschlag MiniKlausur 16/17
Aufgabe 1 (Wissensfragen)

a) 2,3
b) 1,3
c) 1,4 → x = new long[y+1][z+1] => Speicherplatz O(yz); For each grey field on the pic there will be a recursive call => O(yz);

Aufgabe 2 Christkindlesmarkt

public class Christkindlesmarkt {
List<List> alle(List waren, long geld) {
List<List> llw = new ArrayList<>();

	if (waren.size() > 0 && geld > 0) { //if not - stop recursion
		Ware kopf = waren.get(0);
		
		//1) buy the first element from list waren - money is reduced
		if (kopf.preis <= geld){
			List<List<Ware>> llwMit = alle(waren,geld-kopf.preis); // Recursion - continue buying
			
			if (llwMit.size()==0){ //if there is nothing bought yet, create a new list
				llwMit.add(new ArrayList<Ware>());
			}
			
			for (List<Ware> l : llwMit){
				l.add(0,kopf);
				llw.add(l);
			}
		}
		
		//2) do not buy the first element from the list - one element less in the list waren
		waren.remove(0);
		List<List<Ware>> llwOhne = alle(waren,geld); //Recursion - one element out, not bought anything
		llw.addAll(llwOhne);
		waren.add(0,kopf); //(?) backtracking - pack the first element again
	}
	return llw;
}

}

Aufgabe 3: Trie

public class Trie {
Trie[] kind = new Trie[‘Z’ - ‘A’ + 1];
String wort;

// a)
void einfuegen(String s) {
	Trie akt = this;
	for (char c : s.toCharArray()) {
		if (c < 'A' || c > 'Z') {
			throw new IllegalArgumentException();
		}
		// if there is no childnode, create a new one
		if (akt.kind[c - 'A'] == null) { 
			akt.kind[c - 'A'] = new Trie();
		}
		akt = akt.kind[c - 'A']; // go to the childnode
	}
	akt.wort = s;
}

// b)
void ausgeben() {
	if (this.wort != null) {
		System.out.println(this.wort);
	}
	// recursively checking the wort of each child
	for (Trie k : this.kind) {
		if (k != null) {
			k.ausgeben();
		}
	}
}

}

Aufgabe 4 (ADT)

isX(PlayX(t,g),f):= f=g && !isO(t,g) || isX(t,f)
isX(PlayO(t,g),f):= isX(t,f)

tie(t) = all(t) && !winsX(t) && !winsO(t)

3

Du kannst das auch selbst ins Wiki einpflegen. Mit Foren-Account anmelden, unten links auf bearbeiten

1 „Gefällt mir“