Algorytmy — C#

Po co się tego uczymy?

Uczeń ma dostać algorytm w małych porcjach: nazwa, zastosowanie, sposób działania i kod. Dzięki temu materiał nadaje się do samodzielnej nauki, a nie tylko do kopiowania.

Teoria

Algorytmy poniżej są ułożone w osobnych kartach. Każda karta wyjaśnia problem prostym językiem, pokazuje kroki działania i daje krótki przykład kodu z polskimi nazwami zmiennych.

Przykład z życia

Ta wersja jest przygotowana dla języka C#. Każdy algorytm ma osobną kartę: nazwę po polsku, proste wyjaśnienie, kroki działania i krótki kod z polskimi nazwami zmiennych.

Ucz się aktywnie: najpierw przeczytaj opis, potem przejdź kod linijka po linijce, a na końcu zmień dane wejściowe i sprawdź wynik.

Badanie podzielności i operator modulo

liczbymod

Modulo zwraca resztę z dzielenia. Jeżeli reszta z dzielenia przez dzielnik wynosi 0, liczba jest przez niego podzielna.

oblicz resztę z dzielenia
porównaj resztę z zerem
zwróć odpowiedź logiczną

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static bool CzyPodzielna(int liczba, int dzielnik)
    {
        return dzielnik != 0 && liczba % dzielnik == 0;
    }

    static void Main()
    {
        Console.WriteLine(CzyPodzielna(24, 6));
    }
}

Przykład uruchomienia: Console.WriteLine(CzyPodzielna(24, 6));

NWD — algorytm Euklidesa przez odejmowanie

liczbyNWD

Największy wspólny dzielnik nie zmienia się, gdy od większej liczby odejmujemy mniejszą. Powtarzamy to, aż obie liczby będą równe.

porównaj dwie liczby
od większej odejmij mniejszą
zatrzymaj się, gdy liczby są równe

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int NwdOdejmowanie(int a, int b)
    {
        a = Math.Abs(a); b = Math.Abs(b);
        while (a != b)
            if (a > b) a -= b; else b -= a;
        return a;
    }

    static void Main()
    {
        Console.WriteLine(NwdOdejmowanie(48, 18));
    }
}

Przykład uruchomienia: Console.WriteLine(NwdOdejmowanie(48, 18));

NWD modulo i NWW przez NWD

liczbyNWDNWW

Wersja modulo jest szybsza: zamiast odejmować wiele razy, od razu bierzemy resztę z dzielenia. NWW liczymy ze wzoru: a razy b podzielone przez NWD.

zamień parę (a, b) na (b, a % b)
powtarzaj, aż b będzie zerem
NWW policz ze wzoru

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int Nwd(int a, int b)
    {
        while (b != 0) { int reszta = a % b; a = b; b = reszta; }
        return Math.Abs(a);
    }
    static int Nww(int a, int b) => Math.Abs(a * b) / Nwd(a, b);

    static void Main()
    {
        Console.WriteLine($"{Nwd(48, 18)} {Nww(12, 18)}");
    }
}

Przykład uruchomienia: Console.WriteLine($"{Nwd(48, 18)} {Nww(12, 18)}");

Liczba pierwsza i rozkład na czynniki

liczbypierwsze

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. Wystarczy sprawdzać dzielniki do pierwiastka z liczby, bo większe dzielniki miałyby parę mniejszą od pierwiastka.

odrzuć liczby mniejsze od 2
sprawdzaj dzielniki od 2 do √n
przy rozkładzie dziel przez znaleziony czynnik tak długo, jak się da

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static bool CzyPierwsza(int liczba)
    {
        if (liczba < 2) return false;
        for (int dzielnik = 2; dzielnik * dzielnik <= liczba; dzielnik++)
            if (liczba % dzielnik == 0) return false;
        return true;
    }

    static void Main()
    {
        Console.WriteLine(CzyPierwsza(29));
    }
}

Przykład uruchomienia: Console.WriteLine(CzyPierwsza(29));

Sito Eratostenesa

liczbypierwsze

Sito tworzy listę kandydatów na liczby pierwsze i wykreśla wielokrotności kolejnych liczb pierwszych. To szybki sposób na wszystkie liczby pierwsze do n.

załóż, że liczby od 2 są pierwsze
dla kolejnej niewykreślonej liczby wykreśl jej wielokrotności
zostaw niewykreślone wartości

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<int> Sito(int granica)
    {
        bool[] pierwsza = Enumerable.Repeat(true, granica + 1).ToArray();
        pierwsza[0] = pierwsza[1] = false;
        for (int liczba = 2; liczba * liczba <= granica; liczba++)
            if (pierwsza[liczba])
                for (int w = liczba * liczba; w <= granica; w += liczba) pierwsza[w] = false;
        return Enumerable.Range(2, granica - 1).Where(i => pierwsza[i]).ToList();
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", Sito(30)));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", Sito(30)));

Szybkie potęgowanie

liczbydziel i zwyciężaj

Zamiast mnożyć podstawę tyle razy, ile wynosi wykładnik, rozbijamy wykładnik na połowy. Gdy wykładnik jest nieparzysty, dokładamy jedną podstawę do wyniku.

jeśli wykładnik jest nieparzysty, pomnóż wynik przez podstawę
podstawę podnieś do kwadratu
wykładnik podziel całkowicie przez 2

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static long SzybkaPotega(long podstawa, long wykladnik)
    {
        long wynik = 1;
        while (wykladnik > 0) {
            if (wykladnik % 2 == 1) wynik *= podstawa;
            podstawa *= podstawa; wykladnik /= 2;
        }
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(SzybkaPotega(2, 10));
    }
}

Przykład uruchomienia: Console.WriteLine(SzybkaPotega(2, 10));

Schemat Hornera

liczbywielomiany

Horner pozwala obliczyć wartość wielomianu bez osobnego liczenia kolejnych potęg. Wynik budujemy od lewej: mnożymy przez x i dodajemy następny współczynnik.

zacznij od wyniku 0
dla każdego współczynnika wykonaj: wynik = wynik * x + współczynnik
po ostatnim współczynniku masz wartość wielomianu

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int Horner(int[] wspolczynniki, int x)
    {
        int wynik = 0;
        foreach (int wspolczynnik in wspolczynniki)
            wynik = wynik * x + wspolczynnik;
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(Horner(new[] {2, 3, 1}, 2));
    }
}

Przykład uruchomienia: Console.WriteLine(Horner(new[] {2, 3, 1}, 2));

Fibonacci iteracyjnie i rekurencyjnie

rekurencjaiteracja

Ciąg Fibonacciego zaczyna się od 0 i 1, a każdy następny wyraz jest sumą dwóch poprzednich. Wersja iteracyjna jest szybka, rekurencyjna dobrze pokazuje ideę, ale dla dużych n jest wolna.

iteracyjnie trzymaj dwie ostatnie wartości
rekurencyjnie użyj wzoru F(n)=F(n-1)+F(n-2)
pamiętaj o warunku stopu dla 0 i 1

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static long FibIteracyjnie(int n)
    {
        long poprzedni = 0, aktualny = 1;
        while (n-- > 0) { long nastepny = poprzedni + aktualny; poprzedni = aktualny; aktualny = nastepny; }
        return poprzedni;
    }
    static long FibRekurencyjnie(int n) => n < 2 ? n : FibRekurencyjnie(n-1) + FibRekurencyjnie(n-2);

    static void Main()
    {
        Console.WriteLine($"{FibIteracyjnie(10)} {FibRekurencyjnie(10)}");
    }
}

Przykład uruchomienia: Console.WriteLine($"{FibIteracyjnie(10)} {FibRekurencyjnie(10)}");

Silnia i wydawanie reszty zachłannie

liczbyzachłanny

Silnia mnoży kolejne liczby od 1 do n. Wydawanie reszty zachłannie zawsze wybiera największy nominał, który mieści się w pozostałej kwocie.

silnia: mnoż wynik przez kolejne i
reszta: wybierz największy możliwy nominał
odejmij jego wielokrotność od kwoty

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static long Silnia(int n)
    {
        long wynik = 1;
        for (int liczba = 2; liczba <= n; liczba++) wynik *= liczba;
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(Silnia(5));
    }
}

Przykład uruchomienia: Console.WriteLine(Silnia(5));

Sortowanie bąbelkowe

sortowanieO(n²)

Porównujemy sąsiednie elementy i zamieniamy je miejscami, jeśli są w złej kolejności. Największe wartości „wypływają” na koniec tablicy.

przechodź po parach sąsiadów
zamień, jeśli lewy jest większy od prawego
po każdej rundzie ostatni element jest już na miejscu

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] SortowanieBabelkowe(int[] tablica)
    {
        tablica = (int[])tablica.Clone();
        for (int koniec = tablica.Length - 1; koniec > 0; koniec--)
            for (int i = 0; i < koniec; i++)
                if (tablica[i] > tablica[i+1]) (tablica[i], tablica[i+1]) = (tablica[i+1], tablica[i]);
        return tablica;
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", SortowanieBabelkowe(new[] {5, 2, 8, 1})));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", SortowanieBabelkowe(new[] {5, 2, 8, 1})));

Sortowanie przez wybór

sortowanieO(n²)

W każdej rundzie szukamy najmniejszego elementu w nieposortowanej części i przenosimy go na początek tej części.

ustaw pozycję początku nieposortowanej części
znajdź indeks minimum
zamień minimum z początkiem

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] SortowanieWybor(int[] tablica)
    {
        tablica = (int[])tablica.Clone();
        for (int poczatek = 0; poczatek < tablica.Length; poczatek++) {
            int minimum = poczatek;
            for (int i = poczatek + 1; i < tablica.Length; i++) if (tablica[i] < tablica[minimum]) minimum = i;
            (tablica[poczatek], tablica[minimum]) = (tablica[minimum], tablica[poczatek]);
        }
        return tablica;
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", SortowanieWybor(new[] {5, 2, 8, 1})));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", SortowanieWybor(new[] {5, 2, 8, 1})));

Sortowanie przez wstawianie

sortowanieO(n²)

Bierzemy kolejny element i wstawiamy go w odpowiednie miejsce w już posortowanej lewej części tablicy. Działa podobnie do układania kart w ręce.

weź element z nieposortowanej części
przesuwaj większe elementy w prawo
wstaw element w powstałe miejsce

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] SortowanieWstawianie(int[] tablica)
    {
        tablica = (int[])tablica.Clone();
        for (int i = 1; i < tablica.Length; i++) {
            int element = tablica[i], j = i - 1;
            while (j >= 0 && tablica[j] > element) { tablica[j+1] = tablica[j]; j--; }
            tablica[j+1] = element;
        }
        return tablica;
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", SortowanieWstawianie(new[] {5, 2, 8, 1})));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", SortowanieWstawianie(new[] {5, 2, 8, 1})));

Sortowanie przez scalanie

sortowaniedziel i zwyciężaj

Dzielimy tablicę na połowy, sortujemy połówki, a potem scalamy dwie posortowane listy w jedną. To klasyczne „dziel i zwyciężaj”.

podziel tablicę na dwie części
posortuj każdą część rekurencyjnie
scal dwie posortowane części

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] Scal(int[] lewa, int[] prawa)
    {
        var wynik = new List<int>();
        int i = 0, j = 0;
        while (i < lewa.Length && j < prawa.Length) {
            if (lewa[i] <= prawa[j]) wynik.Add(lewa[i++]);
            else wynik.Add(prawa[j++]);
        }
        while (i < lewa.Length) wynik.Add(lewa[i++]);
        while (j < prawa.Length) wynik.Add(prawa[j++]);
        return wynik.ToArray();
    }

    static int[] SortowanieScalanie(int[] tablica)
    {
        if (tablica.Length <= 1) return tablica;
        int srodek = tablica.Length / 2;
        int[] lewa = tablica.Take(srodek).ToArray();
        int[] prawa = tablica.Skip(srodek).ToArray();
        return Scal(SortowanieScalanie(lewa), SortowanieScalanie(prawa));
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", SortowanieScalanie(new[] {5, 2, 8, 1})));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", SortowanieScalanie(new[] {5, 2, 8, 1})));

Quicksort — sortowanie szybkie

sortowaniedziel i zwyciężaj

Wybieramy element osiowy, dzielimy dane na mniejsze, równe i większe od niego, a potem sortujemy części rekurencyjnie.

wybierz pivot
podziel elementy względem pivota
posortuj rekurencyjnie lewą i prawą część

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] Quicksort(int[] tablica)
    {
        if (tablica.Length <= 1) return tablica;
        int pivot = tablica[tablica.Length / 2];
        return Quicksort(tablica.Where(x => x < pivot).ToArray())
            .Concat(tablica.Where(x => x == pivot))
            .Concat(Quicksort(tablica.Where(x => x > pivot).ToArray())).ToArray();
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", Quicksort(new[] {5, 2, 8, 1})));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", Quicksort(new[] {5, 2, 8, 1})));

Sortowanie przez zliczanie

sortowaniekubełkowe

Działa dobrze, gdy wartości są liczbami całkowitymi z niedużego zakresu. Zliczamy, ile razy występuje każda wartość, a potem odtwarzamy posortowaną tablicę.

utwórz tablicę liczników
zwiększ licznik dla każdej wartości
wypisz wartości tyle razy, ile wynosi licznik

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] SortowanieZliczanie(int[] tablica, int maksimum)
    {
        int[] liczniki = new int[maksimum + 1];
        foreach (int liczba in tablica) liczniki[liczba]++;
        var wynik = new List<int>();
        for (int wartosc = 0; wartosc <= maksimum; wartosc++)
            for (int i = 0; i < liczniki[wartosc]; i++) wynik.Add(wartosc);
        return wynik.ToArray();
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", SortowanieZliczanie(new[] {3, 1, 2, 3, 0}, 3)));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", SortowanieZliczanie(new[] {3, 1, 2, 3, 0}, 3)));

Wyszukiwanie liniowe i binarne

wyszukiwanie

Liniowe sprawdza element po elemencie i działa zawsze. Binarne działa tylko na danych posortowanych, ale za każdym krokiem odrzuca połowę zakresu.

liniowe: idź od początku do końca
binarne: sprawdź środek
przesuń lewy lub prawy koniec zakresu

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int SzukajBinarnie(int[] tablica, int szukana)
    {
        int lewy = 0, prawy = tablica.Length - 1;
        while (lewy <= prawy) {
            int srodek = (lewy + prawy) / 2;
            if (tablica[srodek] == szukana) return srodek;
            if (tablica[srodek] < szukana) lewy = srodek + 1; else prawy = srodek - 1;
        }
        return -1;
    }

    static void Main()
    {
        Console.WriteLine(SzukajBinarnie(new[] {1, 4, 7, 9}, 7));
    }
}

Przykład uruchomienia: Console.WriteLine(SzukajBinarnie(new[] {1, 4, 7, 9}, 7));

Minimum, maksimum i lider

wyszukiwanielider

Minimum i maksimum znajdujemy jednym przejściem po tablicy. Lider to wartość, która występuje częściej niż połowa elementów; algorytm Boyera-Moore’a wybiera kandydata i potem go sprawdza.

przechodź po danych raz
aktualizuj minimum i maksimum
dla lidera kasuj pary różnych wartości

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static (int minimum, int maksimum) MinimumMaksimum(int[] tablica)
    {
        return (tablica.Min(), tablica.Max());
    }

    static void Main()
    {
        Console.WriteLine(MinimumMaksimum(new[] {3, 8, 1}));
    }
}

Przykład uruchomienia: Console.WriteLine(MinimumMaksimum(new[] {3, 8, 1}));

Palindrom i zliczanie znaków

tekst

Palindrom czyta się tak samo od lewej i od prawej. Zliczanie znaków polega na przejściu po tekście i zwiększaniu licznika dla każdego znaku.

porównaj tekst z jego odwróceniem
dla zliczania użyj słownika/mapy
zwiększ licznik znaku

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static bool CzyPalindrom(string tekst)
    {
        string odwrocony = new string(tekst.Reverse().ToArray());
        return tekst == odwrocony;
    }

    static void Main()
    {
        Console.WriteLine(CzyPalindrom("kajak"));
    }
}

Przykład uruchomienia: Console.WriteLine(CzyPalindrom("kajak"));

Wyszukiwanie wzorca w tekście

tekst

W wersji naiwnej przykładamy wzorzec do każdego miejsca w tekście i sprawdzamy zgodność znak po znaku. KMP i Rabin-Karp robią to szybciej, ale idea nadal zaczyna się od pojęcia wzorca.

wybierz pozycję startową
porównaj fragment tekstu ze wzorcem
zapisz pozycję, jeśli pasuje

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<int> ZnajdzWzorzec(string tekst, string wzorzec)
    {
        var pozycje = new List<int>();
        for (int i = 0; i + wzorzec.Length <= tekst.Length; i++)
            if (tekst.Substring(i, wzorzec.Length) == wzorzec) pozycje.Add(i);
        return pozycje;
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", ZnajdzWzorzec("abrakadabra", "abra")));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", ZnajdzWzorzec("abrakadabra", "abra")));

Porządkowanie leksykograficzne i szyfry

tekstszyfry

Porządkowanie leksykograficzne to sortowanie tekstów jak w słowniku. Szyfr Cezara przesuwa litery, GADERYPOLUKI podmienia pary liter, a RSA pokazuje ideę klucza jawnego i prywatnego.

dla sortowania porównuj napisy
dla Cezara przesuń literę w alfabecie
dla RSA pamiętaj: to demonstracja matematyczna na małych liczbach

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Cezar(string tekst, int przesuniecie)
    {
        return new string(tekst.Select(znak => {
            if (!char.IsLetter(znak)) return znak;
            char baza = char.IsUpper(znak) ? 'A' : 'a';
            return (char)((znak - baza + przesuniecie + 26) % 26 + baza);
        }).ToArray());
    }

    static void Main()
    {
        Console.WriteLine(Cezar("Ala ma kota", 3));
    }
}

Przykład uruchomienia: Console.WriteLine(Cezar("Ala ma kota", 3));

Metoda bisekcji

numeryczne

Bisekcja szuka miejsca zerowego funkcji w przedziale. Jeśli funkcja zmienia znak między końcami przedziału, dzielimy przedział na pół i zostawiamy tę połowę, gdzie nadal jest zmiana znaku.

policz środek przedziału
sprawdź znak funkcji na końcu i w środku
zawęź przedział

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static double Bisekcja(Func<double,double> funkcja, double lewy, double prawy)
    {
        while (prawy - lewy > 1e-6) {
            double srodek = (lewy + prawy) / 2;
            if (funkcja(lewy) * funkcja(srodek) <= 0) prawy = srodek; else lewy = srodek;
        }
        return (lewy + prawy) / 2;
    }

    static void Main()
    {
        Console.WriteLine(Bisekcja(x => x*x - 2, 0, 2));
    }
}

Przykład uruchomienia: Console.WriteLine(Bisekcja(x => x*x - 2, 0, 2));

Pole pod wykresem i metoda Newtona

numeryczne

Pole pod wykresem można przybliżyć prostokątami albo trapezami. Metoda Newtona/Herona poprawia przybliżenie pierwiastka, uśredniając wynik z ilorazem liczby przez wynik.

podziel przedział na małe części
zsumuj pola prostokątów lub trapezów
dla pierwiastka poprawiaj przybliżenie aż do wymaganej dokładności

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static double PierwiastekNewtona(double liczba)
    {
        double wynik = liczba;
        while (Math.Abs(wynik * wynik - liczba) > 1e-6)
            wynik = (wynik + liczba / wynik) / 2;
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(PierwiastekNewtona(9));
    }
}

Przykład uruchomienia: Console.WriteLine(PierwiastekNewtona(9));

Rekurencja — wieże Hanoi

rekurencja

Rekurencja oznacza, że funkcja wywołuje samą siebie dla mniejszego problemu. W Hanoi najpierw przenosimy n-1 krążków, potem największy, potem znów n-1.

ustal warunek stopu
rozwiąż mniejszy problem
wykonaj jeden ruch główny
rozwiąż drugi mniejszy problem

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Hanoi(int ile, char zrodlo, char pomoc, char cel)
    {
        if (ile == 0) return;
        Hanoi(ile - 1, zrodlo, cel, pomoc);
        Console.WriteLine($"{zrodlo} -> {cel}");
        Hanoi(ile - 1, pomoc, zrodlo, cel);
    }

    static void Main()
    {
        Hanoi(3, 'A', 'B', 'C');
    }
}

Przykład uruchomienia: Hanoi(3, 'A', 'B', 'C');

Algorytm zachłanny — plecak ułamkowy

zachłanny

Algorytm zachłanny podejmuje lokalnie najlepszą decyzję. W plecaku ułamkowym bierzemy przedmioty według największej wartości na jednostkę wagi.

policz wartość na kilogram
posortuj malejąco
bierz cały przedmiot albo jego część

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static double PlecakUlamkowy(List<(double wartosc, double waga)> przedmioty, double pojemnosc)
    {
        double wynik = 0;
        foreach (var przedmiot in przedmioty.OrderByDescending(p => p.wartosc / p.waga)) {
            double biore = Math.Min(przedmiot.waga, pojemnosc);
            wynik += biore * przedmiot.wartosc / przedmiot.waga;
            pojemnosc -= biore;
            if (pojemnosc == 0) break;
        }
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(PlecakUlamkowy(new List<(double wartosc, double waga)> { (60, 10), (100, 20), (120, 30) }, 50));
    }
}

Przykład uruchomienia: Console.WriteLine(PlecakUlamkowy(new List<(double wartosc, double waga)> { (60, 10), (100, 20), (120, 30) }, 50));

Programowanie dynamiczne — monety i LCS

dynamiczne

Programowanie dynamiczne zapamiętuje wyniki mniejszych podproblemów. Dzięki temu nie liczymy wielokrotnie tego samego, jak w naiwnej rekurencji.

zdefiniuj małe podproblemy
zapisuj ich wyniki w tablicy
buduj odpowiedź od prostych przypadków do trudniejszych

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int NajmniejMonet(int kwota, int[] monety)
    {
        int[] dp = Enumerable.Repeat(1_000_000, kwota + 1).ToArray(); dp[0] = 0;
        for (int suma = 1; suma <= kwota; suma++)
            foreach (int moneta in monety) if (moneta <= suma)
                dp[suma] = Math.Min(dp[suma], dp[suma - moneta] + 1);
        return dp[kwota];
    }

    static void Main()
    {
        Console.WriteLine(NajmniejMonet(11, new[] {1, 5, 7}));
    }
}

Przykład uruchomienia: Console.WriteLine(NajmniejMonet(11, new[] {1, 5, 7}));

Backtracking — hetmany i labirynt

backtracking

Backtracking próbuje kolejnych decyzji, a gdy ścieżka prowadzi do błędu, cofa się i sprawdza następną możliwość. To metoda „spróbuj, sprawdź, cofnij”.

wybierz możliwy ruch
sprawdź, czy jest poprawny
idź głębiej rekurencyjnie
jeśli się nie uda, cofnij wybór

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<List<int>> Hetmany(int n)
    {
        var rozwiazania = new List<List<int>>();
        var kolumny = new List<int>();

        bool CzyPoprawne(int wiersz, int kolumna) {
            for (int i = 0; i < kolumny.Count; i++)
                if (kolumny[i] == kolumna || Math.Abs(kolumny[i] - kolumna) == Math.Abs(i - wiersz)) return false;
            return true;
        }

        void Szukaj(int wiersz) {
            if (wiersz == n) { rozwiazania.Add(new List<int>(kolumny)); return; }
            for (int kolumna = 0; kolumna < n; kolumna++) {
                if (CzyPoprawne(wiersz, kolumna)) {
                    kolumny.Add(kolumna);
                    Szukaj(wiersz + 1);
                    kolumny.RemoveAt(kolumny.Count - 1);
                }
            }
        }

        Szukaj(0);
        return rozwiazania;
    }

    static void Main()
    {
        Console.WriteLine(Hetmany(4).Count);
    }
}

Przykład uruchomienia: Console.WriteLine(Hetmany(4).Count);

Struktury danych: tablica, stos, kolejka, drzewo, kopiec, graf

struktury danych

Struktura danych decyduje, jak przechowujesz informacje. Tablica daje szybki dostęp po indeksie, stos działa LIFO, kolejka FIFO, kopiec szybko zwraca minimum/maksimum, a graf opisuje połączenia.

dobierz strukturę do operacji
stos: ostatni wchodzi, pierwszy wychodzi
kolejka: pierwszy wchodzi, pierwszy wychodzi
graf zapisz jako listę sąsiedztwa albo macierz

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void PokazStruktury()
    {
        var tablica = new List<int>{3, 1, 4};

        var stos = new Stack<int>();
        stos.Push(10);
        stos.Push(20);
        int zeStosu = stos.Pop();

        var kolejka = new Queue<int>();
        kolejka.Enqueue(10);
        kolejka.Enqueue(20);
        int zKolejki = kolejka.Dequeue();

        var graf = new List<int>[] { new(){1, 2}, new(){0}, new(){0} };
        Console.WriteLine($"{tablica[0]} {zeStosu} {zKolejki} {graf[0].Count}");
    }

    static void Main()
    {
        PokazStruktury();
    }
}

Przykład uruchomienia: PokazStruktury();

BFS i DFS

grafy

BFS przeszukuje graf wszerz, poziomami, używając kolejki. DFS idzie jak najgłębiej, używając rekurencji albo stosu.

zaznacz start jako odwiedzony
BFS: zdejmuj z kolejki
DFS: odwiedzaj rekurencyjnie sąsiadów

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<int> Bfs(List<int>[] graf, int start)
    {
        bool[] odwiedzone = new bool[graf.Length]; var kolejka = new Queue<int>(); var wynik = new List<int>();
        odwiedzone[start] = true; kolejka.Enqueue(start);
        while (kolejka.Count > 0) { int v = kolejka.Dequeue(); wynik.Add(v);
            foreach (int sasiad in graf[v]) if (!odwiedzone[sasiad]) { odwiedzone[sasiad] = true; kolejka.Enqueue(sasiad); }}
        return wynik;
    }

    static void Main()
    {
        Console.WriteLine(string.Join(" ", Bfs(new List<int>[] { new(){1,2}, new(){}, new(){} }, 0)));
    }
}

Przykład uruchomienia: Console.WriteLine(string.Join(" ", Bfs(new List<int>[] { new(){1,2}, new(){}, new(){} }, 0)));

Dijkstra — najkrótsza ścieżka

grafyścieżki

Dijkstra znajduje najkrótsze odległości od startu w grafie z nieujemnymi wagami. Zawsze wybiera jeszcze nieprzetworzony wierzchołek o najmniejszym znanym koszcie.

ustaw odległość startu na 0
wybierz najbliższy wierzchołek z kolejki priorytetowej
popraw odległości sąsiadów

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int[] Dijkstra(List<(int sasiad, int waga)>[] graf, int start)
    {
        int[] odleglosc = Enumerable.Repeat(1_000_000_000, graf.Length).ToArray();
        var kolejka = new PriorityQueue<int, int>();
        odleglosc[start] = 0;
        kolejka.Enqueue(start, 0);

        while (kolejka.Count > 0) {
            int wierzcholek = kolejka.Dequeue();
            foreach (var krawedz in graf[wierzcholek]) {
                int nowy = odleglosc[wierzcholek] + krawedz.waga;
                if (nowy < odleglosc[krawedz.sasiad]) {
                    odleglosc[krawedz.sasiad] = nowy;
                    kolejka.Enqueue(krawedz.sasiad, nowy);
                }
            }
        }
        return odleglosc;
    }

    static void Main()
    {
        var graf = new List<(int sasiad, int waga)>[] { new(){(1, 3), (2, 1)}, new(){}, new(){(1, 1)} }; Console.WriteLine(string.Join(" ", Dijkstra(graf, 0)));
    }
}

Przykład uruchomienia: var graf = new List<(int sasiad, int waga)>[] { new(){(1, 3), (2, 1)}, new(){}, new(){(1, 1)} }; Console.WriteLine(string.Join(" ", Dijkstra(graf, 0)));

Minimalne drzewo rozpinające — Prim i Kruskal

grafyMST

Minimalne drzewo rozpinające łączy wszystkie wierzchołki najtańszym zestawem krawędzi. Prim rozbudowuje jedno drzewo, a Kruskal bierze krawędzie od najlżejszej i pilnuje, żeby nie zrobić cyklu.

Prim: zacznij od dowolnego wierzchołka
Kruskal: posortuj krawędzie rosnąco
dodawaj krawędź tylko, gdy łączy różne składowe

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    class Dsu
    {
        private int[] rodzic;
        public Dsu(int n) { rodzic = Enumerable.Range(0, n).ToArray(); }
        public int Znajdz(int x) => rodzic[x] == x ? x : rodzic[x] = Znajdz(rodzic[x]);
        public bool Polacz(int a, int b) {
            a = Znajdz(a); b = Znajdz(b);
            if (a == b) return false;
            rodzic[a] = b;
            return true;
        }
    }

    static List<(int waga, int a, int b)> Kruskal(int liczbaWierzcholkow, List<(int waga, int a, int b)> krawedzie)
    {
        var dsu = new Dsu(liczbaWierzcholkow);
        var wynik = new List<(int waga, int a, int b)>();
        foreach (var k in krawedzie.OrderBy(k => k.waga))
            if (dsu.Polacz(k.a, k.b)) wynik.Add(k);
        return wynik;
    }

    static void Main()
    {
        var wynik = Kruskal(3, new List<(int waga, int a, int b)> { (1, 0, 1), (3, 0, 2), (2, 1, 2) }); Console.WriteLine(string.Join(" ", wynik.Select(k => $"{k.a}-{k.b}({k.waga})")));
    }
}

Przykład uruchomienia: var wynik = Kruskal(3, new List<(int waga, int a, int b)> { (1, 0, 1), (3, 0, 2), (2, 1, 2) }); Console.WriteLine(string.Join(" ", wynik.Select(k => $"{k.a}-{k.b}({k.waga})")));

Analiza złożoności Big-O

Big-O

Big-O mówi, jak rośnie czas lub pamięć algorytmu, gdy rośnie liczba danych. Nie mierzy sekund, tylko tempo wzrostu: O(n) rośnie liniowo, O(log n) bardzo wolno, O(n²) szybko robi się kosztowne.

policz dominującą pętlę lub rekurencję
pomijaj stałe
porównuj algorytmy dla dużych danych

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void PokazBigO(int[] tablica)
    {
        // O(n) - jedna pętla po tablicy
        foreach (int liczba in tablica) Console.Write(liczba + " ");
        Console.WriteLine();

        // O(n^2) - pętla w pętli
        foreach (int a in tablica)
            foreach (int b in tablica)
                Console.Write($"({a},{b}) ");
    }

    static void Main()
    {
        PokazBigO(new[] {1, 2, 3});
    }
}

Przykład uruchomienia: PokazBigO(new[] {1, 2, 3});

Komentarz i wyjaśnienie kodu

Nie trzeba uczyć się wszystkich przykładów naraz. Najpierw wybierz algorytmy liczbowe i wyszukiwanie, potem sortowanie, a na końcu rekurencję, programowanie dynamiczne i grafy.

Ćwiczenie samodzielne

Wybierz trzy karty. Dla każdej: przepisz kod ręcznie, uruchom go dla innych danych i dopisz komentarz własnymi słowami, co robi każda ważna linia.

Zadania do pracy własnej

Wybierz 5 algorytmów i przygotuj do każdego po dwa testy danych wejściowych.
Porównaj dwa algorytmy rozwiązujące podobny problem, np. wyszukiwanie liniowe i binarne albo sortowanie bąbelkowe i szybkie.
Wybierz jeden trudniejszy algorytm: Dijkstra, Kruskal, LCS albo hetmany. Narysuj dane wejściowe i opisz działanie krok po kroku.

Typowe błędy

Uruchamianie wyszukiwania binarnego na nieposortowanej tablicy.
Brak warunku stopu w rekurencji.
Mylenie liczby wierzchołków z liczbą krawędzi przy złożoności grafów.

Nawiązanie do egzaminu zawodowego

Algorytmy wspierają programowanie konsolowe, desktopowe i mobilne w INF.04. To fundament do pisania kodu, który nie tylko działa, ale działa przewidywalnie i wydajnie.