Kwantyfikatory
Najlepiej tu zacząć od odrobiny matematyki. Mamy predykat
f(x), zwracający prawdę, jeśli
x spełnia warunek, który nas interesuje. Implementacja w C++ jest prosta, to będzie zwykła funkcja, np
bool f(int x). Problem dla wielu początkujących zaczyna się w momencie, gdy chcemy obliczyć predykat
f(x) w jakimś
kwantyfikatorze. Tworzą one predykat, który jest spełniony, jeśli
wszystkie elementy spełniają warunek (kwantyfikator ogólny), albo, jeśli
istnieje element spełniający warunek (kwantyfikator szczególny). Implementacja będzie wymagała pętli oczywiście, ale jak dokładnie kod ma wyglądać, to już okazuje się być problematyczne.
Rozważmy funkcję
all_f(), która odpowiada na tak postawione pytanie. Oto jak niektórzy zabierają się za takie zadanie:
#include <iostream>
bool f( int x )
{
return x % 2 == 0;
}
bool all_f( int * tab, int size )
{
for( int i = 0; i < size; ++i )
{
if( f( tab[ i ] ) )
return true;
else
return false;
}
}
int main()
{
int tab[ 5 ] = { 2, 4, 8, 1, 4 };
std::cout << all_f( tab, 5 );
}
Funkcja zwraca, że wszystkie elementy spełniają warunek (są parzyste), podczas gdy tak nie jest. Kod jest w dość oczywisty sposób zły, zwracamy
true lub
false po sprawdzeniu pierwszego elementu - decyzja zapada natychmiastowo i ta pętla równie dobrze mogłaby być warunkiem, bo i tak nigdy się nie powtórzy. Rozważmy poprawne, ale naiwne rozwiązanie:
bool all_f( int * tab, int size )
{
bool all = true;
for( int i = 0; i < size; ++i )
{
if( !f( tab[ i ] ) )
all = false;
}
return all;
}
Tu posługujemy się zmienną pomocniczą i na wstępie zakładamy, że wszystkie elementy spełniają warunek - dalsze sprawdzanie może zmienić tą decyzję. Jeśli znajdziemy element, który nie spełnia warunku, oznaczamy że zwrócona wartość to
false. Można tak zapisać kod, jeśli dane biorą się z wywołań funkcji i zależy nam na tym, by zawsze dochodziło do wszystkich wywołań. Tutaj jest to nieoptymalne. Zauważ, że jeśli znajdziemy element niespełniający warunku, to wynik jest przesądzony - nic co zobaczymy dalej już tego nie zmieni, więc wynik można zwrócić od razu. Kod powinien wyglądać tak:
bool all_f( int * tab, int size )
{
for( int i = 0; i < size; ++i )
{
if( !f( tab[ i ] ) )
return false;
}
return true;
}
Ten kod jest bardzo zbliżony do tego, jaki można zapisać dla kwantyfikatora szczególnego, bo są w dużej mierze zamienne.
| Wszystkie elementy spełniają warunek wtedy i tylko wtedy, gdy nie istnieje element niespełniający warunku. |
Usuwając te dwie negacje, otrzymujemy kod, który sprawdza, czy istnieje element spełniający warunek - ponownie: znalezienie przesądza wynik, wyjście z pętli znaczy, że element nie istnieje.
bool exists_f( int * tab, int size )
{
for( int i = 0; i < size; ++i )
{
if( f( tab[ i ] ) )
return true;
}
return false;
}