ALG"6

226 Rozdział 9. Zaawansowane techniki programowania

Ćwicz. 9-1

Proszę wyprowadzić wzory tłumaczące wartości (.v,. y,) na współrzędne ekranowe yckr), znając rozdzielczość ekranu grnlicznego X„„_K i Y_may oraz inak-symalne odchylenia wartości funkcji f(x), które oznaczymy jako i

Powróćmy teraz do właściwego zadania. Pierwszy pomysł na zrealizowanie algorytmu poszukiwania minimum i maksimum pewnej tablicy2 polega na jej liniowym przeszukaniu:

ntin_max.cpp

const int n=12;

int fah[n) = (23, 12, 1,-5, 34, - 7,45,2,88, -3, - 9, 1); void miu_niaxl (int t[], int min, int* max) i

//użyj tylko gdy n>-l!

min=raax=t[01;

for(int i-1;i<n;i•l)

(

if(max<t[i])    // (*)

max=t li];

if(minst[i]i // (**) min=t[i]; i i

Załóżmy, że tablica ma rozmiar n, tzn. obejmuje elementy od t/Of do tfn-lf. Obliczmy złożoność obliczeniową praktyczną tego algorytmu, przyjmując za element czasochłonny instrukcje porównań. Wynik jest natychmiastowy: T(n)=2(n-1), a zatem program jest klasy O(n). Algorytm jest nieskomplikowany i... nieefektywny. Po bliższym przyjrzeniu się procedurze można bowiem zauważyć, że porównanie (**) jest zbędne w przypadku, gdy (*) jako pierwsze zakończyło się sukcesem. Dołożenie clse tuż po (*) spowoduje, że w najgorszym razie wykonamy 2<n-l) porównań, a w najlepszym - tylko n-1. Nie zmieni to oczywiście klasy algorytmu, ale ewentualnie go przyspieszy - w zależności oczywiście od konfiguracji danych wejściowych.

Zrealizujmy teraz analogiczną procedurę, wykorzystującą rekurencyjne uproszczenie algorytmu zgodnie z zasadą „dziel-i-rządź”. Idea jest następująca;

Przypadek ogólny:

•    jeśli tablica ma rozmiar równy /, to zarówno min, jak i max są równe jedynemu elementowi, który się w niej znajduje;

•    jeśli tablica ma dwa elementy, poprzez ich porównanie możemy z łatwością określić wartości min i max.

’ W przykładzie będzie to tablica liczb całkowitych, co nie umniejsza ogólności algorytmu.