a) 1, 2 und 3
b) 2 und 3
c) 1 und 2
d) 1 und 4
e) 1 und 3
f) 3 und 4
g) 1 und 4
h) 2 und 4
a)
b)
c)
d)
e)
Darstellung als Array: 28,24,13,21,19,3,7
f)
a)
class Cursor<E> implements ListIterator<E> { private class Node { private E v; // value (payload) private Node p, n; // previous, next } private Node prev, next; public void add(E e) { Node newN = new Node(); // new node becomes next newN.v = e; if(next != null){ next.p=newN; newN.n=next; } if(prev != null){ prev.n=newN; newN.p=prev; } next=newN; }
b)
public E previous() { if(prev != null){ E vTmp=prev.v; next=prev; prev=prev.p; return vTmp; } return null; }
c)
public void remove() { if(next != null){ next=next.n; // interne Verzeigerungen der Liste aktualisieren if(next != null){ next.p = prev; } if(prev != null){ prev.n = next; } } } }
a) (E, C), (C, B), (C, D), (D, A)
b)
c)
public void floidify(double[][] g){ int n = g.length; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ if(i != j && i != k && k != j){ // so sehen wir uns garantiert 3 paarweise versch Knoten an if(g[j][i] > 0 && g[i][k] > 0){ // es gibt eine Verbindung von Vj ueber Vi nach Vk if(g[j][k] == 0 || g[j][i]+g[i][k] < g[j][k]){ // bisherige Verbingung zwischen Vj und Vk gab es nicht oder kostet mehr als über Vi -> ersetze alte Verbindung durch neue g[j][k] = g[j][i]+g[i][k]; } } } } } } }
a)
getCol(Step(l), x, y) = NOT(getCol(l,x,y), falls x = getX(l) && y = getY(l) getCol(Step(l), x, y) = getCol(l,x,y), sonst
b)
getDir(Step(l)) = (getDir(l) + 3) % 4, falls getCol(l, getX(l), getY(l)) == false getDir(Step(l)) = (getDir(l) + 1) % 4, sonst
c)
getX(Step(l)) = getX(l) + 1, falls getDir(Step(l)) == 1 // + und - vertauscht? 1 = Westen, also nach links also -1 getX(Step(l)) = getX(l) - 1, falls getDir(Step(l)) == 3 //wie oben nur umgekehrt, auch in den Bildern zu sehen getX(Step(l)) = getX(l), sonst
d)
Beachte: Das Koordinatensystem ist nach unten geklappt, d.h. die y-Werte drehen sich bei den Blickrichtungen Norden/Sueden um. Wo steht das? Reine Interpretationssache. Das Raster im Bild ist nach oben auch positiv... ---------> x | | | y
public class LangtonAntJava{ boolean[][] raster = new boolean[4711][4242]; int x = 666, y = 666, d = 0; // Position und Richtung void step(){ if(raster[x][y]){ d = (d+1)%4; } else { d = (d+3)%4; } raster[x][y] = !raster[x][y]; if(d == 0){ y -= 1; } else if (d == 1){ x += 1; // muesste hier nicht x -= 1 stehen, da Blickrichtung nach Osten? Stimme dem zu. Autor kennt, wie bei c) schon erwähnt, die Himmelsrichtungen nicht. } else if (d == 2){ y += 1; } else if (d == 3){ x -= 1; // muesste hier nicht x += 1 stehen, da Blickrichtung nach Westen? } } }
class BinaereIntervallSuche { Intervall sucheIntervall(Intervall[] is, int v) { int a = 0, m, e = is.length - 1; // Anfang, Mitte, Ende while( e >= a ){ m=(a+e)/2; if(v <= is[m].max && v >= is[m].min) // volltreffer return is[m]; if(v > is[m].max){ // v liegt rechts a=m+1; }else{ // v liegt links e=m-1; } } return null; } }
private static void helfer(int p) { // p durchlaeuft alle Positionen in a // Basisfall a und b (fast) gleich gross erreicht? if (Math.abs(a.size() - b.size()) <= 1) { if (y == null && z == null // erste Loesung benoetigt // oder bessere Loesung gefunden || (Math.abs(abDiff) < Math.abs(yzDiff))) { // merke beste bisher gefundene Loesung: y = new LinkedList<>(a); z = new LinkedList<>(b); yzDiff = abDiff; } } else if (p < a.size()) { // kein Abbruch // Rekursion 1: p-ter Wert bleibt in a: helfer(p + 1); // Rekursion 2: p-ten Wert von a nach b verschieben: abDiff-=2*(a.get(p)); b.add(a.remove(p)); helfer(p); //sollte hier nicht auch p+1 stehen? sonst mach ich den gleichen Schritt nochmal // Nein, da ja der aktuelle Wert der Stelle P entfernt wird, wenn du jetzt p +1 machen würdest, würdest du einen Wert überspringen // Backtracking zur 2. Rekursion: abDiff+=2*b.get(b.size()- 1); a.add(p, b.remove(b.size() - 1)); } }