Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Para dada altura h, quantas piramides podemos formar de base n?

0 votos
26 visitas
perguntada Abr 2 em Ciência da Computação por Julia Regina Scotti (31 pontos)  
editado Abr 2 por Julia Regina Scotti

Imagine a função g, que recebe dois parãmetros, h, a altura da pirâmide e n, o tamanho da base da pirâmide, conforme a figura abaixo:

A imagem será apresentada aqui.

Essa função g retorna a quantidade de pirâmides factíveis com aquela altura e base.

Pede-se que se defina essa função g recursivamente. E finalemente, que se teste a reposta considerando que a soma das g para dado é dada pela sequência de Fibonacci de F(2n-1)

Compartilhe

1 Resposta

+1 voto
respondida Abr 2 por Julia Regina Scotti (31 pontos)  

Inicialmente note que:

  • g(1,n)=1 para todo n

  • g(i,i) = 1 para todo i

  • g(h,n) onde h>n = 0

Então, imagine uma matriz em que as colunas são os difenrentes ns, e as linhas são os diferentes hs, e que os elementos dessa matriz são justamente os g(h,n), então a primeira linha será toda de 1s, a diagonal principal também será formada por 1s e a matriz é triangular superior.

Além disso, a soma dos elementos de cada coluna é F(2n-1), fato que será usado para testar se nossa função g está correta.

Agora, note o padrão que se forma nos elementos a determinar:

A imagem será apresentada aqui.

ou seja, g(h,n) = somatório de (i=1) até (n-1) de (n-i)*g(h-1, i)

que pode ser facilmente implementado como:

def g(h,n):
    if (h>n):
        return 0
    elif h==1:
        return 1
    elif (h==n):
        return 1
    elif (n>h):
        aux = 0
        for i in range(1,n):
            aux = aux + (n-i)*g(h-1,i)
        return aux

Para verificar:

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)


def total(n):
    aux = 0
    for i in range(n):
        aux = aux + g(i+1,n)    
    return aux

#Fazendo os testes

for i in range(1,10):
    if total(i)==fib(2*i-1):
        print('Para n =', i, 'o resultado verificou e era', total(i))
    else:
        print('ops')

cujo resultado é:

Para n = 1 o resultado verificou e era 1
Para n = 2 o resultado verificou e era 2
Para n = 3 o resultado verificou e era 5
Para n = 4 o resultado verificou e era 13
Para n = 5 o resultado verificou e era 34
Para n = 6 o resultado verificou e era 89
Para n = 7 o resultado verificou e era 233
Para n = 8 o resultado verificou e era 610
Para n = 9 o resultado verificou e era 1597

comentou Jun 16 por Pedro Henrique T (16 pontos)  
Bom exercício. A programação poderia ficar um pouco mais enxuta e sem perder a clareza se, quando a função g(h,n) estiver que retornar o valor 1, usarmos uma única condição (h==1|h==n).
...