Próbuję nauczyć się wyszukiwania w metodzie rekurencyjnej. Największą przeszkodą dla mnie jest zawsze warunek bazowy do wyjścia z pętli. Czy ktoś może mi to pomógł? Rozumiem koncepcję rekurencji i stosu i wszystkich.

Powiedz, że mam funkcję próbując znaleźć najbliższy wiek w danym wieku w tablicy. Chcę znaleźć indeks w tej tablicy (która ma najbliższy wiek w danym wieku). Więc na przykład w:

arr=[23,78,51,29, 36,90, 12, 30, 79]
age=50

Najbliższy wiek to: 51 z indeksem 2

Gdyby to był sam wiek, byłoby łatwe, po prostu posortuj tablicę, a następnie iteruj przez nową sortowaną tablicę i znajdź najbliższy. Ale potrzebuję indeksu w oryginalnej tablicy

Lubię korzystać z metody rekurencyjnej, więc rozumiem.

def searchRecAge(arr, low, high):
    if ???:
        return
    mid=(high+low)//2
    searchRecAge(arr, low, mid-1)
    searchRecAge(arr, mid+1, high)
    
def searchNearestAgeToGivenAge(arr, age):
    arr=[23,78,51,29, 36,90, 12, 30, 79]
    age=50
    age = searchRecAge(0, len(arr)-1)
    return age

Więc to właśnie mam do tej pory i nie wiem, jak go wypełnić. Myślę, że będę stwierdzić połowę każdej tablicy i sprawdzić, że wiek jest najbliższy w połowie. ??

0
Zoya 15 kwiecień 2021, 20:31

2 odpowiedzi

Najlepsza odpowiedź

Najpierw musisz upewnić się, że tablica jest sortowana , musisz umieścić wartość, którą chcesz znaleźć w tablicy jako parametr funkcji rekurencyjnej . Następnie istnieje kilka warunków, które sprawia, że algorytm zatrzymuje się zgodnie z opisem poniżej:

def searchRecAge(array, value, start, end):
    if start > end: # This means the value does not exist in the array
        return -1

    mid = (start + end) // 2
    if value == array[mid]: # This handles when the value is at the middle of the array
        return mid

    # This handles when value is lower than the value at the middle of the array
    if value < array[mid]: 
        return searchRecAge(array, value, start, mid-1)

    # This handles when value is higher than the value at the middle of the array
    else:
        return searchRecAge(array, value, mid+1, end)
2
Dhana D. 15 kwiecień 2021, 17:51

Oto jedno rozwiązanie do rozwiązywania tego problemu za pomocą rekurencji (ogona):

def nearest_age(arr, age, closest):
    if not arr:
        # Base case: return the `closest` when `arr` is empty
        return closest
    elif abs(age - arr[0]) < abs(age - closest):
        # Replace `closest` with `arr[0]` if difference is small
        return nearest_age(arr[1:], age, arr[0])
    else:
        # Otherwise recur over the rest of the array
        return nearest_age(arr[1:], age, closest)


arr = [23, 78, 51, 29, 36, 90, 12, 30, 79]
age = 50
print(nearest_age(arr, age, 10000))

Python nie jest najlepszym językiem, jeśli chodzi o obsługę rekurencji, więc pokażę, jak to działa z realizacją rakiety / LISP:

#lang racket

(define (nearest_age arr age closest)
  (cond
    ((null? arr) closest)
    ((< (abs (- age (car arr))) (abs (- age closest)))
      (nearest_age (cdr arr) age (car arr)))
    (else (nearest_age (cdr arr) age closest))))

(nearest_age '(23 78 51 29 36 90 12 30 79) 50 10000)

W każdej iteracji to:

  1. Sprawdza, czy lista jest pusta. Jeśli tak: zwróć wartość closest.
  2. Jeśli absolutna różnica między aktualnym najbliższym jest większa niż bezwzględna różnica między pierwszym elementem listy: Powtarzaj nad resztą listy, ale zastąp closest z bieżącym pierwszym elementem.
  3. W przeciwnym razie: Udaj się na resztę listy, utrzymując bieżące wartości age i closest.

Oto ślad obliczeń:

>(nearest_age '(23 78 51 29 36 90 12 30 79) 50 10000)
>(nearest_age '(78 51 29 36 90 12 30 79) 50 23)
>(nearest_age '(51 29 36 90 12 30 79) 50 23)
>(nearest_age '(29 36 90 12 30 79) 50 51)
>(nearest_age '(36 90 12 30 79) 50 51)
>(nearest_age '(90 12 30 79) 50 51)
>(nearest_age '(12 30 79) 50 51)
>(nearest_age '(30 79) 50 51)
>(nearest_age '(79) 50 51)
>(nearest_age '() 50 51)
<51
51

Wersja wyszukiwania binarnego

Jeśli chcesz, aby wersja, która implementuje wyszukiwanie binarne, zapoznaj się z inną odpowiedzią i komentarze (napisałem też podobny algorytm z rozwiązaniem Pythona, jeśli chcesz go przeczytać: https://gist.github.com/hayesall/bde9ff0f90C9AF175DB9D41D53881D4).

Jeśli chcesz zastosować go do swojej tablicy, powinieneś być w stanie posortować go najpierw za pomocą sorted(arr).

1
Alexander L. Hayes 15 kwiecień 2021, 17:58