Fórum: Programação Multiparadigma

Definições de Fibonacci e outras

 
Imagen de Pedro Santos
Definições de Fibonacci e outras
de Pedro Santos - sexta, 28 de setembro de 2012, 21:41
 

Boa noite professor e caros colegas,

Alguém completou as duas definições de Fibonacci (circular e directa)?

Eu tenho duas possíveis soluções mas uma delas não me parece nem 100% directa, nem circular.

1ª solução:

def zfib_aux(l: ZList[Int]): ZList[Int] = ZNode(zhd(l)+zhd(ztl(l)), u => zfib_aux(ztl(l)))
def zfib_dir:ZList[Int] = ZNode(1, u => ZNode(1, u => zfib_aux(zfib_dir)))

2ª solução (com uma função que adiciona os elementos de uma lista a outra)

def zfib : ZList[Int] = ZNode(1, u => ZNode(1, u => zaddl(zfib, ztl(zfib))))
println(zshow(zfib))

def zaddl(l:ZList[Int], r:ZList[Int]):ZList[Int] = {
  (l,r) match {
    case (ZNil,ZNil) => ZNil
    case (ZNil, ZNode(y,ys)) => ZNode(y, ys)
    case (ZNode(x,xs), ZNil) => ZNode(x, xs)
    case (ZNode(x,xs), ZNode(y,ys)) => ZNode(x+y, u => zaddl(xs(),ys()))
  }
}


A segunda é claramente circular. Mas a primeira usa uma função auxiliar que é recursiva e quando a utiliza é circular, pois usa zfib_dir na própria definição de zfib_dir. Por isso não sei bem em que categoria se insere. Além disso, caso a 1ª não seja directa não estou a ver como fazer uma definição directa para fibonnacci.

Para além da de fibonacci também para a lista infinita de zero, a circular é muito mais imediata e a directa é simplesmente um "wrapper" para a circular para que não se use a própria definição, mas a definição auxiliarem si é circular.

Lista de zeros (circular):
val zzeroes : ZList[Int] = ZNode(0, u=>zzeroes)


Lista de zeros (directa):
def zzeroes_dirX():ZList[Int] = ZNode(0, u=>zzeroes_dirX())
def zzeroes_dir = zzeroes_dirX()

Eu percebo o conceito de definição directa e circular. Mas por vezes fica-se com definições que parecem ser "mistas", ou pelo menos não são puramente um dos dois tipos. Gostava de esclarecer bem como decidir se é um caso ou outro.

Desde já obrigado por qualquer resposta.




Imagen de Carlos Loureiro
Re: Definições de Fibonacci e outras
de Carlos Loureiro - sexta, 28 de setembro de 2012, 23:11
 

A tua 1ª solução é circular pois utilizas uma função gera ela própria os elementos da lista (zfib_aux). Na 2ª solução está presente este conceito ;)

Para ser directa tinhas de ter uma função geradora, onde tens de indicar quais os elementos de entrada. No caso da Fibonacci ficaria:

def zfibGen(a: Int, b: Int): ZList[Int] = ZNode(a, u => ZNode(b, u => zfibGen(a+b, a+2*b)))

def zfibDir = zfibGen(1,1)

Percebes-te?

Cumprimentos

 
Imagen de Pedro Santos
Re: Definições de Fibonacci e outras
de Pedro Santos - sábado, 29 de setembro de 2012, 13:53
 

Obrigado pela resposta.

Ou seja, sempre que utitlize a própria definição na sua própria definição, posso considerar circular. Mesmo que dependa de definições auxiliares. Certo?

Imagen de Artur Miguel Dias
Re: Definições de Fibonacci e outras
de Artur Miguel Dias - domingo, 30 de setembro de 2012, 19:07
 

É isso.

Em ambos os casos, o normal é usar funções auxiliares. Por exemplo, na teórica 2, a definição circular de zints usa a função auxiliar zadd e a definição direta de zints usa a função auxiliar zcount_from.

O que muda é a atitude. Por exemplo, numa definição direta geramos a os valores da sequência de forma direta e explícita, um de cada vez, de acordo com uma regra que temos de inventar.