Differences

This shows you the differences between two versions of the page.

--- ffprog:ffprogjava2016:soiaufgben [2016/09/30 16:21]
Ivo Blöchliger [Tunnel]
+++ ffprog:ffprogjava2016:soiaufgben [2016/10/11 13:00]
Ivo Blöchliger [Tunnel]
@@ Line 99: / Line 99: @@
   * {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000.txt |}}  {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000-output.txt |}}
+=== 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<String> lines = new 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("%d",n));
+            List<Integer> bounds = Arrays.asList(r.nextInt(n), r.nextInt(n));
+            Collections.sort(bounds);
+            int minH = r.nextInt(maxH/2)+maxH/4;
+            System.out.println("Tunnel open at height "+minH+" from "+bounds.get(0)+" to "+bounds.get(1)+" min length="+(bounds.get(1)-bounds.get(0)));
+            int heights[][] = new int[2][n];
+            for (int i=0; i<n; i++) {
+                int x = (i>=bounds.get(0) && i<bounds.get(1)) ? minH : r.nextInt(maxH-1)+1;
+                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), lines);
+        System.out.println("Wrote file "+fileName);
+    }
+</code>
+Aufruf mit
+<code java>
+        generate("tunnel3.txt", 50, 1000000, 100000000, 42);
+</code>
+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
+</code>