algoritmos recursivos exemplos busca bonaria

Prévia do material em texto

' $
ALGORITMOS RECURSIVOS
Prof. Ce´sar Francisco de Moura Couto
Matema´tica Discreta
& %
' $
CEFET-MG Algoritmos Recursivos
Algoritmos Recursivos
• Um algoritmo recursivo para computar mdc(a,b).
• Soluc¸a˜o:
procedure mdc(a,b: numeros inteiros n~ao negativos com a < b)
if a = 0 then mdc(a,b) := b
else mdc(a,b) := mdc(b mod a, a)
end
Prof. Ce´sar Francisco de Moura Couto 1& %
' $
CEFET-MG Algoritmos Recursivos
Algoritmos Recursivos
• Um algoritmo recursivo para busca linear.
• Soluc¸a˜o:
procedure busca(i,j,x: numeros inteiros, 1 <= i <= m, 1 <= j <= m)
if a[i] = x then
localizacao := i
else if i = j then
localizacao := 0
else
busca(i + 1, j, x)
end
Prof. Ce´sar Francisco de Moura Couto 2& %
' $
CEFET-MG Algoritmos Recursivos
Algoritmos Recursivos
• Um algoritmo recursivo para busca binaria
• Soluc¸a˜o:
procedure buscabinaria(i,j,x: numeros inteiros, 1 <= i <= m, 1 <= j <= m)
m := [(i + j) / 2]
if a[m] = x then
localizacao := m
else if (x < a[m] e i < m) then
buscabinaria (x, i, m - 1)
else if (x > a[m] e j > m) then
buscabinaria (x, m + 1, j)
else
localizacao := 0
end
Prof. Ce´sar Francisco de Moura Couto 3& %
' $
CEFET-MG Algoritmos Recursivos
Algoritmos Recursivos
• O algoritmo Merge Sort recursivo para ordenac¸a˜o de um vetor.
• Soluc¸a˜o: Entendimento do Merge Sort. Ordenamento dos nu´meros 8 2 4 6 9 7 10 1 5 3
Prof. Ce´sar Francisco de Moura Couto 4& %
' $
CEFET-MG Algoritmos Recursivos
Algoritmos Recursivos
• Segue o algoritmo:
procedure mergesort(L = [a1, ..., an])
if n > 1 then
m := n/2
L1 := [a1, ..., am]
L2 := [am+1, ..., an]
L := merge(mergesort(L1), mergesort(L2))
end
Prof. Ce´sar Francisco de Moura Couto 5& %