Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
ffprog:ffprogjava2016:soiaufgben [2016/09/11 22:14] Ivo Blöchliger [CableCar] |
ffprog:ffprogjava2016:soiaufgben [2016/10/11 13:00] Ivo Blöchliger [Tunnel] |
||
---|---|---|---|
Line 37: | Line 37: | ||
=== Teilaufgabe 3 === | === Teilaufgabe 3 === | ||
+ | **Achtung: | ||
* {{ : | * {{ : | ||
+ | |||
+ | <hidden Lösungsvorschlag in Java> | ||
+ | <code java> | ||
+ | public static void aufgabe3() throws IOException { | ||
+ | Path datei = Paths.get(" | ||
+ | // Speicher für die Ausgabe | ||
+ | ArrayList< | ||
+ | try (Scanner scanner = new Scanner(Files.newInputStream(datei))) { | ||
+ | int anzahlFaelle = scanner.nextInt(); | ||
+ | for (int fall=0; fall< | ||
+ | int maximum = 2; | ||
+ | int m = scanner.nextInt(); | ||
+ | System.out.println(m); | ||
+ | int erster = scanner.nextInt(); | ||
+ | int letzter = scanner.nextInt(); | ||
+ | int d = letzter-erster; | ||
+ | int anzahl = 2; | ||
+ | for (int j=2; j<m; j++) { | ||
+ | int aktueller = scanner.nextInt(); | ||
+ | // | ||
+ | if (aktueller-letzter!=d) { // Mit letztem Masten vergleichen | ||
+ | d = aktueller-letzter; | ||
+ | anzahl = 2; | ||
+ | } else { | ||
+ | anzahl++; | ||
+ | if (anzahl > maximum) { | ||
+ | maximum = anzahl; | ||
+ | } | ||
+ | } | ||
+ | letzter = aktueller; | ||
+ | } | ||
+ | lines.add(String.format(" | ||
+ | } | ||
+ | } | ||
+ | // Einzeiler, das eine Liste von Strings in eine Datei schreibt. | ||
+ | Files.write(Paths.get(" | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | </ | ||
=== Teilaufgabe 4 === | === Teilaufgabe 4 === | ||
* {{ : | * {{ : | ||
- | Der " | + | Der " |
+ | |||
+ | Ein " | ||
+ | |||
+ | ==== Tunnel ==== | ||
+ | Aufgabentext: | ||
+ | |||
+ | * $O(n)$ Lösung: http:// | ||
+ | |||
+ | === Aufgabe 1 === | ||
+ | * {{ : | ||
+ | |||
+ | === Aufgabe 2 === | ||
+ | |||
+ | * {{ : | ||
- | Ein "dynamische Programmierung"-Algorithmus | + | === Aufgabe 3 === |
+ | Anstatt einer Instanz-Datei (ca.0.5GB) gibt es hier einen Java-Code, der eine Instanz-Datei generiert: | ||
+ | <code java> | ||
+ | public static void generate(String fileName, int cases, int maxN, int maxH, int seed) throws IOException { | ||
+ | ArrayList< | ||
+ | lines.add(String.format("%d",cases)); | ||
+ | Random r = new Random(seed); | ||
+ | for (int c=0; c<cases; c++) { | ||
+ | int n = r.nextInt(maxN-4)+5; | ||
+ | lines.add(String.format(" | ||
+ | List< | ||
+ | Collections.sort(bounds); | ||
+ | int minH = r.nextInt(maxH/ | ||
+ | System.out.println(" | ||
+ | int heights[][] = new int[2][n]; | ||
+ | for (int i=0; i<n; i++) { | ||
+ | int x = (i> | ||
+ | heights[1][i] = r.nextInt(x); | ||
+ | heights[0][i] = r.nextInt(maxH-x)+x+1; | ||
+ | } | ||
+ | StringBuilder sb = new StringBuilder(); | ||
+ | for (int j=0; j<2; j++) { | ||
+ | for (int i=0; i<n; i++) { | ||
+ | sb.append(heights[j][i]); | ||
+ | if (i<n-1) { | ||
+ | sb.append(" | ||
+ | } | ||
+ | } | ||
+ | lines.add(sb.toString()); | ||
+ | sb = new StringBuilder(); | ||
+ | } | ||
+ | } | ||
+ | Files.write(Paths.get(fileName), | ||
+ | System.out.println(" | ||
+ | } | ||
+ | </ | ||
+ | Aufruf mit | ||
+ | <code java> | ||
+ | generate(" | ||
+ | </ | ||
+ | Für diese Parameter sieht die Lösung wie folgt aus: | ||
+ | <code txt> | ||
+ | Case #1: 54553 | ||
+ | Case #2: 118568 | ||
+ | Case #3: 42236 | ||
+ | Case #4: 95017 | ||
+ | Case #5: 392495 | ||
+ | Case #6: 23351 | ||
+ | Case #7: 214369 | ||
+ | Case #8: 207164 | ||
+ | Case #9: 80147 | ||
+ | Case #10: 101236 | ||
+ | Case #11: 29947 | ||
+ | Case #12: 272675 | ||
+ | Case #13: 11311 | ||
+ | Case #14: 568669 | ||
+ | Case #15: 74155 | ||
+ | Case #16: 36411 | ||
+ | Case #17: 98517 | ||
+ | Case #18: 118678 | ||
+ | Case #19: 579076 | ||
+ | Case #20: 364181 | ||
+ | Case #21: 784906 | ||
+ | Case #22: 10987 | ||
+ | Case #23: 92835 | ||
+ | Case #24: 208998 | ||
+ | Case #25: 304626 | ||
+ | Case #26: 130612 | ||
+ | Case #27: 316250 | ||
+ | Case #28: 88649 | ||
+ | Case #29: 99034 | ||
+ | Case #30: 256000 | ||
+ | Case #31: 107054 | ||
+ | Case #32: 178513 | ||
+ | Case #33: 226822 | ||
+ | Case #34: 64840 | ||
+ | Case #35: 48131 | ||
+ | Case #36: 4544 | ||
+ | Case #37: 27783 | ||
+ | Case #38: 66297 | ||
+ | Case #39: 3345 | ||
+ | Case #40: 44137 | ||
+ | Case #41: 341521 | ||
+ | Case #42: 226068 | ||
+ | Case #43: 72879 | ||
+ | Case #44: 383934 | ||
+ | Case #45: 215890 | ||
+ | Case #46: 58735 | ||
+ | Case #47: 366097 | ||
+ | Case #48: 263738 | ||
+ | Case #49: 41854 | ||
+ | Case #50: 6945 | ||
+ | </ |