Znajdź drugą najmniejszą liczbę na liście używając rekursji

Question

Wiem, że zadałem pytanie na ten temat, ale żadna z odpowiedzi mi nie pomogła. Nie potrzebuję pomocy przy implementowaniu kodu, potrzebuję tylko pomocy w sortowaniu tego procesu rekurencyjnego.

Początkowo myślałem, zwracając rekurencyjnie krotkę na każdym poziomie i porównując ją, znajdź drugą najmniejszą wartość. Ale to nie działa, ponieważ chcę, aby moja funkcja zwracała tylko 1 wartość na końcu - druga najmniejsza wartość.

Co powinienem zrobić z procesem rekursywnym dla tego problemu? Dziękuję Ci!

Edytuj: Przepraszam, że nie zawierają wystarczającej liczby informacji, więc tutaj jest.

funkcja powinna działać w następujący sposób:

>>> sm([1,3,2,1,3,2]) 
>>> 2 

Druga edycja: Przepraszamy za opóźnienie, byłem zajęty aż do teraz, w końcu był w stanie usiąść i umieścić co miałem na myśli w kodzie. Działa zgodnie z przeznaczeniem, ale szczerze uważam, że jest to bardzo gówniany i nieefektywny sposób wykonywania rekursji, ponieważ prawdopodobnie możesz powiedzieć, że jestem nowy w tej koncepcji.

Aby ponownie sformułować moje oryginalne pytanie za pomocą poniższego pseudo kodu: Czy można zrobić to, co tutaj zrobiłem, ale bez owijania go w drugą funkcję? Czy możliwe jest posiadanie funkcji, która rekurencyjnie nazywa siebie samą i zwraca 1 numer - drugą najmniejszą liczbę?

def second_smallest(list): 
    def sm(list): 
     if base case(len of list == 2): 
      return ordered list [2nd smallest, smallest] 
     else: 
      *recursive call here* 
      compare list[0] with returned ordered list 
      eg: [3, [5,2]] 
      re-arrange, and return a new ordered list 
      [3,2] 
    return sm(list)[0] 

Answer 1

Możesz napisać swoją funkcję rekursywną, aby pobrać 3 argumenty: pierwszą i drugą najmniejszą wartość, jaką dotychczas spotkałeś, oraz resztę listy, której nie sprawdziłeś.

Następnie, porównując pierwszy element argumentu listy z dwoma najmniejszymi-do tej pory, można wybrać, które 2 z 3 należy przekazać jako argumenty do następnej rekursji.

Tę funkcję rekursywną należy zawijać w funkcji prezentacji, która konfiguruje i wywołuje rekursywną, podczas obsługi takich przypadków, jak listy zawierające mniej niż 2 elementy.

def recurse(min1, min2, list): 
    if len(list)==0: 
     return min2 
    first, rest = list[0], list[1:] 
    if first < min1: 
     return recurse(first, min1, rest) 
    if first < min2: 
     return recurse(min1, first, rest) 
    return recurse(min1, min2, rest) 

def second_smallest(list): 
    if len(list) < 2: 
     raise ValueError("too few elements to find second_smallest") 
    a, b, rest = list[0], list[1], list[2:] 
    if b < a: 
     return recurse(b, a, rest) 
    else: 
     return recurse(a, b, rest) 

Tego rodzaju rozwiązanie nie jest szczególnie Pythoniczne - jest to bardziej funkcjonalny styl programowania.

Wreszcie, można przekazać argumentów na początku listy, i połączyć dwie funkcje, aby uzyskać rodzaju rozwiązanie szukasz:

def second_smallest(list): 
    if len(list) < 2: 
     raise ValueError("too few elements to find second_smallest") 
    a, b = list[0], list[1] 
    a, b = min(a,b), max(a,b) 
    if len(list) == 2: 
     return b 
    c, rest = list[2], list[3:] 
    if c < a: 
     return second_smallest([c,a]+rest) 
    if c < b: 
     return second_smallest([a,c]+rest) 
    return second_smallest([a,b]+rest) 

Funkcja ta ma pewne nadmiarowe pracy , ponieważ nie może wiedzieć, czy jest wywoływany jako pierwszy, czy też nazywa się rekursywnie.Ponadto, + tworzy nową listę, więc ten kod najprawdopodobniej zajmie O (n^2) dla listy o rozmiarze n.

Answer 2

Potrafię wymyślić kilka sposobów. Powolny polega na znalezieniu największej wartości z podanej listy, a następnie powtórzenie na pozostałej liście. Gdy długość listy wynosi 2, nie wykonuj wywołania cyklicznego.

Szybszym sposobem jest znalezienie najmniejszego elementu, powtarzaj w pozostałej części listy, powtarzając tylko dwa razy. Napisz rutynę, aby znaleźć najmniejszy element w ten sposób, a następnie zawiń go w procedurę, która wywołuje go za pomocą n = 2.

Czy to wystarczy?

Answer 3

Jednym z możliwych sposobów jest stworzenie funkcji przyjmować 3 parametry: list oraz opcjonalny smallest_value i second_smallest. W funkcji pop pierwszy element należy porównać z najmniejszym i drugim najmniejszym, a w razie potrzeby zmienić wartości. Następnie wywołaj funkcję ponownie z nowymi list, smallest i second_smallest. Rekursja powinna kończyć się, gdy lista jest pusta i zwracać drugą najmniejszą.

Istnieje kilka trudnych stanów (gdy jedna/obie wartości nie są jeszcze ustawione). Ale myślę, że to szczegóły implementacji i możesz ponownie zapytać, czy masz jakieś problemy z jej kodowaniem.

Answer 4

Możesz użyć klasycznego podziału i podbić. Niech f(x) będzie funkcją zwracającą krotkę (a,b) zawierającą najmniejsze i następne najmniejsze elementy na liście x.

Podstawowymi skrzynkami są, gdy x ma 0 lub 1 element. Poza przypadkiem bazowym, podzielić listę na 2, powtarzać się znaleźć najmniej dwa elementy każdej połowie, a następnie wybrać co najmniej 2 z tych 4 w wyniku:

def min2(x): 
    if len(x) == 0: return sys.maxsize, sys.maxsize 
    if len(x) == 1: return x[0], sys.maxsize 
    m = int(len(x)/2) 
    a1, b1 = min2(x[:m]) 
    a2, b2 = min2(x[m:]) 
    return (a1, min(b1, a2, b2)) if a1 < a2 else (a2, min(b2, a1, b1)) 

def secondSmallest(x) 
    return min2(x)[1] 

Tutaj używam sys.maxsize jako „nieskończoności . "

Answer 5

Możesz użyć flagi, aby śledzić, czy jesteś na najbardziej zewnętrznym poziomie połączeń.

def second_smallest(numbers, top_level=True): 
    # Do your stuff and call `second_smallest(numbers[1:], False)` for any recursions. 
    # When it comes to returning a value from the function, use the following. 

    if top_level: 
     return result[0] # what your function ultimately returns 
    return result   # [second, first] since you're still in recursive calls 

Answer 6

Co rozumiem z pytaniem: - 1. Rozwiązanie powinno być rekurencyjne 2. Brak funkcji wewnętrzny rodzaj włamać 3. Należy zwrócić druga najmniejsza i listy przyjąć jako parametr mój kod, aby rozwiązać ten -

from inspect import getouterframes, currentframe 
def second_smallest(ls): 
    level = len(getouterframes(currentframe(1))) 

    if len(ls)<2: 
     return None 
    if len(ls) == 2: 
       if level == 1: 
        return max(ls) 
       else: 
        return min(ls), max(ls) 
    else: 
     m,n = second_smallest(ls[1:]) 
     if ls[0]<=m: 
      n = m 
      m = ls[0] 
     elif ls[0] < n: 
      n = ls[0] 
     if level == 1: 
      return n 
     return m,n 

Uwaga - Ten kod działa, jeśli uruchamiane jako plik programu python

Answer 7

można zrobić coś wzdłuż tych linii:

def rmin(li, n=2): 
    def _rmin(li): 
     if len(li) == 1: 
      return li[0] 
     else: 
      m = _rmin(li[1:]) 
      return m if m < li[0] else li[0] 

    a=[]   
    for i in range(n): 
     x=_rmin([e for e in set(li) if e not in a]) 
     a.append(x) 
    return x