« Jak sprawdzić, czy wszystkie elementy spełniają warunek / czy istnieje element spełniający warunek?, pytanie/odpowiedź »
Implementacja kwantyfikatorów logicznych. "Czy wszystkie elementy spełniają warunek?" "Czy istnieje element spełniający warunek?" (pytanie/odpowiedź)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Autor pekfos
FAQ

Jak sprawdzić, czy wszystkie elementy spełniają warunek / czy istnieje element spełniający warunek?

[pytanie/odpowiedź] Implementacja kwantyfikatorów logicznych. "Czy wszystkie elementy spełniają warunek?" "Czy istnieje element spełniający warunek?"

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:
C/C++
#include <iostream>

bool f( int x )
{
    return x % 2 == 0;
}

bool all_f( int * tab, int size )
{
    for( int i = 0; i < size; ++i )
    {
        //  !!! ŹLE !!!
        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:
C/C++
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:
C/C++
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.
C/C++
bool exists_f( int * tab, int size )
{
    for( int i = 0; i < size; ++i )
    {
        if( f( tab[ i ] ) )
             return true;
       
    }
   
    return false;
}