ffprog:ffprogjava2016:soiaufgben

This is an old revision of the document!


Teilaufgaben 1 & 2

Lösungsvorschlag Cablecar Aufgaben 1 und 2

Anzeigen

Anzeigen

        Path datei = Paths.get("cable2-100-1000-1000000.txt");
        // Speicher für die Ausgabe
        ArrayList<String> lines = new ArrayList<>();
        try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
            int n = scanner.nextInt();
            for (int i=0; i<n; i++) {
                int m = scanner.nextInt();
                boolean ok = true;
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                int d = b-a; // Differenz zwischen Masten 0 und 1
                for (int j=2; j<m; j++) {
                    int c = scanner.nextInt();
                    if (c-b!=d) { // Mit letztem Masten vergleichen
                        ok = false;
                    }
                    b = c;  // Aktueller Mast wird letzter Mast
                }
                lines.add(String.format("Case #%d: %s", i+1, ok ? "yes" : "no"));
            }
        }
        // Einzeiler, das eine Liste von Strings in eine Datei schreibt.
        Files.write(Paths.get("output.txt"), lines);

Teilaufgabe 3

Teilaufgabe 4

Der “naive” Brute-Force Algorithmus in Ruby braucht (auf meiner 5-jährigen Kiste) etwa 3min 12s. Die Komplexität ist $O(n^3)$.

Ein “dynamische Programmierung”-Algorithmus (ebenfalls Ruby) braucht dafür etwa 9s. Die Komplexität ist $O(n^2 \log(n))$, wobei das $\log(n)$ von Lookups herrührt.

  • ffprog/ffprogjava2016/soiaufgben.1474033213.txt.gz
  • Last modified: 2016/09/16 15:40
  • by Ivo Blöchliger