Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch Miniklausur WS 2019/20   (Übersicht)

Dies ist eine alte Version des Dokuments!


Lösungsversuch Miniklausur WS 2019/20

Aufgabe 3 (Backtracking)

a)

//counts number of chars in ws
	int countChars(List<String> ws) {
		int cnt = 0;
		if(ws == null) return cnt;
		for(String wort : ws) {
			cnt += wort.length();
		}
		return cnt;
	}

b)

        boolean containsAll(List<String> ws) {
		boolean [] chars = new boolean['z' - 'a' + 1];
		int idxOffset = 'a';
		if(ws == null) return false;
		// first pass through ws, toggle all found chars
		for(String wort : ws) {
			for(int i = 0; i< wort.length(); i++) {
				String wortKlein = wort.toLowerCase();
				chars[wortKlein.charAt(i) - idxOffset] = true;
			}
		}
		boolean all = true;
		//second pass: Go through chars array and see if anything still untoggled
		// --> not all chars contained
		for(int i = 0; i < chars.length; i++) {
			if(!chars[i]) all = false;
		}
		return all;
	}

c)

// helper method : returns null if both null otherwise shorter of two lists
	List<String> better(List<String> a, List<String> b) {
		if(a != null && b != null) {
			int aCnt = countChars(a);
			int bCnt = countChars(b);
			return aCnt <= bCnt? a : b;
		} else if(a == null && b == null) {
			return null;
		} else {
			return a == null ? b : a;
		}
	}
 
	List<String> getOptimal(List<String> ws) {
                 return helper(ws, 0, new LinkedList<>());
	}
 
        List<String> helper(List<String> ws, int i, List<String> coll) {
		if(containsAll(coll)) {
			return new LinkedList<>(coll);
		} else if (i < ws.size()){
			List<String> collWith = new LinkedList<>(coll); // clone
			List<String> resWith, resWithout;
			//choose
			String word = ws.get(i);
			collWith.add(word);
			//explore
			resWith = helper(ws, i+1, collWith);
			resWithout = helper(ws, i+1 , coll);
			return better(resWith, resWithout);
		}
		return null;
	}