NWD, liczby pierwsze i inne klasyczne algorytmy w Javie

Największy wspólny dzielnik (NWD) da się znaleźć bez zgadywania. Euklides wykorzystuje to, że NWD liczb a i b jest taki sam jak NWD liczb b i a % b. Zastępujesz więc (a, b) przez (b, a % b) tak długo, aż b będzie równe 0. Wtedy NWD jest w a.

1(1071, 462)  1071 % 462 = 1472(462, 147)   462 % 147 = 213(147, 21)    147 % 21 = 04(21, 0)      b wynosi 0, NWD = 21

Jeśli a jest mniejsze od b, pierwszy krok tylko zamienia je miejscami. Liczby maleją szybko: liczba kroków rośnie tylko z liczbą cyfr mniejszej liczby, czyli O(log n).

Z tego wynika najmniejsza wspólna wielokrotność: NWW(a, b) = a / NWD(a, b) · b. Najpierw dziel, bo inaczej a · b szybko się przepełni.

1public class Main {2    public static int gcd(int a, int b) {3        while (b != 0) {4            int r = a % b;5            System.out.println("a = " + a + ", b = " + b + ", r = " + r);6            a = b;7            b = r;8        }9        return a;10    }11
12    public static long lcm(int a, int b) {13        return (long) (a / gcd(a, b)) * b;14    }15
16    public static void main(String[] args) {17        System.out.println("gcd: " + gcd(1071, 462));18        System.out.println("lcm: " + lcm(4, 6));19    }20}

Liczba pierwsza jest większa od 1 i dzieli się tylko przez 1 i przez samą siebie. Do sprawdzenia wystarczy próbować dzielników do √n: jeśli n = a · b, to jeden z dwóch czynników jest co najwyżej równy √n. Zamiast t <= Math.sqrt(n) pisze się zwykle t * t <= n. Test potrzebuje wtedy O(√n) kroków zamiast O(n).

Jeśli potrzebujesz wszystkich liczb pierwszych do n, szybsze jest sito Eratostenesa. Tworzysz tablicę typu boolean i dla każdej liczby pierwszej i wykreślasz jej wielokrotności, zaczynając od i · i. To, co na końcu nie jest wykreślone, jest liczbą pierwszą. Sito potrzebuje O(n log log n) kroków, w praktyce prawie liniowo, ale wymaga tablicy o rozmiarze n.

1import java.util.ArrayList;2import java.util.List;3
4public class Main {5    public static boolean isPrime(int n) {6        if (n < 2) {7            return false;8        }9        for (int t = 2; t * t <= n; t++) {10            if (n % t == 0) {11                return false;12            }13        }14        return true;15    }16
17    public static List<Integer> sieve(int n) {18        boolean[] composite = new boolean[n + 1];19        List<Integer> primes = new ArrayList<>();20        for (int i = 2; i <= n; i++) {21            if (!composite[i]) {22                primes.add(i);23                for (long k = (long) i * i; k <= n; k += i) {24                    composite[(int) k] = true;25                }26            }27        }28        return primes;29    }30
31    public static void main(String[] args) {32        System.out.println(isPrime(91) + " " + isPrime(97));33        System.out.println(sieve(50));34    }35}

Liczba w systemie o podstawie b ma wagi pozycji 1, b, b², b³, …, licząc od prawej. 1101 dwójkowo to 1·8 + 1·4 + 0·2 + 1·1 = 13.

• Dziesiętny → podstawa b (metoda reszt): dziel wielokrotnie przez b i zapisuj reszty. Pierwsza reszta to ostatnia cyfra, dlatego na końcu odwróć kolejność.
• Podstawa b → dziesiętny (schemat Hornera): idź od lewej do prawej i licz wartość = wartość · b + cyfra.

Obie metody potrzebują tylu kroków, ile cyfr ma liczba, czyli O(log n). System szesnastkowy używa cyfr 0–9 i A–F. Java ma do tego gotowe metody, takie jak Integer.toHexString i Integer.parseInt(text, podstawa). Na egzaminie musisz jednak umieć zrobić to sam.

1public class Main {2    public static String toBinary(int n) {3        if (n == 0) {4            return "0";5        }6        StringBuilder bits = new StringBuilder();7        while (n > 0) {8            bits.append(n % 2);9            n = n / 2;10        }11        return bits.reverse().toString();12    }13
14    public static int fromBinary(String bits) {15        int value = 0;16        for (int i = 0; i < bits.length(); i++) {17            value = value * 2 + (bits.charAt(i) - '0');18        }19        return value;20    }21
22    public static void main(String[] args) {23        System.out.println(toBinary(13));24        System.out.println(fromBinary("1101"));25        System.out.println(Integer.toHexString(255));26        System.out.println(Integer.parseInt("FF", 16));27    }28}

W szyfrze Cezara każda litera jest przesuwana o n miejsc. Na typie char można liczyć, bo każdy znak napisu jest wewnętrznie liczbą: c - 'a' to pozycja w alfabecie, a % 26 sprawia, że po z wracasz do a. Odszyfrowanie to przesunięcie o -n. + 26 zapobiega przy tym ujemnym resztom. Bezpieczne to nie jest: istnieje tylko 25 kluczy i można wypróbować wszystkie.

Cyfra kontrolna nie chroni przed atakami, tylko przed literówkami. W algorytmie Luhna (karty płatnicze) co druga cyfra od prawej jest podwajana, a od wyników większych niż 9 odejmuje się 9. Jeśli suma wszystkich cyfr jest podzielna przez 10, numer jest poprawny. Wykrywa to każdą pojedynczą błędną cyfrę i większość zamian dwóch sąsiednich cyfr. Obie metody przechodzą każdy znak raz: O(n).

1public class Main {2    public static String caesar(String text, int shift) {3        StringBuilder result = new StringBuilder();4        for (char c : text.toCharArray()) {5            if (c >= 'a' && c <= 'z') {6                result.append((char) ('a' + (c - 'a' + shift + 26) % 26));7            } else if (c >= 'A' && c <= 'Z') {8                result.append((char) ('A' + (c - 'A' + shift + 26) % 26));9            } else {10                result.append(c);11            }12        }13        return result.toString();14    }15
16    public static boolean luhn(String digits) {17        int sum = 0;18        for (int i = 0; i < digits.length(); i++) {19            int digit = digits.charAt(digits.length() - 1 - i) - '0';20            if (i % 2 == 1) {21                digit = digit * 2;22                if (digit > 9) {23                    digit = digit - 9;24                }25            }26            sum += digit;27        }28        return sum % 10 == 0;29    }30
31    public static void main(String[] args) {32        String secret = caesar("Hello, World!", 3);33        System.out.println(secret);34        System.out.println(caesar(secret, -3));35        System.out.println(luhn("79927398713"));36        System.out.println(luhn("79927398710"));37    }38}

Algorytm zachłanny (greedy) w każdym kroku wybiera to, co w danej chwili wygląda najlepiej, i nigdy nie cofa tej decyzji. Przy wydawaniu reszty oznacza to: zawsze największa moneta, która jeszcze się mieści. Przy monetach euro daje to najmniejszą liczbę monet.

Przy innych systemach monet to zawodzi. Przy monetach 4, 3 i 1 algorytm zachłanny wypłaca 6 jako 4 + 1 + 1, choć wystarczy 3 + 3. A przy 5 i 2 w ogóle nie znajduje rozwiązania dla 6, choć 2 + 2 + 2 działa. Algorytm zachłanny jest szybki, ale optymalny tylko dla odpowiednich problemów. Żeby znaleźć najlepsze rozwiązanie w każdym przypadku, potrzeba innych metod, na przykład backtrackingu.

1public class Main {2    public static void change(int amount, int[] coins) {3        System.out.print(amount + " =");4        for (int coin : coins) {5            while (amount >= coin) {6                System.out.print(" " + coin);7                amount -= coin;8            }9        }10        System.out.println(amount == 0 ? "" : " (rest " + amount + ")");11    }12
13    public static void main(String[] args) {14        int[] euro = {200, 100, 50, 20, 10, 5, 2, 1};15        change(388, euro);16
17        int[] odd = {4, 3, 1};18        change(6, odd);19    }20}

Złożoność w skrócie

• NWD algorytmem Euklidesa: O(log n)
• Test pierwszości do √n: O(√n)
• Sito Eratostenesa: O(n log log n)
• Zamiana na inną podstawę: O(log n)
• Szyfr Cezara, Luhn (tekst długości n): O(n)
• Zachłanne wydawanie reszty z k posortowanymi nominałami: O(k), z / i % dla każdego nominału