Funkcja rekurencyjna - najmniejsza wartość wejściowa dla uzyskania określonego wyniku

Question

Próbuję rozwiązać ostatni arkusz z informatyki w ramach przygotowania do tegorocznej matury i zaciąłem się na poniższym zadaniu.

Mam taką funkcję rekurencyjną:

licz(x)
	jeżeli x = 1
		podaj wynik 1
	w przeciwnym przypadku
		w <- licz(x div 2)
		jeżeli x mod 2 = 1
			podaj wynik w+1
		w przeciwnym przypadku
			podaj wynik w-1

div - dzielenie całkowite, mod - reszta z dzielenia

 

Do tego kodu muszę wykonać takie zadanie:

Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania licz(x) będzie 0.

 

Doszedłem do tego, że żeby otrzymać ostateczny wynik zero, jedna z rekurencji musi mi zwrócić wynik w=-1 lub w=1.

w=-1
x%2=1
x=0

w=1
x%2=0
x=0

Wówczas to zero spowoduje, że każde kolejne wykonanie wywoła zero, co da mi ostatecznie licz(x)=0, lecz nie jestem w stanie wydedukować, jaka najniższa wartość wejściowa pozwoli mi to osiągnąć.

Proszę o pomoc w znalezieniu sposobu na rozwiązanie tego zadania.

 

JEST TO CZĘŚĆ TEORETYCZNA, NA KARTCE.

Answer 1

Według mnie: ŻADNA. Czemu? Bo jeżeli wyjdzie Ci nieparzysta tu:  jeżeli x mod 2 = 1 to -> to zwróci Ci wynik+1 co uniemożliwia zero. A jeżeli  podaj wynik w-1 -> to zauważ ze tu dla parzystego 0 zwróci ci -1,  a dla parzystej 2 zwróci Ci 1;

Program poniżej to potwierdza:

 

class Main {

    public static void main(String[] args) {
        for (int i = 100; i < 10000; i++) {
            int wynik = licz(i);
            if (wynik == 0) {
                System.out.println(i);
                break;
            }
        }
    }

    public static int licz(int x) {
        if (x == 1) {
            return 1;
        } else {
            int w = licz(x / 2);
            if (w % 2 == 1) {
                return w + 1;
            } else {
                return w - 1;
            }
        }
    }
}

 

Comments

W kluczu odpowiedzi jako poprawna (czyli najniższa; za 2 punkty) podana jest wartość wejściowa 135 lub inna wartość wyższa od 100, dla której wynikiem działania algorytmu będzie zero (za 1 punkt).

W jaki sposób do tego dojść "na piechotę"? W części praktycznej napisałbym mały program w C++, ale tutaj nie mam możliwości.

---

Czyli mój program jest źle napisany?:( gdzie zrobiłem błąd interpretując zadanie?

---

Napisałem program w C++ i dla 100<x<200 zwraca mi kilkadziesiąt wartości spełniających warunek. Nawet zgadza się wynik 135 jako ten najmniejszy. Wygląda na to, że Pana program ma jakiś błąd :P

int licz(int x) {
    if(x==1) {
        return 1;
    }
    else {
        int w=licz(x/2);
        if(x%2==1) {
            return w+1;
        }
        else {
            return w-1;
        }
    }
}

int main()
{
    for(int i=100; i<200; i++) {
        if(licz(i)==0) {
            cout << "Rozwiazaniem jest liczba: " << i << endl;
        }
    }
    return 0;
}

Rozwiazaniem jest liczba: 135
Rozwiazaniem jest liczba: 139
Rozwiazaniem jest liczba: 141
Rozwiazaniem jest liczba: 142
Rozwiazaniem jest liczba: 147
Rozwiazaniem jest liczba: 149
Rozwiazaniem jest liczba: 150
Rozwiazaniem jest liczba: 153
Rozwiazaniem jest liczba: 154
Rozwiazaniem jest liczba: 156
Rozwiazaniem jest liczba: 163
Rozwiazaniem jest liczba: 165
Rozwiazaniem jest liczba: 166
Rozwiazaniem jest liczba: 169
Rozwiazaniem jest liczba: 170
Rozwiazaniem jest liczba: 172
Rozwiazaniem jest liczba: 177
Rozwiazaniem jest liczba: 178
Rozwiazaniem jest liczba: 180
Rozwiazaniem jest liczba: 184
Rozwiazaniem jest liczba: 195
Rozwiazaniem jest liczba: 197
Rozwiazaniem jest liczba: 198

Ale jak to policzyć "na piechotę"?

---

Widzę swój błąd. Pomyliłem "w" z "x". Dzieki