ALG9

6.5, Metoda funkcji przeciwnych 179

b=l;

olso

(

PI(a-l,b);

// tu funkcja odwrotna? b=b+a;

)

Sens matematyczny tej procedury jest dla nas nieistotny. Jedyne, co nas w tym momencie interesuje, to takie jej przekształcenie, aby uzyskać procedurę void P2. która korzystając tylko ze zmiennych globalnych a i b będzie działała w sposób identyczny.

Pierwszym etapem naszej analizy jest odpowiedź na pytanie: „Które zmienne są modyfikowane przez rekurencyjne wywołanie PI?". Zmienna b ma charakter globalny, gdyż nie jest przez PI modyfikowana. Służy ona wyłącznie do przekazywania wyniku z wywoływanej procedury. l ak więc funkcja odwrotna - jaka by nie była jej postać — nie będzie się musiała zajmować zachowaniem wartości b. Jedyną zmienną, która jest modyfikowana, jest ci. Dekrementowana wartość zmiennej a jest przekazywana procedurze PI, natomiast po ukończeniu pracy tejże chcemy korzystać z niezmienionej wartości a.

W poznanej poprzednio metodzie eliminacji zmiennych lokalnych należałoby po prostu zachować oryginalną wartość a na stosie W naszym przypadku wystarczy (wiedząc, że jedyną modyfikacją, jakiej może na zmiennej u dokonać procedura PI. jest dekrementacja) po prostu przywrócić oryginalną wartość a inkrementując ją! I to jest tą naszą tajemniczą „funkcją odwrotną”... Popatrzmy na zmodyfikowaną treść procedury:

int a,b; // zmienne globalne void P2()

{

if(a==0) b=l; else

(

a=a-l; t>2 () ; a=a+l; b=b+a;

Sprawdźmy teraz w programie głównym, czy istotnie nasz program działa prawidłowo¹:

1

Nie zastąpi to oczywiście formalnego dowodu równoważności /'/ i P2. ale zadanie jest na tyle proste, iż dowód ten wydaje się w tym miejscu zbędny.