Wyszukiwanie liniowe rekurencyjnie

Zadanie 7 z 13 · rozdział 15Trudność: 2 z 3rekurencjalistywyszukiwanie

Treść zadania

Napisz rekurencyjną funkcję wyszukaj(lista, klucz, indeks=0), która zwraca indeks pierwszego wystąpienia liczby klucz w liście, sprawdzając kolejne elementy od pozycji indeks. Jeśli klucz nie występuje w liście, funkcja zwraca -1.

Program wczytuje listę i klucz, wywołuje funkcję i wypisuje wynik.

Dane wejściowe

  • 1. linia: n — liczba elementów listy
  • 2. linia: n liczb całkowitych oddzielonych spacjami
  • 3. linia: klucz — liczba całkowita

Dane wyjściowe

Jedna liczba całkowita — indeks pierwszego wystąpienia klucza (indeksy liczymy od 0) albo -1, jeśli klucza nie ma w liście.

Ograniczenia

  • 1 ≤ n ≤ 100
  • elementy listy i klucz są z zakresu -1000 … 1000

Uwagi

  • Przypadki bazowe: indeks wyszedł poza listę (klucza nie ma) albo lista[indeks] jest równe kluczowi. W przeciwnym razie szukaj dalej od pozycji indeks + 1.

Przykład

Wejście
3
1 2 2
2
Wyjście
1

Liczba 2 występuje na pozycjach 1 i 2 — wypisujemy pierwszą z nich.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 15

Poniższe zadania uczą rekurencji: funkcja rozwiązuje problem, wywołując samą siebie dla mniejszych danych, aż dojdzie do przypadku bazowego, w którym odpowiedź jest znana od razu (np. $0! = 1$).

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście. Program wczytuje dane, wywołuje funkcję opisaną w treści i wypisuje wynik (gotowy szkielet znajdziesz w sekcji „Kod startowy”).
  • Rozwiązanie musi być rekurencyjne. Właściwe obliczenia wykonuje funkcja, która wywołuje samą siebie. Nie używaj w niej pętli for ani while, ani gotowych narzędzi, które wykonają całą pracę za Ciebie (np. sum(), pow(), operatora **, math.factorial(), list.index()). Sprawdzarka porównuje tylko wynik, ale celem zadań jest ćwiczenie rekurencji.
  • Każda funkcja rekurencyjna potrzebuje przypadku bazowego (kiedy przestajemy się wywoływać) i kroku rekurencyjnego (wywołania dla mniejszego problemu). Bez przypadku bazowego program przerwie działanie błędem RecursionError.
  • Python ogranicza głębokość rekurencji (domyślnie do około 1000 zagnieżdżonych wywołań), dlatego dane w zadaniach są małe.
  • Liczby naturalne liczymy od zera: $0, 1, 2, \dots$
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
5
4 8 15 16 23
4
Oczekiwane wyjście
0

Test 2

Nie uruchomiono
Wejście
5
4 8 15 16 23
23
Oczekiwane wyjście
4

Test 3

Nie uruchomiono
Wejście
6
3 1 4 1 5 1
1
Oczekiwane wyjście
1

Test 4

Nie uruchomiono
Wejście
3
10 20 30
25
Oczekiwane wyjście
-1

Test 5

Nie uruchomiono
Wejście
1
42
7
Oczekiwane wyjście
-1

Test 6

Nie uruchomiono
Wejście
4
7 0 -5 -5
-5
Oczekiwane wyjście
2
Uruchom z własnymi danymi