Riešenia (skupina D, 5. týždeň)

import java.util.Arrays;

public abstract class TriediaciAlgoritmus {

        /**
         * Aktualne usporiadavane pole
         */
        private int[] p;
                private int pocetPorovnani = 0;
                private int pocetVymen = 0;

        /**
         * Porovna prvky v poli na zadanych indexoch
         *
         * @return vrati zaporne cislo, ak p[idx1] < p[idx2],
         *                 0, ak p[idx1]==p[idx2], a
         *         kladne cislo, ak p[idx1] > p[idx2]
         */
        protected int porovnaj(int idx1, int idx2) {
                        pocetPorovnani ++;
                return p[idx1] - p[idx2];

                /*
                 * Alternativa:
                 * if (p[idx1] < p[idx2]) return -1;
                 * if (p[idx1] > p[idx2]) return 1;
                 * return 0;
                 */
        }

        /**
         * Vymeni prvky v usporiadavanom poli na zadanych indexoch
         */
        protected void vymen(int idx1, int idx2) {
                        pocetVymen++;
                int pom = p[idx1];
                p[idx1] = p[idx2];
                p[idx2] = pom;
        }

        /**
         * Vypise pole
         */
        protected void vypisPole() {
                Arrays.toString(p);
        }

        public void vypisInfo() {
                System.out.println("Pocet porovnani: " + pocetPorovnani);
                System.out.println("Pocet vymen: " + pocetVymen);
        }
        /**
         * Usporiada prvky v poli od najmensieho po najvacsie
         *
         * @param p
         *            pole, ktoreho prvky maju byt usporiadane
         */
        public void utried(int[] p) {
                this.p = p;
                pocetPorovnani = 0;
                pocetVymen = 0;
                utried(0, p.length - 1);
//                this.p = null;
        }

        /**
         * Metoda, ktora implementuje triedenie podla urciteho algoritmu
         * @param dlzkaPola dlzka (pocet prvkov) usporiadavaneho pola
         */
        protected abstract void utried(int odIdx, int poIdx);
}

import java.util.Arrays;


public class QuickSort extends TriediaciAlgoritmus {

        @Override
        protected void utried(int odIdx, int poIdx) {
                if (poIdx < odIdx)
                        return;

                //rozdelenie podla pivota
                int pivotIdx = rozdel(odIdx, poIdx);

                //rekurzivne volanie
                utried(odIdx, pivotIdx - 1);
                utried(pivotIdx + 1, poIdx);
        }

        public int rozdel(int odIdx, int poIdx) {
                int idx = odIdx;
                for (int i = odIdx; i <= poIdx - 1; i++)
                if (porovnaj(i, poIdx) < 0) {
                        vymen(i, idx);
                        idx++;
                }
                vymen(idx, poIdx);
                return idx;
        }

        public static void main(String[] args) {
//              int[] pole = new int[] {3, 9, 2, 7, 5, 4, 6, 11, 8, 4, 2};
//              int[] pole = new int[] {1,2,4,5,3,7,8,10,11,9,6};
                int[] pole = new int[] {11,10,9,8,7,6,5,4,3,2,1};
                System.out.println(Arrays.toString(pole));
                QuickSort qs = new QuickSort();
                qs.utried(pole);
                System.out.println(Arrays.toString(pole));
                qs.vypisInfo();
        }
}

import java.util.Arrays;

public class Stromy {

        public static int hodnotaVStrome(int[] pole, String cesta) {
                int j = 0;
                for (int i = 0; i < cesta.length(); i++) {
                        if ('L' == cesta.charAt(i)) {
                                j = 2*j + 1;
                        } else {
                                j = 2*j + 2;
                        }
                }
                if (j < pole.length) {
                        return pole[j];
                } else {
                        return -1;
                }
        }

        public static boolean jeHaldou(int[] pole){

                        for (int i = 0; i < pole.length; i++) {
                                if(2*i+1 < pole.length)
                                        if(pole[i] < pole[2*i+1]){
                                                return false;
                                        }       

                                if(2*i+2 < pole.length)
                                        if(pole[i] < pole[2*i+2]){
                                                return false;
                                        }       
                        }

                return true;

        }


        public static void main(String[] args) {
                Stromy s = new Stromy();
                        int[] pole = new int[] {10,9,6,5,8,4,2,3,1,7};
                System.err.println(hodnotaVStrome(pole, "LR"));
                System.out.println(s.jeHaldou(pole));
        }

}

import java.util.Arrays;

public class MergeSort {

        public static int[] zluc(int[] p1, int[] p2) {
                int i1 = 0;
                int i2 = 0;
                int[] novePole = new int[p1.length + p2.length];

                while (i1 < p1.length && i2 < p2.length) {
                        if (p1[i1] < p2[i2]) {
                                novePole[i1 + i2] = p1[i1];
                                i1++;
                        } else {
                                novePole[i1 + i2] = p2[i2];
                                i2++;
                        }

                }
                while (i1 < p1.length) {
                        novePole[i1 + i2] = p1[i1];
                        i1++;
                }
                while (i2 < p2.length) {
                        novePole[i1 + i2] = p2[i2];
                        i2++;
                }
                return novePole;
        }

        public static void main(String[] args) {
                System.out.println(Arrays.toString(MergeSort.zluc(new int[] { 1, 5, 7,
                                9, 10 }, new int[] { 5, 6, 7, 8 })));
        }
}
 

import java.awt.event.MouseEvent;

import sk.upjs.jpaz2.*;

public class GrafickyEditor extends WinPane {

        private Turtle pero;

        private boolean jeZatlaceneLave = false;

        public GrafickyEditor() {
                this.pero = new Turtle();
                this.add(this.pero);
        }

        @Override
        protected void onMouseClicked(int x, int y, MouseEvent detail) {
                this.pero.setPosition(x, y);
        }

        @Override
        protected void onMouseMoved(int x, int y, MouseEvent detail) {
                if (detail.isAltDown()) {
                        this.pero.setDirection(this.pero.getDirectionTowards(x, y));
                        double dlzka = this.pero.distanceTo(x, y);
                        this.pero.step(dlzka);
                        this.pero.step(-dlzka);
                }
        }

        @Override
        protected void onMouseDragged(int x, int y, MouseEvent detail) {
                if (this.jeZatlaceneLave) {
                        this.pero.moveTo(x, y);
                }
        }

        @Override
        protected void onMousePressed(int x, int y, MouseEvent detail) {
                if (detail.getButton() == MouseEvent.BUTTON1) {
                        this.jeZatlaceneLave = true;
                }
        }

        @Override
        protected void onMouseReleased(int x, int y, MouseEvent detail) {
                if (detail.getButton() == MouseEvent.BUTTON1) {
                        this.jeZatlaceneLave = false;
                }
        }
}

import java.awt.Color;
import java.awt.event.MouseEvent;

import sk.upjs.jpaz2.JPAZUtilities;
import sk.upjs.jpaz2.Turtle;
import sk.upjs.jpaz2.WinPane;

public class Korytnackovo extends WinPane {

        private Turtle[] korytnacky;

        public Korytnackovo() {
                this.korytnacky = new Turtle[10];
                for (int i = 0; i < this.korytnacky.length; i++) {
                        this.korytnacky[i] = new Turtle();
                        this.add(this.korytnacky[i]);
                        this.korytnacky[i].setPosition(Math.random() * this.getWidth(),
                                        Math.random() * this.getHeight());
                }

                this.nahodneFarby();
        }

        public void posunITu(int idx, double dlzka) {
                this.korytnacky[idx].step(dlzka);
        }

        public void nahodneFarby() {
                for (int i = 0; i < this.korytnacky.length; i++) {
                        this.korytnacky[i].setPenColor(new Color(
                                        (int) (Math.random() * 256), (int) (Math.random() * 256),
                                        (int) (Math.random() * 256)));
                }
        }

        public Color sFarbouVon(int index) {
                return this.korytnacky[index].getPenColor();
        }

        @Override
        protected void onMouseClicked(int x, int y, MouseEvent detail) {
                int nahodnyIndex = (int) (Math.random() * this.korytnacky.length);
                this.korytnacky[nahodnyIndex].setPosition(x, y);
        }

        public void krok() {
                for (int i = 0; i < this.korytnacky.length; i++) {
                        int indexDalsej = (i + 1) % this.korytnacky.length;
                        double smerKDalsej = this.korytnacky[i]
                                        .getDirectionTowards(this.korytnacky[indexDalsej]
                                                        .getPosition());

                        double vzdialenostKDalsej = this.korytnacky[i]
                                        .distanceTo(this.korytnacky[indexDalsej].getPosition());

                        this.korytnacky[i].setDirection(smerKDalsej);
                        this.korytnacky[i].step(vzdialenostKDalsej / 10);
                }
        }

        public void kroky(int pocetKrokov) {
                for (int i = 0; i < pocetKrokov; i++) {
                        this.krok();
                        JPAZUtilities.delay(100);
                }
        }

        public void doKruhu(double polomer) {
                Turtle pomocnik = new Turtle();
                this.add(pomocnik);
                pomocnik.center();
                pomocnik.penUp();

                for (int i = 0; i < this.korytnacky.length; i++) {
                        pomocnik.step(polomer);
                        this.korytnacky[i].setPosition(pomocnik.getX(), pomocnik.getY());
                        pomocnik.step(-polomer);
                        pomocnik.turn(360.0 / this.korytnacky.length);
                }

                this.remove(pomocnik);
        }
}

import sk.upjs.jpaz2.*;

public class Spustac {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // GrafickyEditor msPaint = new GrafickyEditor();
                Korytnackovo upjs = new Korytnackovo();
                ObjectInspector oi = new ObjectInspector();
                oi.inspect(upjs);
        }

}

import java.awt.Color;
import java.awt.event.MouseEvent;

import sk.upjs.jpaz2.ImageTurtleShape;
import sk.upjs.jpaz2.Turtle;
import sk.upjs.jpaz2.WinPane;

public class Farma extends WinPane {

        /**
         * Instancna premenna refercujuca pole (polovy objekt) int-ov. I-ty prvok
         * pola uchovava informaciu o tom, kolko kvetin mame vysadenych v i-tom
         * zahone.
         */
        private int[] zahony;

        /**
         * Nakresli deliace hranice pre zahony
         *
         * @param pocetZahonov
         *            pocet zahonov, pre ktore kreslime hranicu
         */
        public void kresliZahony(int pocetZahonov) {
                // Korytnacka kreslic
                Turtle kreslic = new Turtle();
                this.add(kreslic);

                // Nakreslime vertikalne ciary
                int sirkaZahonu = this.getWidth() / pocetZahonov;
                for (int i = 0; i < pocetZahonov - 1; i++) {
                        kreslic.setPosition((i + 1) * sirkaZahonu, 0);
                        kreslic.moveTo((i + 1) * sirkaZahonu, this.getHeight());
                }

                // Kreslica odstranime z farmy (kresliacej plochy)
                this.remove(kreslic);
        }

        /**
         * Zasadi kvietok na zadane suradnice
         *
         * @param x
         *            x-ova suradnica pre sadeny kvietok
         * @param y
         *            y-ova suradnica pre sadeny kvietok
         */
        public void zasadKvietok(int x, int y) {
                // Kreslic ...
                Turtle kreslic = new Turtle();
                // Zmenime tvar korynacky podla obrazku v grafickom subore
                kreslic.setShape(new ImageTurtleShape("kvietok.png"));
                // Kreslica pridame do plochy a nechame ho otlacit svoj tvar do
                // kresliacej plochy
                this.add(kreslic);
                kreslic.setPosition(x, y);
                kreslic.stamp();
                // No a nakoniec kreslica odstranime z farmy
                this.remove(kreslic);

                // Vypocitame si sirku jedneho zahonu
                int sirkaZahonu = this.getWidth() / this.pocetZahonov();
                // Vypocitame si index zahonu, do ktoreho sme klikli
                int kliknutyZahon = x / sirkaZahonu;
                // V poli si poznacime, ze v danom zahone sme posadili novy kvietok
                this.zahony[kliknutyZahon]++;
        }

        /**
         * Vrati pocet zahonov
         */
        public int pocetZahonov() {
                return this.zahony.length;
        }

        /**
         * Vrati pocet kvietkov v zadanom zahone
         *
         * @param indexZahonu
         *            index zahonu na farme
         */
        public int vZahone(int indexZahonu) {
                return this.zahony[indexZahonu];
        }

        /**
         * Vrati pocet zahonov, kde je viac ako hranica kvetiniek
         */
        public int sViacAko(int hranica) {
                int pocitadlo = 0;

                // Prechadzame vsetky zahony
                for (int i = 0; i < this.zahony.length; i++) {
                        // Ak ma i-ty zahon viac ako hranica kvetiniek, tak zvysime
                        // pocitadlo o 1
                        if (this.zahony[i] > hranica) {
                                pocitadlo++;
                        }
                }

                return pocitadlo;
        }

        /**
         * Overime, ci v kazdom zahone je aspon jeden kvietok
         */
        public boolean vsadeNieco() {
                // Prechadzame vsetky zahony
                for (int i = 0; i < this.zahony.length; i++) {
                        // Ak v i-tom zahone niet kvetiniek, tak koncime s false
                        if (this.zahony[i] == 0) {
                                return false;
                        }
                }

                // Ak sme sa dostali sem, tak v kazdom zahone musel byt aspon jeden
                // kvietok
                return true;
        }

        /**
         * Vrati index zahonu, v ktorom je najvacsi pocet kvetiniek
         */
        public int najZahon() {
                // Index zahonu, ktory je kandidatom na najkvietkovanejsi zahon
                int najIndex = 0;
                // Prechadzame vsetky zahony
                for (int i = 1; i < this.zahony.length; i++) {
                        // Ak v i-tom zahone je viac kvetin, ako ma kandidat, tak mame
                        // lepsieho kandidata
                        if (this.zahony[i] > this.zahony[najIndex]) {
                                najIndex = i;
                        }
                }

                return najIndex;
        }

        @Override
        protected void onMouseClicked(int x, int y, MouseEvent detail) {
                this.zasadKvietok(x, y);
        }

        public int pocetKvetin(int odZahonuIdx, int poZahonIdx) {
                int vysledok = 0;
                for (int i = odZahonuIdx; i <= poZahonIdx; i++) {
                        vysledok = vysledok + zahony[i];
                }

                return vysledok;
        }

        public double priemernyPocetVZahone() {
                /*
                 * int vysledok = 0; for (int i=0; i<zahony.length; i++) { vysledok =
                 * vysledok + zahony[i]; }
                 *
                 * return vysledok/(double)zahony.length;
                 */
                return this.pocetKvetin(0, zahony.length) / (double) zahony.length;
        }

        /**
         * "Inicializacna metoda", ktora zabezpeci vykonanie prikazov hned po
         * vytvoreni objektu triedy Farma
         */
        public Farma() {
                // Zmenime rozmery kresliacej plochy
                this.resize(500, 300);
                // Nastavime farbu pozadia
                this.setBackgroundColor(new Color(255, 211, 155));
                // Vytvorime pole s poctom prvkom 7 (dokaze uchovat 7 int-ov).
                // Referenciu na vytvorene pole ulozime do instancnej premennej zahony
                this.zahony = new int[7];
                // Nechame nakreslit hranice zahonov podla velkosti pola
                this.kresliZahony(this.zahony.length);
        }
}

import java.awt.Color;
import java.awt.event.MouseEvent;

import sk.upjs.jpaz2.JPAZUtilities;
import sk.upjs.jpaz2.Turtle;
import sk.upjs.jpaz2.WinPane;

public class Korytnackovo extends WinPane {

        private Turtle[] korytnacky;

        public Korytnackovo() {
                this.korytnacky = new Turtle[10];
                for (int i = 0; i < this.korytnacky.length; i++) {
                        this.korytnacky[i] = new Turtle();
                        this.add(this.korytnacky[i]);
                        this.korytnacky[i].setPosition(Math.random() * this.getWidth(),
                                        Math.random() * this.getHeight());
                }

                this.nahodneFarby();
        }

        public void posunITu(int idx, double dlzka) {
                this.korytnacky[idx].step(dlzka);
        }

        public void nahodneFarby() {
                for (int i = 0; i < this.korytnacky.length; i++) {
                        this.korytnacky[i].setPenColor(new Color(
                                        (int) (Math.random() * 256), (int) (Math.random() * 256),
                                        (int) (Math.random() * 256)));
                }
        }

        public Color sFarbouVon(int index) {
                return this.korytnacky[index].getPenColor();
        }

        @Override
        protected void onMouseClicked(int x, int y, MouseEvent detail) {
                int nahodnyIndex = (int) (Math.random() * this.korytnacky.length);
                this.korytnacky[nahodnyIndex].setPosition(x, y);
        }

        public void krok() {
                for (int i = 0; i < this.korytnacky.length; i++) {
                        int indexDalsej = (i + 1) % this.korytnacky.length;
                        double smerKDalsej = this.korytnacky[i]
                                        .getDirectionTowards(this.korytnacky[indexDalsej]
                                                        .getPosition());

                        double vzdialenostKDalsej = this.korytnacky[i]
                                        .distanceTo(this.korytnacky[indexDalsej].getPosition());

                        this.korytnacky[i].setDirection(smerKDalsej);
                        this.korytnacky[i].step(vzdialenostKDalsej / 10);
                }
        }

        public void kroky(int pocetKrokov) {
                for (int i = 0; i < pocetKrokov; i++) {
                        this.krok();
                        JPAZUtilities.delay(100);
                }
        }

        public void doKruhu(double polomer) {
                Turtle pomocnik = new Turtle();
                this.add(pomocnik);
                pomocnik.center();
                pomocnik.penUp();

                for (int i = 0; i < this.korytnacky.length; i++) {
                        pomocnik.step(polomer);
                        this.korytnacky[i].setPosition(pomocnik.getX(), pomocnik.getY());
                        pomocnik.step(-polomer);
                        pomocnik.turn(360.0 / this.korytnacky.length);
                }

                this.remove(pomocnik);
        }

        public int pocetTopKorytnaciek(double zhora) {
                int pocet = 0;
                for (int i = 0; i < korytnacky.length; i++) {
                        if (korytnacky[i].getY() < zhora) {
                                pocet++;
                        }
                }
                return pocet;
        }

        public void bezpecnyKruh(int indexKorytnacky) {
                double najmensia = Double.POSITIVE_INFINITY;
                for (int i = 0; i < korytnacky.length; i++) {
                        if (i != indexKorytnacky) {
                                double vzd = korytnacky[indexKorytnacky].distanceTo(
                                                korytnacky[i].getX(), korytnacky[i].getY());
                                if (vzd < najmensia) {
                                        najmensia = vzd;
                                }

                        }
                }

                korytnacky[indexKorytnacky].dot(najmensia);
        }

        public double najblizsie() {
                double vysledok = Double.POSITIVE_INFINITY;
                for (int i = 0; i < korytnacky.length; i++) {
                        for (int j = i+1; j < korytnacky.length; j++) {
                                double vzd = korytnacky[i].distanceTo(korytnacky[j]
                                                .getPosition());

                                if (vzd < vysledok) {
                                        vysledok = vzd;
                                }
                        }
                }

                return vysledok;
        }
}