JFiZO - Lista 6

Mało zadeptany śnieg - drak (zad 47)

func:

1. niemalejąca: func(n) \le func(m), n < m
2. całkowita: \forall n \in A: func(n) = m
3. rekurencyjna: func(n) = 1 \Leftrightarrow n \in A, func(n) = 0 \Leftrightarrow n \not\in A

Przypadek 1: func - od pewnego momentu stała

max = max(dom(func(N)))

int g(n)
{
    for(i = 0; func(i) <= max; i++) {
        if (func(i) == n) return 1;
        if (func(i) == max) return 0;
    }
}

Przypadek 2: func - ma nieskonczenie wiele wartosci

int g(n)
{
    for(i = 0; func(i) <= n; i++) {
        if (func(i) == n) return 1;
    }
    return 0;
}