(a) Considere a seguinte definição recursiva em Python e descreva sucintamente qual a função calculada por aaa.
def aaa(x,w):
if w==[]:
return False
elif x==w[0]:
return True
else:
return aaa(x,w[1:])
aaa(x,w) é True se o elemento x pertence a lista w, e False caso contrário.
(b) Usando aaa, defina recursivamente em Python uma função dist que dada uma lista de inteiros w devolva o número de valores distintos que ocorrem em w.
Por exemplo, dist([1,2,3,2,3,0,3]) deve ser 4 (na lista ocorrem os valores 0, 1, 2 e 3).
Neste exercício não pode usar definições por compreensão nem métodos. As únicas construções sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), comparação com a lista vazia (==[]) e concatenação (+).
def dist(w):
if w==[]:
return 0
elif aaa(w[0],w[1:]):
return dist(w[1:])
else:
return 1+dist(w[1:])
(a) Considere a seguinte definição recursiva em Python e descreva sucintamente qual a função calculada por bbb.
def bbb(x,w):
if w!=[]:
return (1 if x==w[0] else 0)+bbb(x,w[1:])
else:
return 0
bbb(x,w) é o número de ocorrências do elemento x na lista w.
(b) Usando bbb, defina recursivamente em Python uma função quantos que dada uma lista de inteiros w e um valor r devolva como resultado o número de formas de se obter r como a soma de dois elementos de w.
Por exemplo, quantos([1,2,1,3,4],5) deve ser 3 (pois 1+4, 2+3 e 1+4 são todas 5).
Neste exercício não pode usar definições por compreensão nem métodos. As únicas construções sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), comparação com a lista vazia (==[]) e concatenação (+).
def quantos(w,r):
if w==[]:
return 0
else:
return bbb(r-w[0],w[1:])+quantos(w[1:],r)
(a) Considere a seguinte definição recursiva em Python e descreva sucintamente qual a função calculada por ccc.
def ccc(x,w):
if w==[]:
return False
else:
return x==w[0] or ccc(x,w[1:])
ccc(x,w) é True se o elemento x pertence a lista w, e False caso contrário.
(b) Usando ccc, defina recursivamente em Python uma função parsomaQ que dada uma lista de inteiros w e um valor r devolva como resultado True se se pode obter r como a soma de dois elementos de w, e False caso contrário.
Por exemplo, parsomaQ([1,2,3],4) deve ser True (pois 1+3 é 4), mas parsomaQ([1,2,3],6) deve ser False (pois a maior soma possível é 2+3, ou seja, 5).
Neste exercício não pode usar definições por compreensão nem métodos. As únicas construções sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), comparação com a lista vazia (==[]) e concatenação (+).
def parsomaQ(w,r):
if w==[]:
return False
elif ccc(r-w[0],w[1:]):
return True
else:
return parsomaQ(w[1:],r)
(a) Considere a seguinte definição recursiva em Python e descreva sucintamente qual a função calculada por ddd.
def ddd(x,w):
if w==[]:
return 0
elif x==w[0]:
return 1+ddd(x,w[1:])
else:
return ddd(x,w[1:])
ddd(x,w) é o número de ocorrências do elemento x na lista w.
(b) Usando ddd, defina recursivamente em Python uma função reps que dada uma lista de inteiros w devolva o número de valores repetidos que ocorrem em w.
Por exemplo, reps([1,2,3,1,1,3]) deve ser 2 (os valores 1 e 3 ocorrem repetidos).
Neste exercício não pode usar definições por compreensão nem métodos. As únicas construções sobre listas permitidas são: lista vazia ([]), acesso aos elementos da lista por posição (lista[posição]), seccionamento da lista (lista[posição:posição]), comparação com a lista vazia (==[]) e concatenação (+).
def reps(w):
if w==[]:
return 0
elif ddd(w[0],w[1:])==1:
return 1+reps(w[1:])
else:
return reps(w[1:])