Implementacja algorytmu - I_R_W14_M25_Java Szukanie jednoczesne min‑max

R1QX9EB6BE8D1

Metoda „Dziel i zwyciężaj” (ang. Divide and Conquer) to potężna technika projektowania algorytmów, która polega na rozbiciu złożonego problemu na mniejsze, łatwiejsze do rozwiązania podproblemy tego samego typu.

Proces ten składa się z trzech głównych kroków:

Dziel (Divide): Rozdzielamy problem na mniejsze części (zwykle na dwie połowy).
Zwyciężaj (Conquer): Rozwiązujemy te mniejsze problemy (często rekurencyjnie). Jeśli problem jest wystarczająco mały (przypadek bazowy), rozwiązujemy go bezpośrednio.
Połącz (Combine): Łączymy rozwiązania mniejszych części w jedno rozwiązanie problemu głównego.

W przypadku szukania minimum i maksimum, zamiast porównywać każdy element po kolei, dzielimy tablicę na pół, aż otrzymamy segmenty jedno- lub dwuelementowe.

Implementacja algorytmu w języku Java

Ćwiczenie 1

Napisz program, który wykorzystując metodę bąbelkową, wyznaczy i przesunie na początek ciągu liczbowego (reprezentowanego w programie jako tablica) najmniejszy jego wyraz. Po wyznaczeniu i przesunięciu najmniejszego wyrazu na początek ciągu, wypisz go.

Specyfikacja problemu:

Dane:

ciag – ciąg liczb całkowitych zapisany w tablicy; tablica liczb całkowitych
n – długość ciągu (rozmiar tablicy); liczba całkowita

Wynik:

najmniejszaLiczba – najmniejszy wyraz ciągu; liczba całkowita

R1OFRJ9PV6GQ9

Przykładowe rozwiązanie zadania

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. prawy ukośnik asterysk asterysk. Linia 4. asterysk Implementacja algorytmu MinMax metodą dziel i zwyciężaj kropka. Linia 5. asterysk at param tablica minus tablica wejściowa. Linia 6. asterysk at param pocz minus indeks początkowy. Linia 7. asterysk at param kon minus indeks końcowy. Linia 8. asterysk at return int otwórz nawias kwadratowy zamknij nawias kwadratowy gdzie otwórz nawias kwadratowy 0 zamknij nawias kwadratowy to min przecinek a otwórz nawias kwadratowy 1 zamknij nawias kwadratowy to max. Linia 9. asterysk prawy ukośnik. Linia 10. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy znajdzMinMax otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tablica przecinek int pocz przecinek int kon zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. prawy ukośnik prawy ukośnik Przypadek bazowy 1 dwukropek Tylko jeden element w przedziale. Linia 12. if otwórz nawias okrągły kon znak równości znak równości pocz zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy zamknij nawias klamrowy średnik. Linia 14. zamknij nawias klamrowy. Linia 16. prawy ukośnik prawy ukośnik Przypadek bazowy 2 dwukropek Dwa elementy w przedziale. Linia 17. if otwórz nawias okrągły kon znak równości znak równości pocz plus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. if otwórz nawias okrągły tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy zamknij nawias klamrowy średnik. Linia 20. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 21. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy zamknij nawias klamrowy średnik.

public class Main {

   /**
    * Implementacja algorytmu MinMax metodą dziel i zwyciężaj.
    * @param tablica - tablica wejściowa
    * @param pocz - indeks początkowy
    * @param kon - indeks końcowy
    * @return int[] gdzie [0] to min, a [1] to max
    */
   public static int[] znajdzMinMax(int[] tablica, int pocz, int kon) {
       // Przypadek bazowy 1: Tylko jeden element w przedziale
       if (kon == pocz) {
           return new int[]{tablica[pocz], tablica[pocz]};
       }

       // Przypadek bazowy 2: Dwa elementy w przedziale
       if (kon == pocz + 1) {
           if (tablica[pocz] <= tablica[kon]) {
               return new int[]{tablica[pocz], tablica[kon]};
           } else {
               return new int[]{tablica[kon], tablica[pocz]};

Linia 1. zamknij nawias klamrowy. Linia 4. prawy ukośnik prawy ukośnik DZIEL dwukropek Wyznaczamy środek i dzielimy na dwa podproblemy. Linia 5. int polowa znak równości otwórz nawias okrągły pocz plus kon zamknij nawias okrągły prawy ukośnik 2 średnik. Linia 7. prawy ukośnik prawy ukośnik ZWYCIĘŻAJ dwukropek Rekurencyjne wywołania dla lewej i prawej strony. Linia 8. int otwórz nawias kwadratowy zamknij nawias kwadratowy lewa znak równości znajdzMinMax otwórz nawias okrągły tablica przecinek pocz przecinek polowa zamknij nawias okrągły średnik. Linia 9. int otwórz nawias kwadratowy zamknij nawias kwadratowy prawa znak równości znajdzMinMax otwórz nawias okrągły tablica przecinek polowa plus 1 przecinek kon zamknij nawias okrągły średnik. Linia 11. prawy ukośnik prawy ukośnik POŁĄCZ dwukropek Wybieramy globalne min i max z obu połówek. Linia 12. int min znak równości Math kropka min otwórz nawias okrągły lewa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek prawa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 13. int max znak równości Math kropka max otwórz nawias okrągły lewa otwórz nawias kwadratowy 1 zamknij nawias kwadratowy przecinek prawa otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 15. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy min przecinek max zamknij nawias klamrowy średnik.
   }


   // DZIEL: Wyznaczamy środek i dzielimy na dwa podproblemy
   int polowa = (pocz + kon) / 2;

   // ZWYCIĘŻAJ: Rekurencyjne wywołania dla lewej i prawej strony
   int[] lewa = znajdzMinMax(tablica, pocz, polowa);
   int[] prawa = znajdzMinMax(tablica, polowa + 1, kon);

   // POŁĄCZ: Wybieramy globalne min i max z obu połówek
   int min = Math.min(lewa[0], prawa[0]);
   int max = Math.max(lewa[1], prawa[1]);

   return new int[]{min, max};
}
public static void main(String[] args) { int[] dane = {34, 7, 23, 32, 5, 62, 12, 1};
Linia 1. prawy ukośnik prawy ukośnik Wywołujemy funkcję dla całego zakresu tablicy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy wynik znak równości znajdzMinMax otwórz nawias okrągły dane przecinek 0 przecinek dane kropka length minus 1 zamknij nawias okrągły średnik. Linia 4. System kropka out kropka println otwórz nawias okrągły cudzysłów Znalezione minimum dwukropek cudzysłów plus wynik otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 5. System kropka out kropka println otwórz nawias okrągły cudzysłów Znalezione maksimum dwukropek cudzysłów plus wynik otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik.
   // Wywołujemy funkcję dla całego zakresu tablicy
   int[] wynik = znajdzMinMax(dane, 0, dane.length - 1);

    System.out.println("Znalezione minimum: " + wynik[0]);
   System.out.println("Znalezione maksimum: " + wynik[1]);
} }

Metoda dziel i zwyciężaj - Algorytm jednoczesnego wyszukiwania minimum i maksimum

Strefa wyzwań

Implementacja algorytmu w języku Java