• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
600 wizyt
pytanie zadane 30 marca 2018 w Algorytmy przez norbi1952 Początkujący (310 p.)

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.

1 odpowiedź

0 głosów
odpowiedź 30 marca 2018 przez Tomasz Rogalski Bywalec (2,800 p.)

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;
            }
        }
    }
}

 

komentarz 30 marca 2018 przez norbi1952 Początkujący (310 p.)
edycja 30 marca 2018 przez norbi1952

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.

komentarz 30 marca 2018 przez Tomasz Rogalski Bywalec (2,800 p.)
Czyli mój program jest źle napisany?:( gdzie zrobiłem błąd interpretując zadanie?
komentarz 30 marca 2018 przez norbi1952 Początkujący (310 p.)
edycja 30 marca 2018 przez norbi1952

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ę"?

komentarz 30 marca 2018 przez Tomasz Rogalski Bywalec (2,800 p.)

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

Podobne pytania

0 głosów
1 odpowiedź 1,678 wizyt
0 głosów
1 odpowiedź 458 wizyt
pytanie zadane 23 grudnia 2017 w Algorytmy przez Sensej Użytkownik (540 p.)
0 głosów
0 odpowiedzi 281 wizyt
pytanie zadane 15 października 2019 w C i C++ przez four Użytkownik (720 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...