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