Algorytmy i struktury danych · Rozdział 4
Klassische Algorithmen
Manche Algorithmen sind älter als jeder Computer und tauchen trotzdem in fast jeder Prüfung auf: Euklid, Primzahlen, Zahlensysteme, Prüfziffern und Wechselgeld. Sie sind kurz, lassen sich gut auf Papier durchspielen und zeigen, wie viel eine gute Idee an Laufzeit spart.
ggT und kgV mit Euklid
Der größte gemeinsame Teiler (ggT) lässt sich ohne Ausprobieren finden. Euklid nutzt: Der ggT von a und b ist derselbe wie der von b und a % b. Also ersetzt du so lange (a, b) durch (b, a % b), bis b 0 ist. Dann steht der ggT in a.
(1071, 462) 1071 % 462 = 147(462, 147) 462 % 147 = 21(147, 21) 147 % 21 = 0(21, 0) b ist 0, ggT = 21Ist a kleiner als b, tauscht der erste Schritt die beiden nur. Die Zahlen schrumpfen schnell: Die Zahl der Schritte wächst nur mit der Zahl der Stellen der kleineren Zahl, also O(log n).
Das kleinste gemeinsame Vielfache folgt daraus: kgV(a, b) = a / ggT(a, b) · b. Teile zuerst, sonst läuft a · b schnell über.
public class Main { public static int gcd(int a, int b) { while (b != 0) { int r = a % b; System.out.println("a = " + a + ", b = " + b + ", r = " + r); a = b; b = r; } return a; }
public static long lcm(int a, int b) { return (long) (a / gcd(a, b)) * b; }
public static void main(String[] args) { System.out.println("gcd: " + gcd(1071, 462)); System.out.println("lcm: " + lcm(4, 6)); }}Primzahlen und das Sieb
Eine Primzahl ist größer als 1 und nur durch 1 und sich selbst teilbar. Für den Test reicht es, Teiler bis √n zu probieren: Ist n = a · b, dann ist einer der beiden Faktoren höchstens √n. Statt t <= Math.sqrt(n) schreibt man meist t * t <= n. Der Test braucht so O(√n) Schritte statt O(n).
Brauchst du alle Primzahlen bis n, ist das Sieb des Eratosthenes schneller. Du legst ein boolean-Array an und streichst für jede Primzahl i ihre Vielfachen ab i · i. Was am Ende nicht gestrichen ist, ist prim. Das Sieb braucht O(n log log n) Schritte, praktisch fast linear, dafür aber ein Array der Größe n.
import java.util.ArrayList;import java.util.List;
public class Main { public static boolean isPrime(int n) { if (n < 2) { return false; } for (int t = 2; t * t <= n; t++) { if (n % t == 0) { return false; } } return true; }
public static List<Integer> sieve(int n) { boolean[] composite = new boolean[n + 1]; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (!composite[i]) { primes.add(i); for (long k = (long) i * i; k <= n; k += i) { composite[(int) k] = true; } } } return primes; }
public static void main(String[] args) { System.out.println(isPrime(91) + " " + isPrime(97)); System.out.println(sieve(50)); }}Zahlensysteme
Eine Zahl im System mit Basis b hat Stellenwerte 1, b, b², b³, …, von rechts gezählt. 1101 binär ist 1·8 + 1·4 + 0·2 + 1·1 = 13.
- Dezimal → Basis b (Restwertverfahren): Teile wiederholt durch
bund merke dir die Reste. Der erste Rest ist die letzte Ziffer, darum am Ende umdrehen. - Basis b → dezimal (Horner-Schema): Geh von links nach rechts und rechne
wert = wert · b + ziffer.
Beide brauchen so viele Schritte, wie die Zahl Stellen hat, also O(log n). Hexadezimal nutzt die Ziffern 0–9 und A–F. In Java gibt es dafür fertige Methoden wie Integer.toHexString und Integer.parseInt(text, basis). In der Prüfung sollst du das Verfahren aber selbst können.
public class Main { public static String toBinary(int n) { if (n == 0) { return "0"; } StringBuilder bits = new StringBuilder(); while (n > 0) { bits.append(n % 2); n = n / 2; } return bits.reverse().toString(); }
public static int fromBinary(String bits) { int value = 0; for (int i = 0; i < bits.length(); i++) { value = value * 2 + (bits.charAt(i) - '0'); } return value; }
public static void main(String[] args) { System.out.println(toBinary(13)); System.out.println(fromBinary("1101")); System.out.println(Integer.toHexString(255)); System.out.println(Integer.parseInt("FF", 16)); }}Caesar und Prüfziffern
Bei der Caesar-Verschlüsselung wird jeder Buchstabe um n Stellen verschoben. Mit char lässt sich rechnen: c - 'a' ist die Position im Alphabet, % 26 sorgt dafür, dass es nach z wieder bei a weitergeht. Entschlüsseln heißt um -n verschieben. Das + 26 verhindert dabei negative Reste. Sicher ist das nicht: Es gibt nur 25 Schlüssel, die man alle ausprobieren kann.
Eine Prüfziffer schützt nicht vor Angriffen, sondern vor Tippfehlern. Beim Luhn-Algorithmus (Kreditkarten) wird von rechts jede zweite Ziffer verdoppelt, bei Ergebnissen über 9 zieht man 9 ab. Ist die Summe aller Ziffern durch 10 teilbar, ist die Nummer gültig. So fällt jede einzelne falsche Ziffer auf und die meisten Vertauschungen zweier Nachbarn. Beide Verfahren gehen jedes Zeichen einmal durch: O(n).
public class Main { public static String caesar(String text, int shift) { StringBuilder result = new StringBuilder(); for (char c : text.toCharArray()) { if (c >= 'a' && c <= 'z') { result.append((char) ('a' + (c - 'a' + shift + 26) % 26)); } else if (c >= 'A' && c <= 'Z') { result.append((char) ('A' + (c - 'A' + shift + 26) % 26)); } else { result.append(c); } } return result.toString(); }
public static boolean luhn(String digits) { int sum = 0; for (int i = 0; i < digits.length(); i++) { int digit = digits.charAt(digits.length() - 1 - i) - '0'; if (i % 2 == 1) { digit = digit * 2; if (digit > 9) { digit = digit - 9; } } sum += digit; } return sum % 10 == 0; }
public static void main(String[] args) { String secret = caesar("Hello, World!", 3); System.out.println(secret); System.out.println(caesar(secret, -3)); System.out.println(luhn("79927398713")); System.out.println(luhn("79927398710")); }}Greedy und seine Grenzen
Ein Greedy-Algorithmus (gierig) trifft in jedem Schritt die Wahl, die gerade am besten aussieht, und nimmt sie nie zurück. Beim Wechselgeld heißt das: immer die größte Münze, die noch passt. Mit Euro-Münzen liefert das die wenigsten Münzen.
Bei anderen Münzsystemen geht das schief. Mit 4, 3 und 1 zahlt Greedy 6 als 4 + 1 + 1, obwohl 3 + 3 reicht. Und mit 5 und 2 findet es für 6 gar keine Lösung, obwohl 2 + 2 + 2 geht. Greedy ist schnell, aber nur bei passenden Problemen optimal. Für die beste Lösung in allen Fällen braucht es andere Verfahren wie Backtracking (Kapitel 6).
public class Main { public static void change(int amount, int[] coins) { System.out.print(amount + " ="); for (int coin : coins) { while (amount >= coin) { System.out.print(" " + coin); amount -= coin; } } System.out.println(amount == 0 ? "" : " (rest " + amount + ")"); }
public static void main(String[] args) { int[] euro = {200, 100, 50, 20, 10, 5, 2, 1}; change(388, euro);
int[] odd = {4, 3, 1}; change(6, odd); }}Laufzeiten im Überblick
- ggT nach Euklid: O(log n)
- Primzahltest bis √n: O(√n)
- Sieb des Eratosthenes: O(n log log n)
- Umrechnen in eine andere Basis: O(log n)
- Caesar, Luhn (Text der Länge n): O(n)
- Wechselgeld Greedy mit k sortierten Münzwerten: O(k), mit
/und%je Münzwert
Typowe błędy
Überlauf bei int
a * bmit zweiintwird alsintgerechnet, auch wenn das Ergebnis in einerlong-Variable landet. Bei100000 * 99999kommt eine falsche, sogar negative Zahl heraus. Teile vorher (a / ggT(a, b) * b) oder mache einen Faktor zumlong. Dasselbe gilt fürt * t <= n, wennnnahe anInteger.MAX_VALUEliegt.Ziffern in falscher Reihenfolge
Das Restwertverfahren liefert die letzte Ziffer zuerst. Wer die Reste einfach aneinanderhängt, bekommt für 6
011statt110. Umgekehrt ist beim Einlesen das erste Zeichen die höchste Stelle. Teste darum nie nur mit Zahlen wie101, die vorwärts und rückwärts gleich sind.Zeichen statt Ziffer
'7'ist eincharmit dem Zahlenwert 55, nicht 7. Wer mittext.charAt(i)rechnet, bekommt Unsinn. Den Ziffernwert lieferttext.charAt(i) - '0'. Genauso istc == 1etwas anderes alsc == '1'.