verschachtelte Rekursion
public static int g(int n) { if (n == 1) return 1; return 1 + g(n - g(g(n - 1))); } }
public static int gMem(int n) { assert n >= 1; return gMH(n, new int[n + 1]); // m[0] is left unused } public static int gMH(int n, int[] m) { assert n >= 1; if (n <= 1) { return 1; } else if (m[n] == 0) { m[n] = 1 + gMH(n - gMH(gMH(n - 1, m), m), m); } else { return m[n]; } return m[n]; }
static int gDP(int n) { assert n >= 1; int[] m = new int[n + 1]; // m[0] is left unused m[1] = 1; for (int k = 2; k <= n; k++) { m[k] = 1 + m[k - m[m[k - 1]]]; } return m[n]; }
1,2,6,8,4,12,14,16,19,10
4,12,6,14,16,10,8,22,20,18
public class Aufgabe3 { public static void main(String[] args) { LinkedList<Integer> l1 = new LinkedList<Integer>(Arrays.asList(2, 3, 30, 90, 120, 240, 511)); LinkedList<Integer> l2 = new LinkedList<Integer>(Arrays.asList(1, 3, 12, 32, 90, 125, 240)); List<Integer> e = maxPartSumList(l1, l2); System.out.println(e); } // a static List<Integer> subListHead(List<Integer> one, int lastIndex) { // falls LastIndex letzter Eintrag ist draf man nicht mit +1 die Liste erstellen return (lastIndex < one.size() ? one.subList(0, lastIndex + 1) : one.subList(0, lastIndex)); } // returns the values from ’one’ starting immediately after lastIndex static List<Integer> subListTail(List<Integer> one, int lastIndex) { return one.subList(lastIndex + 1, one.size()); } // b private static int partSum(List<Integer> part) { int r = 0; for (int i : part) { r += i; } return r; } // c private static List<List<Integer>> split(List<Integer> one, List<Integer> two) { List<List<Integer>> r = new LinkedList<>(); for (int v : two) { int idx = one.indexOf(v); if (idx != -1) { r.add(subListHead(one, idx)); List<Integer> neu = subListTail(one, idx); one = new LinkedList<>(neu); } } // falls one groesser two, ist one noch nicht komplett leer und muss noch an r // angefügt werden if (!one.isEmpty()) { r.add(one); } return r; } // d private static List<Integer> maxPartSumList(List<Integer> one, List<Integer> two) { List<Integer> r = new LinkedList<>(), oneP, twoP; Iterator<List<Integer>> oneI = split(one, two).iterator(); Iterator<List<Integer>> twoI = split(two, one).iterator(); while (oneI.hasNext() && twoI.hasNext()) { // wichtig .next nur einmal in while schleife aufrufen, // da mit jedem .next der Iterator eins weiter geht!!! List<Integer> eins = oneI.next(); List<Integer> zwei = twoI.next(); int sumOne = partSum(eins); int sumTwo = partSum(zwei); if (sumOne >= sumTwo) { r.addAll(eins); } else { r.addAll(zwei); } } // falls noch letzter Abschnitt hinzugefügt werden muss if (oneI.hasNext()) { r.addAll(oneI.next()); } if (twoI.hasNext()) { r.addAll(twoI.next()); } return r; } }
boolean isStronglyConnected(Graph<E> g) { Set<E> allNodes = g.allNodes(); for (E start : allNodes) { LinkedList<E> visited = new LinkedList<>(), queue = new LinkedList<>(); queue.add(start); while (!queue.isEmpty()) { E akt = queue.poll(); // wenn aktueller Knoten quelle ist dann kein zusamenhängender Graph if (preds(akt).isEmpty()) { return false; } if (!visited.contains(akt)) { visited.add(akt); List<E> nachfolger = succs(akt); if (nachfolger.isEmpty()) { // aktueller Knoten ist Senke, kann kein stark zusammenhängeder graph sein return false; } for (E i : nachfolger) { queue.add(i); } }//visitedAbfrage schließt }//while schießt if(visited.size()!=allNodes.size()){ return false; // abfrage ist wichtig, weil es kann sein, dass zwei Knoten gegenseitig auf sich zeigen, damit haben sie beide Vor und Nachfolger aber die anderen Knoten werden nicht erreicht } }//forschleife schließt return true; }
boolean hasEulerCircuit(Graph<E> g) { Set<E> allNodes = g.allNodes(); for(E akt : allNodes) { List<E> vor = preds(akt); List<E> nach = succs(akt); if(vor.size() != nach.size()) { return false; } } return isStronglyConnected(g); }
List<E> euler(Graph<E> g, E node) { LinkedList<E> stack = new LinkedList<>(), euler = new LinkedList<>(); stack.add(node); while(!stack.isEmpty()) { E akt = stack.peek(); //nicht rauslöschen!!! List<E> nach = succs(akt); if(nach.isEmpty()) { //keine nachfolger = Blattknoten -> zu Euler hinzu euler.addFirst(akt); //vorne anfügen stack.pop(); }else { for(E e : nach) { stack.push(e); } //besuchte Kante löschen g.removeEdge(akt,stack.peek()); } } return euler; }
Union(Empty,s2) = s2 Union(add(s2,e),s2)= Add(unision(s1,s2),e)
ContainsAll(s1,Empty) = true containsAll(Empty,s2) = false containsAll(s1,Add(s2,e)) = ContainsAll(s1,s2) && contains (s1,e)
costSum(Create) = 0 CostSum(Append(l,s,c)) = c+costsum(l)
setUnion(Create) = Empty setUnion(Append(l,s,c)) = union(S,setUnion(l))
sCH(Create, u, accu) = ... ... accu falls containsAll (setUnion(accu), u) ... create sonst sCH(Append(l,s,c),u,accu= ... ... sCH(l,u,better(Append(accu,s,c),accu))
String getVerticalPrefix(int r, int c) { if(r<0 || g[r][c]=='#' || r>= g.length || c >= g[r].length) { return ""; }else { return g[r][c]+getVerticalPrefix(r-1,c); } }
List<String> consumeV(int r, int c, String w) { List<String> wsPV = new LinkedList<>(); // completed by inserting w for (int i = c; i < c + w.length(); i++) { String vp = getVerticalPrefix(r,i); if(wsV.contains(vp)) { wsV.remove(vp); wsPV.add(vp); } } return wsPV; }
boolean solve() { return helper(0, 0); // will always return true } boolean helper(int r, int c) { // traverse g row by row and left to right if(wsH.isEmpty()) { return true; } else if(c>g[r].length) { // ende der Zeile return helper(r+1,0); }else if(g[r][c] =='#') { //worttrenner return helper(r,c+1); } // try placing each remaining w from wsH at g[r][c] boolean[] cpH; // result from placeH List<String> wsPV; // result from consumeV for (int i = 0; i < wsH.size(); i++) { String w = wsH.remove(i); if(canPlace(r,c,w)) { cpH = placeH(r,c,w); wsPV = consumeV(r,c,w); if(helper(r,c+w.length())) { return true; } //keine Lösung, backtrack unPlace(r,c,cpH); wsV.addAll(wsPV); // consume loescht das Wort in wsV und speichert es in wsPV, das muss zurückkoppiert werden wsH.add(w); } } return false; }