Tablice i funkcje (w czasach zarazy, oczywiście)

 

Wprowadzenie

Mając gotowy (i poprawnie działający) program, możemy postarać się wyodrębnić zasadniczą jego część i zaprogramować ją jako funkcję.

Dziś chciałem o dwu sprawach napisać:

  1. Jak przerobić kawałek algorytmu na funkcję.
  2. Jak to jest gdy chcemy aby parametrem funkcji była tablica albo inna funkcja.

Algorytm B

Posłużę się wersją opisaną na stronie: Algorytm B dla bystrzaków

Żeby sobie ułatwić, komentarzami zaznaczyłem poszczególne kroki algorytmu.

Gdzie zaczyna się kod algorytmu?

To co chcemy zamknąć jako osobną funkcję „zaczyna się” tam gdzie zaznaczyłem krok1. A gdzie się kończy? Prosta odpowiedź jest taka, że tam gdzie jest drukowanie wyniku. Ale to nie jest dobra odpowiedź!

Nie interesuje nas funkcja, która na podstawie przedstawionych danych podaje wynik na ekran! My chcemy ten wynik wykorzystać do dalszych obliczeń. Czasami tylko upewnić się, że NWD1 jest równe 1 (liczby są wzajemnie pierwsze), lub wykorzystać zebraną wiedzę do jakichś działań (uprościć ułamek).

Możemy więc powiedzieć, że Algorytm B kończy się tam gdzie jest już wyliczony wynik.

Jakie są dane do algorytmu?2

Danymi są zmienne uv (typu całkowitego).

Czy funkcja powinna sprawdzać ich poprawność? Pytanie ma charakter filozoficzny. Z formalnego punktu widzenia uv powinny być większe od zera.

Z drugiej strony zadanie możemy uogólnić. NWD dla dowolnej liczby różnej od zera i zera jest ta liczba.

Jaki powinien być wynik działania programu gdy obie wartości (uv) równe są zeru?

Najprostsza odpowiedź może być taka: Program napisze błąd i skończy pracę. Ale znowu: nie interesują nas komunikaty pojawiające się na ekranie tylko informacja zwracana przez funkcję temu, kto ją wywołał…

Umówmy się, że w tym przypadku (oba argumenty mają wartość zero) funkcja zwraca zero.

Co jest wynikiem algorytmu

Zmienna wynik (typu int).

Funkcja

Teraz możemy zacząć pisać funkcję:

 

Natomiast program korzystający z tej funkcji może wygladać tak:

 

Metoda Połowienia

Skorzystam z algorytmu przedstawionego tu: Metoda połowienia dla bystrzaków

Funkcja nasza nazywać się będzie polowienie() i będzie zwracała wartość typu double będącą wartością miejsca zerowego. Nie będzie sprawdzała poprawności danych początkowych (to znaczy tego czy na początku \(f(a)*f(b)<0\)).

Danymi wejściowymi funkcji będą wartości AB. stałe deltaepsilon ustalone są na „sztywno”.

Funkcja może wyglądać jakoś tak:

 

Polecenie return tuż przed końcem funkcji zostało tak zaprogramowane, żeby „wykonać jeszcze jeden krok” połowienia. Przedział A–B jest już wystarczająco krótki, zwracamy informację o jego środku.

Wadą tak przedstawionej funkcji jest to, że nie jest ona uniwersalna: szuka miejsca zerowego funkcji sinus. Żeby zrobić funkcję uniwersalną potrzebne jest jeszcze coś.

Funkcja jako parametr funkcji

Do tej pory (Algorytm B) parametrami funkcji były zwykłe zmienne. A wyszukiwaniu binarnym parametrem była tablica jednowymiarowa. Tu parametrem będzie funkcja…

Jest to właściwie bardzo proste. Trzeba sobie tylko przypomnieć jak wygląda prototyp funkcji.

 

Trzecim parametrem funkcji jest dowolna funkcja o jednym argumencie typu double zwracająca wartości typu double. Wszędzie teraz trzeba zamienić sin() na f(). I gotowe.

Wywołanie funkcji będzie mogło wyglądać tak:

 

(szukamy miejsca zerowego funkcji sin() w przedziale \((2., 5.)\)).

Wyszukiwanie binarne

Tu omówię algorytm ze strony: Wyszukiwanie binarne dla bystrzaków.

 

Analiza przebiega podobnie jak w poprzednich przypadkach. Początek algorytmu jest tuż przed linią kodu oznaczoną etykietą poczatek.

Zastanówmy się co będzie parametrami funkcji:

  • na pewno tablica z danymi t (i to jest najważniejsza cześć tego wykładu);
  • jej rozmiar n;
  • szukana wartość x.

Funkcja powinna zwrócić informację, na którym miejscu tablicy znajduje się szukany element lub informację, że elementu nie ma. W pierwszym przypadku będzie to liczba z zakresu od 0 do n-1 (włącznie); w drugim — -1.

„Najtrudniejsza” część to zadeklarowanie tablicy jako parametru funkcji. Wszystko wyjaśni się gdy zaczniemy dyskutować wskaźniki.

Funkcja binarne()

Niech nasza funkcja nazywa się binarne(), a jej parametrami będą zmienna całkowita x, zmienna całkowita n i tablica t (na potrzeby tego przykładu xt będą całkowite).

Do tej pory deklaracje parametrów funkcji niewiele różniły się od deklaracji zmiennych. Może uda się i teraz:

 

Zadeklarowałem tablicę t tak samo jak deklaruje się tablicę o zmiennej długości. Robiąc to trzeba zagwarantować, że długość tablicy n jest zadeklarowana wcześniej (czyli na lewo od t[n]).

Okaże się później (ale to powinno być w pewnym sensie oczywiste), że nie trzeba podawać długości tablicy w deklaracji3 (i tak nie ma ona żadnego znaczeni), czyli:

trzeba jednak zasygnalizować, że t to tablica (o czym świadczy para nawiasów kwadratowych po nazwie, tak jak w deklaracji tablicy gdy nie ma długości, ale jest inicjator).

Zmiennymi używanymi przez funkcję będą

 

Wyrzucamy z funkcji printf() i ostatecznie otrzymujemy:

 

Funkcja główna będzie mogła wyglądać jakoś tak:

 

Zwracam uwagę, że w wywołaniu funkcji binarne podajemy tylko i wyłącznie nazwę tablicy. Tak na prawdę to nić innego nie pasuje. Wpisanie t[\(\alpha\)] (gdzie \(\alpha\) to jakaś stałą, zmienna lub wyrażenie typu int) nie ma sensu bo wartość elementu tablicy o indeksie \(\alpha\). A t[] nie ma najmniejszego sensu4.

I zakończenie programu:

 

Plik w formacie…

PDF jest również dostępny.


  1. Największy Wspólny Dzielnik.
  2. Zdecydować trzeba, które zmienne będą argumentami i jaki jest ich typ.
  3. Natomiast koniecznie jednym z parametrów musi być n czyli rozmiar tablicy. Z różnych względów (o czym będzie mowa później) nie można zmierzyć rozmiaru tego parametru (sizeof()) wewnątrz funkcji.
  4. Może pojawić się jedynie w deklaracji tablicy, dla której nie podajemy długości.