Como resolver essa questão envolvendo estrutura de dados

[jeander]

Alguém sabe como se resolve essa questão??

Suponha esta função QUANTO:

FUNÇÃO QUANTO(m, n: inteiro): inteiro

SE ( m = 2n) OU ( m = 2)

ENTÃO QUANTO := 3

SENÃO QUANTO := QUANTO( m - 2, n) + QUANTO(m , n - 1)

FIM DO SE

FIM DA FUNÇÃO QUANTO

Assinale a alternativa que apresenta o resultado CORRETO de QUANTO(8, 6).

A) 63

66

C) 69

D) 72

A resposta é a B.

[Trebloc]

Alguém sabe como se resolve essa questão??

Suponha esta função QUANTO:

FUNÇÃO QUANTO(m, n: inteiro): inteiro

SE ( m = 2n) OU ( m = 2)

ENTÃO QUANTO := 3

SENÃO QUANTO := QUANTO( m - 2, n) + QUANTO(m , n - 1)

FIM DO SE

FIM DA FUNÇÃO QUANTO

Assinale a alternativa que apresenta o resultado CORRETO de QUANTO(8, 6).

A) 63

66

C) 69

D) 72

A resposta é a B.

Bom, como você deve saber, essa é uma função recursiva. Vou mostrar o que acontece nas primeiras chamadas só pra você entender:

QUANTO(8, 6)

m = 8 e n = 6

FUNÇÃO QUANTO(m, n: inteiro): inteiro
SE ( m = 2n) OU ( m = 2)

Chamada 1 - QUANTO(8, 6)

Como m não é o dobro de n (2 * 6 = 12) e nem m vale 2, a condição não é satisfeita; entramos no senão:

SENÃO QUANTO := QUANTO( m - 2, n) + QUANTO(m , n - 1)

Isso equivale à:

QUANTO := QUANTO(6, 6) + QUANTO(8, 5)

Chamada 1A - QUANTO(6, 6)

As condições do SE novamente não são satisfeitas e entramos no senão, agora fazendo mais duas chamadas:

QUANTO := QUANTO(4, 6) + QUANTO(6, 5)

Chamada 1Aa - QUANTO (4, 6)

Já vemos que também não satisfaz a condição, logo também faz mais duas chamadas:

QUANTO := QUANTO(2, 6) + QUANTO(4, 5)

Chamada 1Aa1 - QUANTO (2, 6)

Satisfaz a condição, pois m = 2. É retornado 3.

Chamada 1Aa2 - QUANTO (4, 5)

Não satisfaz a condição e portanto retornará:

QUANTO := QUANTO(2, 5) + QUANTO(2, 4)

Em ambas, m = 2, portanto retornarão 3. A função que as chamou, QUANTO(4, 5), valerá 6. Voltando algumas chamadas:

Chamada 1Aa - QUANTO(4, 6)

QUANTO := QUANTO(2, 6) + QUANTO(4, 5)

Como visto, essa expressão equivale à:

QUANTO := 3 + 6

Portanto retorna 9. Voltando à quem fez a chamada 1Aa:

Chamada 1A - QUANTO(6, 6)

QUANTO := QUANTO(4, 6) + QUANTO(6, 5)

Sabemos que QUANTO(4, 6) vale 9, resta sabermos a outra.

Chamada 1Ab - QUANTO(6 ,5)

...

E assim segue. Espero que tenha captado a ideia e sugiro que estude mais funções recursivas.

[duda3005]

Funçoes recursivas são chatas de pegar no começo e bem "extensas" de se fazer..

meu conselho é.... pegue um papel... e vá fazendo..

tentar resolver de cabeça nao tem como...

sempre que for fazer o famoso "teste de mesa" vá escrevendo os passos que está seguindo, quais os valores de todas as variaves a cada passo ( mesmo as que nao se alteram )...

para acompanhar o processo que o algoritimo faz..

Acredito que a resposta da questão em si do tópico foi respondida já pelo nosso amigo Trebloc.

[RooT]

Qualquer coisa existe o seguinte tópico que foi escrito para Estruturas de Dados em C, mas serve para entender o funcionamento das EDs em qualquer linguagem, pois é fácil assimilar os algoritmos:

http://forum.clubedohardware.com.br/estruturas-dados-pilhas/702596

[jayrojr]

Caramba, essa questão ta osso viu...

Fiz o chinês passo a passo e não acho a resposta correta de jeito nenhum, meu resultado ta dando 96

A explicação do Trebloc está ótima, no entanto o ponto que eu estou fazendo diferente é nesse trecho abaixo:

>>Chamada 1Aa2 - QUANTO (4, 5)

>>Não satisfaz a condição e portanto retornará:

>>Código: QUANTO := QUANTO(2, 5) + QUANTO(2, 4)

>>Em ambas, m = 2, portanto retornarão 3. A função que as chamou, QUANTO(4, 5), valerá 6. Voltando algumas chamadas:

Não consigo entender porque

QUANTO := QUANTO(2, 5) + QUANTO(2, 4)

pois o m=4 e não m=2, dentro dessa função QUANTO(4, 5)!

Ao meu entender, deveria ser

QUANTO := QUANTO(2, 5) + QUANTO(4, 4)

da mesma forma como foi feito nas funções anteriores

Por exemplo, na Chamada 1A - QUANTO(6, 6), ficou:

QUANTO := QUANTO(4, 6) + QUANTO(6, 5)

O que aconteceu de diferente na Chamada 1Aa2 - QUANTO (4, 5):

QUANTO := QUANTO(2, 5) + QUANTO(2, 4)

???

Será que consegui ser claro na minha dúvida?

To achando que vou fazer um programinha e debugar pra ver como ele vai se comportar porque na ponta do lápis não ta rolando de jeito nenhum...