zadanie z rekurencją. Wyszukiwanie największego elementu na liście.

0

Utwórz funkcję, która będzie przyjmowała jako argument listę i zwracała wartość
największego jej elementu. Aby odnaleźć element o największej wartości,
skorzystaj z rekurencji.

Bardzo proszę o podanie kodu do tego zadania. Nie radzę sobie z rekurencją i chcę to jakoś ugryźć.

4

Niech funkcja max(list) ma definicje:

  • Jeśli lista ma 1 element to zwróć ten element
  • Jeśli lista ma przynajmniej 2 elementy to podziel listę na pierwszy element (head) i resztę elementów (tail) i zwróć większą wartość z head, max(tail)

Innymi słowy maksimum to albo pierwszy element listy, albo maksimum z pozostałych elementów. Jeśli lista ma tylko 1 element, to jest on automatycznie maksymalny, z oczywistych względów.

Mógłbyś równie dobrze zrobić to połówkując, tzn: możesz podzielić tablicę na 2 połówki, policzyć max z każdej z połówek i wybrać większy z tych maxów. Jeśli tablica ma tylko 1 element, to automatycznie jest maksymalny. Ale opcja z head i tail jest łatwiejsza bo w pythonie możesz zrobić tablica[0] i tablica[1:]

1

@Shalom: Fatalne nazewnictwo. Trafiłeś w słowa kluczowe Pythona :D

>>> lista = [456, 123, 543, 33, 77778, 124, 543]
>>> max(lista)
77778

@takitamnoobek: Chyba tak by mogło być...

lista = [456, 123, 543, 33, 77778, 124, 543]

def max_rek(lista, lista_length, current_max, cmp_idx):
    if cmp_idx >= lista_length:
        return current_max
    elif lista[cmp_idx] > current_max:
        return max_rek(lista, lista_length, lista[cmp_idx], cmp_idx + 1)
    else:
        return max_rek(lista, lista_length, current_max, cmp_idx + 1)

def max_start(lista):
    return max_rek(lista, len(lista), lista[0], 1)

print (max_start(lista))

Chociaż w Pythonie bez sensu jest takie zadanie, bo tak jak napisałem powyżej, jest na to bardzo wygodna funkcja wbudowana.

2

@Spine o_O toś przekombinował, po co ci tam jakieś indeksy? o_O

def head(lista):
    return lista[0]

def tail(lista):
    return lista[1:]

def max_of_2(a, b):
    return a if a > b else b

def max(lista):
    if len(lista) == 1:
        return head(lista)
    else:
        return max_of_2(head(lista), max(tail(lista)))
0
Shalom napisał(a):

@Spine o_O toś przekombinował, po co ci tam jakieś indeksy? o_O

Wiesz jak działa lista[1:]?
Kopiuje elementy, tworząc nową listę!

0

A czy takie rozwiązanie ma sens (przy dużych tablicach?)

lTab=[14,-133,7,9,12,4,78,1220,30,2,818,112]
iTab=iter(lTab)

def f_SearchMax(elm,nMax=None):
    if nMax!=None:
        if nMax<elm: nMax=elm
    else: nMax=elm
    try: return f_SearchMax(next(iTab),nMax) # tu jedynie nie wiem co poradzić na ostatni element iter
    except: return nMax

nMaxVal=f_SearchMax(next(iTab))
print(nMaxVal)

Pozdrawiam
Radosław Głębicki

0
def max_element(xs, xmax=None):
    if not xs:
        return xmax
    if not xmax or xs[0] > xmax:
        xmax = xs[0]
    return max_element(xs[1:], xmax)

PS.
Jak komuś przeszkadza wycinek tablicy, to może operować na indeksie i licznie elementów. Wtedy powstaje:

def max_element(xs, i=0, xmax=None):
    if i >= len(xs):
        return xmax
    if not xmax or xs[i] > xmax:
        xmax = xs[i]
    return max_element(xs, i+1, xmax)

Generalnie szkoda czasu na dywagowanie na takim zadaniem.

0

W zadaniach rekurencyjnych, piszesz kod, zgodnie z zadaniem; a jak w grę wchodzą listy, to poniższy pattern występuje prawie zawsze:

def my_max(xs):
    if len(xs) == 1:
        return xs[0]
    return max(xs[0], my_max(xs[1:]))

Nie podaleś co robić w przypadku pustej listy, dlatego też to rozwiązanie, jak i @Shalom się na niej wykrzaczą.
Acha @takitamnoobek nie przeskoczysz, w Pythonie nie ma optymalizacji rekurencji, więc do duzych struktur się ona nie nadaje.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0