Implementacja algorytmu (wersja rekurencyjna)

1. Algorytm znajduje rozwiązanie wykonując 2*(n‑1) porównań (I wersja)

Linia 1. def min podkreślnik max podkreślnik rek otwórz nawias okrągły tablica przecinek indeks znak równości 0 przecinek minimum znak równości None przecinek maksimum znak równości None zamknij nawias okrągły dwukropek. Linia 2. if indeks znak równości znak równości 0 dwukropek. Linia 3. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 4. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 6. if indeks znak równości znak równości len otwórz nawias okrągły tablica zamknij nawias okrągły dwukropek. Linia 7. return minimum przecinek maksimum. Linia 9. if tablica otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny minimum dwukropek. Linia 10. minimum znak równości tablica otwórz nawias kwadratowy indeks zamknij nawias kwadratowy. Linia 11. if tablica otwórz nawias kwadratowy indeks zamknij nawias kwadratowy zamknij nawias ostrokątny maksimum dwukropek. Linia 12. maksimum znak równości tablica otwórz nawias kwadratowy indeks zamknij nawias kwadratowy. Linia 14. return min podkreślnik max podkreślnik rek otwórz nawias okrągły tablica przecinek indeks plus 1 przecinek minimum przecinek maksimum zamknij nawias okrągły. Linia 15. tablica znak równości otwórz nawias kwadratowy minus 23 przecinek 56 przecinek 0 przecinek minus 9 przecinek 128 zamknij nawias kwadratowy. Linia 16. print otwórz nawias okrągły min podkreślnik max podkreślnik rek otwórz nawias okrągły tablica zamknij nawias okrągły zamknij nawias okrągły.

Jak działa program?

  • Funkcja wywołuje samą siebie dla kolejnego indeksu.

  • Każde wywołanie przetwarza jeden element.

  • Przypadek podstawowy: gdy indeks dojdzie do końca tablicy.

2. Algorytm znajduje rozwiązanie korzystając z efektywniejszego algorytmu min‑max** (II wersja)

Rekurencyjnie: dziel i zwyciężaj - Jak to działa?

  • Podziel listę na dwie połowy.

  • Znajdź min i max w lewej połowie.

  • Znajdź min i max w prawej połowie.

  • Połącz wyniki.

Linia 1. def min podkreślnik max podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły tablica przecinek lewy przecinek prawy zamknij nawias okrągły dwukropek. Linia 2. kratka jeden element. Linia 3. if lewy znak równości znak równości prawy dwukropek. Linia 4. return tablica otwórz nawias kwadratowy lewy zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy lewy zamknij nawias kwadratowy. Linia 6. kratka dwa elementy. Linia 7. if prawy znak równości znak równości lewy plus 1 dwukropek. Linia 8. if tablica otwórz nawias kwadratowy lewy zamknij nawias kwadratowy otwórz nawias ostrokątny tablica otwórz nawias kwadratowy prawy zamknij nawias kwadratowy dwukropek. Linia 9. return tablica otwórz nawias kwadratowy lewy zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy prawy zamknij nawias kwadratowy. Linia 10. else dwukropek. Linia 11. return tablica otwórz nawias kwadratowy prawy zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy lewy zamknij nawias kwadratowy. Linia 13. kratka więcej elementów – dzielimy problem. Linia 14. srodek znak równości otwórz nawias okrągły lewy plus prawy zamknij nawias okrągły prawy ukośnik prawy ukośnik 2. Linia 16. min podkreślnik l przecinek max podkreślnik l znak równości min podkreślnik max podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły tablica przecinek lewy przecinek srodek zamknij nawias okrągły. Linia 17. min podkreślnik p przecinek max podkreślnik p znak równości min podkreślnik max podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły tablica przecinek srodek plus 1 przecinek prawy zamknij nawias okrągły. Linia 19. return min otwórz nawias okrągły min podkreślnik l przecinek min podkreślnik p zamknij nawias okrągły przecinek max otwórz nawias okrągły max podkreślnik l przecinek max podkreślnik p zamknij nawias okrągły.