ajuda no trabalho

[dardevil]

boas pessoal, precisava que alguem me ajudasse a resolver este problema. nao tou a conseguir resolver por mais voltas que de. se puderem ajudar era bom xD

Defina a função tib::Integer->Integer que, avaliada com o argumento inteiro não negativo n, é o (n+1)-ésimo elemento da seguinte sequência: 1,1,1,3,5,9,17,31,57,105… (i.e., cada valor, excepto os três primeiros, é a soma dos três anteriores). A sua definição recursiva não deve ter complexidade exponencial.

Por exemplo, a avaliação de tib3 100 resulta em 127071617887002752149434981

cumps o/

[Betovsky]

Claro que ajudamos. Tens é de dar mais informações. Que é que já tentaste fazer? Em que parte concreta tens dúvidas?

[dardevil]

o problema é que eu ainda não percebo muito este tipo de linguagem, era por isso que precisava de ajuda... ja comecei o fazer o mais simples a assinatura e o caso base, o problema vem a seguir lol... se fosse em java ja tava feito lool...

cumps o/

[Rui Carlos]

Podes começar por meter aqui a versão em Java. Se tiveres uma versão recursiva em Java a conversão também não será muito complicada.

[joxnas]

tibactual::Int->Int
tibactual 1 = 1
tibactual 2 = 1
tibactual 3 = 1
tibactual x = tibactual (x-3) + tibactual (x-1) + tibactual (x-2)

tib3::Int->Int
tib3 x = tibactual (x) + tibactual (x-1) + tibactual (x-2)

Será isto que queres?

[dardevil]

tibactual::Int->Int
tibactual 1 = 1
tibactual 2 = 1
tibactual 3 = 1
tibactual x = tibactual (x-3) + tibactual (x-1) + tibactual (x-2)

tib3::Int->Int
tib3 x = tibactual (x) + tibactual (x-1) + tibactual (x-2)

Será isto que queres?

E isto mesmo xD

Brigadao joxnas, e ao resto do pessoal...

o/

[Betovsky]

E isto mesmo xD

Brigadao joxnas, e ao resto do pessoal...

o/

Cuidado que essa solução é exponencial. Pensava que era um requerimento a solução não ser exponencial.

Podes alterar ligeiramente para ficar de acordo.

Tens 2 hipóteses,

- Aplicar memoização;

- Passar como argumentos, a cada passo, os 3 valores que precisas já calculados.