Riešenia (skupina E, 6. týždeň)

import java.util.Arrays;

public class Generator {
        int[] mnozina;
        int[] variacia;
        int pocet;

        public void variacieSOpakovanim(int k, int[] mnozina) {
                this.mnozina = mnozina;
                variacia = new int[k];

                variacieSOpakovanim(k, 0);
        }

        private void variacieSOpakovanim(int k, int idx) {
                if (k == idx) {
                        vypis();
                        return;
                }

                for (int i = 0; i < mnozina.length; i++) {
                        variacia[idx] = mnozina[i];
                        variacieSOpakovanim(k, idx + 1);
                }
        }

        public void variacieBezOpakovania(int k, int[] mnozina) {
                this.mnozina = mnozina;
                variacia = new int[k];

                boolean[] hodnoty = new boolean[mnozina.length];
                Arrays.fill(hodnoty, false);
                variacieBezOpakovania(k, 0, hodnoty);
        }

        private void variacieBezOpakovania(int k, int idx, boolean[] hodnoty) {
                if (k == idx) {
                        vypis();
                        return;
                }

                for (int i = 0; i < mnozina.length; i++) {
                        if (hodnoty[i])
                                continue;

                        hodnoty[i] = true;
                        variacia[idx] = mnozina[i];
                        variacieBezOpakovania(k, idx + 1, hodnoty);
                        hodnoty[i] = false;
                }
        }

        private void vypis() {
                pocet++;
                System.out.println(Arrays.toString(variacia));
        }

        public static void main(String[] args) {
                int[] mnozina = { 1, 2, 3 };
                Generator g = new Generator();
                g.variacieSOpakovanim(5, mnozina);

                System.out.println();
                System.out.println("Pocet = " + g.pocet);
        }
}

import java.util.Arrays;

public class Zlodeji {

        int pocetZlodejov;
        double[] lup;
        double ktinaLupu;
        int[] najspravodlivejsieRozdelenie;
        double najspravodlivejsiKoeficient;

        public void najdiNajspravodlivejsieRozdelenie(int pocetZlodejov, double[] lup) {
                this.pocetZlodejov = pocetZlodejov;
                this.lup = lup;
                najspravodlivejsiKoeficient = Double.MAX_VALUE;

                double suma = 0;
                for (int i = 0; i < lup.length; i++)
                        suma += lup[i];
                ktinaLupu = suma / lup.length;

                rozdel(0, new int[lup.length]);
        }

        private void rozdel(int idx, int[] rozdelenie) {
                if (idx == rozdelenie.length) {
                        spracujRozdelenie(rozdelenie);
                        return;
                }

                for (int i = 0; i < pocetZlodejov; i++) {
                        rozdelenie[idx] = i;
                        rozdel(idx + 1, rozdelenie);
                }
        }

        private void spracujRozdelenie(int[] rozdelenie) {
                // vypocitaj koeficient spravodlivosti
                double koeficient = 0;
                double[] sumy = new double[pocetZlodejov];
                Arrays.fill(sumy, 0);

                for (int i = 0; i < rozdelenie.length; i++)
                        sumy[rozdelenie[i]] += lup[i];

                for (int i = 0; i < sumy.length; i++)
                        koeficient += (sumy[i] - ktinaLupu) * (sumy[i] - ktinaLupu);

                // je dane rozdelenie spravodlivejsie ako to ktore mame?
                if (koeficient < najspravodlivejsiKoeficient) {
                        najspravodlivejsiKoeficient = koeficient;
                        najspravodlivejsieRozdelenie = rozdelenie.clone();
                }
        }

        public static void main(String[] args) {
                double[] lup = { 100, 50.4, 102, 108 };
                Zlodeji z = new Zlodeji();
                z.najdiNajspravodlivejsieRozdelenie(3, lup);

                System.out.println("Najspravodlivejsie rozdelenie je:");
                System.out.println(Arrays.toString(z.najspravodlivejsieRozdelenie));
        }
}

import java.util.Arrays;

public class NepriatelskeCisla {

        int[] cisla;
        int[] usporiadanie;
        boolean[] hodnoty;

        public void najdiUsporiadania(int[] cisla) {
                this.cisla = cisla;
                this.hodnoty = new boolean[cisla.length];
                Arrays.fill(hodnoty, false);
                this.usporiadanie = new int[cisla.length];

                hladaj(0);
        }

        private void hladaj(int idx) {
                if (idx == cisla.length) {
                        vypis();
                        return;
                }

                for (int i = 0; i < cisla.length; i++) {
                        if (hodnoty[i])
                                continue;

                        usporiadanie[idx] = cisla[i];
                        if (jeToDobre(idx)) {
                                hodnoty[i] = true;
                                hladaj(idx + 1);
                                hodnoty[i] = false;
                        }
                }
        }

        private boolean jeToDobre(int idx) {
                if (idx == 0)
                        return true;
                // skontrolujeme len poslednu dvojicu
                return (usporiadanie[idx - 1] % usporiadanie[idx] != 0)
                                && (usporiadanie[idx] % usporiadanie[idx - 1] != 0);
        }

        private void vypis() {
                System.out.println(Arrays.toString(usporiadanie));
        }

        public static void main(String[] args) {
                int[] cisla = { 2, 4, 5, 7, 8, 9, 3 };
                NepriatelskeCisla nc = new NepriatelskeCisla();
                nc.najdiUsporiadania(cisla);
        }
}

import java.util.Arrays;

public class ProblemDam {

        private static final int NEOBSADENE = -1;

        int rozmer;
        int[] indexyVStlpcoch;
        boolean[] volneStlpce;
        boolean[] uhloprieckyPL;
        boolean[] uhloprieckyLP;
        int pocetRieseni;

        public int najdiVsetkyRozmiestnenia(int rozmer) {
                this.rozmer = rozmer;
                indexyVStlpcoch = new int[rozmer];
                volneStlpce = new boolean[rozmer];
                uhloprieckyPL = new boolean[2 * rozmer - 1];
                uhloprieckyLP = new boolean[2 * rozmer - 1];
                pocetRieseni = 0;

                Arrays.fill(indexyVStlpcoch, NEOBSADENE);
                Arrays.fill(volneStlpce, true);
                Arrays.fill(uhloprieckyPL, true);
                Arrays.fill(uhloprieckyLP, true);

                hladajRiesenia(0);
                return pocetRieseni;
        }

        private void hladajRiesenia(int riadok) {
                if (riadok == rozmer) {
                        pocetRieseni++;
                        vypisRiesenie();
                        return;
                }

                for (int stlpec = 0; stlpec < rozmer; stlpec++) {
                        if (mozemPolozitDamu(riadok, stlpec)) {
                                polozDamu(riadok, stlpec);
                                hladajRiesenia(riadok + 1);
                                odstranDamu(riadok, stlpec);
                        }
                }
        }

        private boolean mozemPolozitDamu(int riadok, int stlpec) {
                boolean jeVolnyStlpec = volneStlpce[stlpec];
                boolean jeVolnaUhloprieckaRL = uhloprieckyPL[riadok + stlpec];
                boolean jeVolnaUhloprieckaLP = uhloprieckyLP[riadok - stlpec + rozmer - 1];

                return jeVolnyStlpec && jeVolnaUhloprieckaRL && jeVolnaUhloprieckaLP;
        }

        private void polozDamu(int riadok, int stlpec) {
                indexyVStlpcoch[riadok] = stlpec;
                volneStlpce[stlpec] = false;
                uhloprieckyPL[riadok + stlpec] = false;
                uhloprieckyLP[riadok - stlpec + rozmer - 1] = false;
        }

        private void odstranDamu(int riadok, int stlpec) {
                indexyVStlpcoch[riadok] = NEOBSADENE;
                volneStlpce[stlpec] = true;
                uhloprieckyPL[riadok + stlpec] = true;
                uhloprieckyLP[riadok - stlpec + rozmer - 1] = true;
        }

        private void vypisRiesenie() {
                for (int riadok = 0; riadok < rozmer; riadok++) {
                        for (int stlpec = 0; stlpec < rozmer; stlpec++)
                                System.out.print(indexyVStlpcoch[riadok] == stlpec ? "D " : "- ");
                        System.out.println();
                }
                System.out.println();
        }

        public static void main(String[] args) {
                ProblemDam pd = new ProblemDam();
                pd.najdiVsetkyRozmiestnenia(9);

                System.out.println();
                System.out.println("Pocet rieseni je " + pd.pocetRieseni);
        }
}