a) 1 und 3
b) 2 und 3
c) 2 || Ziemlich sicher, dass auch 1 richtig ist.
d) 3
e) 1 und 4
f) 2 und 4
g) 2 (achtung, falsch: Folgendes beachten)
a) Liste
b) (P)→ entspricht dem Pfeil mit P und (S) dem Pfeil mit S
<T> int suche(T[] ts, T t, Comparator<T> c1, Comparator<T> c2){ int a=0, m, z=ts.length -1; //Anfang, Mitte, Ende while(z >= a){ m= (a+z)/2; if(c1.compare(t, ts[m]) < 0){ z=m-1; }else if(c1.compare(t, ts[m]) == 0){ if(c2.compare(t, ts[m]) < 0){ z=m-1; }else if(c2.compare(t, ts[m]) == 0){ return m; }else{ a=m+1; } }else { a=m+1; } } return -1; }
a) Min Heap
b) ⇒ Min-Halde
2 | 6 | 3 | 7 | 10 | 5 | 4 | 8 | 9 | 12 | 11 |
---|
c) ⇒ Min-Halde
0 | 2 | 1 | 7 | 6 | 3 | 4 | 8 | 9 | 10 | 11 | 12 | 5 |
---|
a)
L * | A1 | B1 | F | A2 | B2 |
---|---|---|---|---|---|
A1 | L* | B1 | F | A2 | B2 |
A1 | B1 | L* | F | A2 | B2 |
A1 | B1 | F | L* | A2 | B2 |
A1 | A2 | B1 | F | L* | B2 |
A1 | A2 | B1 | B2 | F | L* |
void sortierenDurchEinfuegen(String[] a) { String tmp; for (int n = 1; n < a.length; n++) { tmp = a[n]; // entnommenes Element merken int i = n - 1; while (i >= 0 && tmp.compareTo(a[i]) < 0) { a[i + 1] = a[i]; i--; } a[i + 1] = tmp; // entnommenes Element // einsetzen } }
a)
b) Quelle
long a(int n) { if (n <= 1) { // Basisfall: return 1; } else { // Rekursion: long an = a(n-1); for(int i = 1; i < n; i++){ an+= a(i)*a(n-i); } return an; } }
c)
long aDP(int n){ if(mem == null || n >= mem.length){ // Bemerkung: n > mem.length reicht, da mem mit n+1 initialisiert wird long[] oldMem=mem; mem=new long[n+1]; if(oldMem != null){ for(int i=0; i < oldMem.length;i++) mem[i]=oldMem[i]; } } if(n <= 1){ mem[n]=1; }else if(mem[n] == 0){ mem[n]=aDP(n-1); for(int i=1; i<n; i++) mem[n] += aDP(i)*aDP(n-i); } return mem[n]; }
a)
void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { if (!bes.contains(k)) { verb.add(k); bes.add(k); for (int i = 0; i < am[k].length; i++) { if (am[k][i]) { sammle(am, i, verb, bes); } } for (int i = 0; i < am.length; i++) { if (am[i][k]) { sammle(am, i, verb, bes); } } } }
b)
List<Set<Integer>> mszt(boolean[][] am) { // Ergebnisliste: List<Set<Integer>> ergebnis = new LinkedList<>(); // Menge besuchter Knoten: Set<Integer> bk = new HashSet<>(); // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: for (int k = 0; k < am.length; k++) { if (!bk.contains(k)) { // falls k noch nicht besucht => sammle mit k verbundene Knoten Set<Integer> verb = new HashSet(); sammle(am, k, verb, bk); ergebnis.add(verb); //einfacher waere hier statt den letzten drei zeilen folgendes: //sammle(am, k, ergebnis.get(k), bk); } } return ergebnis; }
c)
void itg(boolean[][] am, Set<Integer> vs) { for (int i = 0; i < am.length; i++) { for (int j = 0; j < am.length; j++) { if (am[i][j]) { if (!vs.contains(i) || !vs.contains(j)) { // es muss sowohl x als auch y in vs enthalten sein am[i][j] = false; // der Graph ist gerichtet, daher reicht die Betrachtung an einer Stelle } } } } } // alte Loesung: void itg(boolean[][] am, Set<Integer> vs) { for (int i = 0; i < am.length; i++) { for (int j = 0; j < am.length; j++) { if (am[i][j]) { if (!(vs.contains(i) && vs.contains(j))) { am[i][j] = false; am[j][i] = false; } } } } }
Code zum selber testen:
public static void main(String[] args){ //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph GraphWS15 g = new GraphWS15(); boolean[][] am = {{false, true, false, true, false, false}, {false, false, false, true, false, false}, {false, false, false, false, true, false}, {false, true, false, false, false, false}, {false, false, false, false, false, false}, {false, false, false, false, false, false}}; //Set<Integer> verb = new HashSet(); List<Set<Integer>> n = g.mszt(am); System.out.println(n.size()); System.out.println(n.get(0).size()); System.out.println(n.get(1).size()); System.out.println(n.get(2).size()); } }
a)
b)
c)
false sonst