Metoda iteracyjna - Algorytm jednoczesnego wyszukiwania minimum i maksimum - I_R_W14_M25_Java Szukanie jednoczesne min‑max

R1QX9EB6BE8D1

Zastosowane iteracji do równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartości.

Metoda iteracyjna polega na przeglądaniu elementów zbioru krok po kroku z wykorzystaniem pętli. W algorytmie jednoczesnego znajdowania minimum i maksimum celem jest takie zorganizowanie iteracji, aby w jednym przebiegu danych określić zarówno najmniejszą, jak i największą wartość.

Na początku algorytmu przyjmujemy, że pierwszy element tablicy jest jednocześnie minimum i maksimum. Następnie, w kolejnych krokach, każdy następny element jest porównywany z aktualnymi wartościami minimum i maksimum. Jeśli rozpatrywany element jest mniejszy od aktualnego minimum, to minimum zostaje zaktualizowane. Jeżeli natomiast jest większy od aktualnego maksimum, to maksimum zostaje zaktualizowane.

W bardziej efektywnej wersji iteracyjnej elementy są porównywane parami. Najpierw porównuje się dwa sąsiednie elementy, aby ustalić, który z nich jest mniejszy, a który większy. Następnie mniejszy z pary porównywany jest tylko z aktualnym minimum, a większy tylko z aktualnym maksimum. Takie podejście pozwala zmniejszyć liczbę porównań i zwiększyć wydajność algorytmu.

Metoda iteracyjna jest łatwa do implementacji, wydajna czasowo i nie wymaga dodatkowej pamięci, dlatego jest najczęściej stosowanym sposobem realizacji algorytmu jednoczesnego wyszukiwania minimum i maksimum w praktycznych programach.

Linia 1. funkcja MinMax otwórz nawias okrągły A otwórz nawias kwadratowy 1 kropka kropka n zamknij nawias kwadratowy zamknij nawias okrągły. Linia 3. jeżeli n znak równości 0 dwukropek. Linia 4. zwróć 0. Linia 6. jeżeli n znak równości 1 dwukropek. Linia 7. min ← A otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 8. max ← A otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 9. zwróć otwórz nawias okrągły min przecinek max zamknij nawias okrągły. Linia 11. jeżeli A otwórz nawias kwadratowy 1 zamknij nawias kwadratowy otwórz nawias ostrokątny A otwórz nawias kwadratowy 2 zamknij nawias kwadratowy. Linia 12. min ← A otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 13. max ← A otwórz nawias kwadratowy 2 zamknij nawias kwadratowy. Linia 14. w przeciwnym wypadku dwukropek. Linia 15. min ← A otwórz nawias kwadratowy 2 zamknij nawias kwadratowy. Linia 16. max ← A otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 18. dla i ← 3 DO n dwukropek. Linia 19. jeżeli i znak równości n dwukropek. Linia 20. jeżeli A otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny min. Linia 21. min ← A otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 22. jeżeli A otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny max dwukropek. Linia 23. max ← A otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 24. w przeciwnym wypadku dwukropek. Linia 25. jeżeli A otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny A otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy dwukropek. Linia 26. mniejszy ← A otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 27. większy ← A otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy. Linia 28. w przeciwnym wypadku dwukropek. Linia 29. mniejszy ← A otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy. Linia 30. większy ← A otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 32. jeżeli mniejszy otwórz nawias ostrokątny min dwukropek. Linia 33. min ← mniejszy. Linia 34. jeżeli większy zamknij nawias ostrokątny max dwukropek. Linia 35. max ← większy. Linia 37. zwróc otwórz nawias okrągły min przecinek max zamknij nawias okrągły.

funkcja MinMax(A[1..n])

    jeżeli n = 0:
        zwróć 0

    jeżeli n = 1:
        min ← A[1]
        max ← A[1]
        zwróć (min, max)

    jeżeli A[1] < A[2]
        min ← A[1]
        max ← A[2]
    w przeciwnym wypadku:
        min ← A[2]
        max ← A[1]

    dla i ← 3 DO n:
        jeżeli i = n:
            jeżeli A[i] < min
                min ← A[i]
            jeżeli A[i] > max:
                max ← A[i]
        w przeciwnym wypadku:
            jeżeli A[i] < A[i+1]:
                mniejszy ← A[i]
                większy ← A[i+1]
            w przeciwnym wypadku:
                mniejszy ← A[i+1]
                większy ← A[i]

            jeżeli mniejszy < min:
                min ← mniejszy
            jeżeli większy > max:
                max ← większy

    zwróc(min, max)

Słownik

iteracja

(z łac. iteratio) powtarzanie w pętli tych samych instrukcji aż do spełnienia pewnego warunku

metoda „dziel i zwyciężaj”

metoda polegająca na podzieleniu problemu na mniejsze, prostsze do rozwiązania podproblemy; po całkowitym rozbiciu problemu oraz rozwiązaniu podproblemów, łączymy je z powrotem w całość i rozwiązujemy cały problem

rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

rozwiązanie naiwne

najprostsze, bezpośrednie rozwiązanie danego problemu, pozbawione jakichkolwiek usprawnień i optymalizacji, przez co zazwyczaj jest to rozwiązanie nieoptymalne; przykładami mogą być algorytmy, które sprawdzają wszystkie możliwe rozwiązania (podczas gdy wystarczyłoby sprawdzenie tylko części), przeszukują całe zbiory danych (podczas gdy wystarczyłoby tylko częściowe przeszukiwanie) itp.

złożoność czasowa

czas niezbędny do rozwiązania określonego problemu, podawany zazwyczaj w liczbach operacji dominujących; złożoność czasowa zależy od ilości danych wejściowych

Na dobry początek

Implementacja algorytmu

Zastosowane iteracji do równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartości.

Słownik