ADS - Matičky

class Sroubky_A_Maticky
{
    // Předpokládejme, že matičky, respektive šroubky, jsou od sebe rozlišitelné pouze podle jejich velikosti.
    // Velikost matiček, respektive šroubků, budeme reprezentovat pomocí přirozených čísel.
    // Každá matička a každý šroubek má svůj index.
    public struct CoKamPasuje // V této struktuře si pamatuji, jaký šroubek pasuje na jakou matičku. Tedy jsou zde jejich indexy.
    {
        public uint Co;
        public uint Kam;
    }
    public List<CoKamPasuje> Tabulka = new List<CoKamPasuje>();
    public List<uint> Sroubky = new List<uint>();
    public List<uint> Maticky = new List<uint>();
    public Sroubky_A_Maticky(List<uint> Sroubky, List<uint> Maticky) // Vložíme seznam matiček a šroubků tak, jak jsou na stole vyskládané za sebou.
    {
        this.Sroubky = Sroubky;
        this.Maticky = Maticky;
    }

    // V následující metodě budeme vyplňovat tabulku, jaký šroubek psauje na jakou matičku.
    // Budeme postupně dělit seznam šroubků na poloviny až do doby, dokud nezůstane jeden šroubek.
    // Pak nalezneme vhodnou matičku a indexy zapíšeme do tabulky.

    // Dle Master Theoremu T(n) = 2 * T(n/2) + O(n)
    // Tedy 2/2^1 = 1 → T(n) = O(n * log n)
    public void NajdiOdpovidajiciDvojice(List<uint> Sroubky)
    {
        if (Sroubky.Count == 1)
        {
            foreach (uint Maticka in Maticky)
                if (Sroubky.First() == Maticka)
                {
                    CoKamPasuje JedenVyskyt;
                    JedenVyskyt.Co = (uint)this.Sroubky.IndexOf(Sroubky.First());
                    JedenVyskyt.Kam = (uint)Maticky.IndexOf(Maticka);
                    Tabulka.Add(JedenVyskyt);
                    break;
                }
        }

        else
        {
            NajdiOdpovidajiciDvojice(Sroubky.GetRange(0, Sroubky.Count / 2));
            NajdiOdpovidajiciDvojice(Sroubky.GetRange(Sroubky.Count / 2, Sroubky.Count / 2));
        }
    }
}