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

Question

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:

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)

Answer 1

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:

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