Solução dos Exercícios e Desafio da Semana

Olá! É hora de conferir a solução do exercício e do desafio. Primeiro vamos ao exercício: escrever um módulo com duas funções que calculam o fatorial de um número, sendo uma recursiva e a outra linear:

# coding: utf-8
# fatorial.py

def fatorial_recursivo(numero):
    if numero == 1:
        return 1
    return numero * fatorial_recursivo(numero - 1)

def fatorial_linear(numero):
    k = numero - 1
    fatorial = numero
    while k > 0:
        fatorial = fatorial * k
        k -= 1
    return fatorial

if __name__ == '__main__':
    print fatorial_recursivo(5)
    print fatorial_linear(5)

Não tem muito mistério na solução acima. Apenas quero destacar um ponto: na versão linear, temos um comando que em Python pode ser reescrito de forma simplificada: "fatorial = fatorial * k". Isto pode ser reescrito como "fatorial *= k". Tal operação significa que a variável "fatorial" irá receber o resultado do seu valor atual multiplicado pelo valor da variável "k". Esta forma do comando também é válida para outras operações, tais como soma, subtração e divisão.

Agora a solução do desafio: o problema das Torres de Hanoi. Para resolver este problema utilizamos o princípio da indução, fazendo algumas suposição que assumiremos como verdade.

Como chegamos a resolução do problema para "n" anéis? Vamos simplificar: Suponha que você sabe solucionar o problema para "n - 1" anéis. Para solucionar o problema com "n" anéis, solucione o problema com "n - 1" anéis primeiro, mas movendo estes "n - 1" anéis para o pino temporário. Sendo assim, ao final desta etapa você terá "n - 1" anéis no pino temporário e o maior anel ainda estará no pino inicial. O pino destino estará, então, vazio, e você poderá mover o maior anel para ele diretamente. Agora, basta solucionar novamente o problema para "n - 1" anéis, movendo os "n - 1" anéis to pino temporário para o pino destino, utilizando o pino inicial como pino temporário.

Calma, se você ainda não entendeu não se preocupe, isto é normal. Leva um certo tempo para se acostumar com toda essa maluquice! Mas com a prática isto se tornará tão natural como se levantar pela manhã ao acordar. Vejamos como ficaria o código:

# coding: utf-8
# hanoi.py

def hanoi(n, inicial, destino, temporario):
    if n == 1:
        print 'Mova um anel do pino', inicial, 'para o pino', destino
    else:
        hanoi(n - 1, inicial, temporario, destino)
        print 'Mova um anel do pino', inicial, 'para o pino', destino
        hanoi(n - 1, temporario,  destino, inicial)

if __name__ == '__main__':
    # executar o procedimento para 5 anéis, sendo o pino 1 o inicial, o pino 2 o destino
    # e o pino 3 é o temporário
    hanoi(5, 1, 2, 3)

Executem o código acima e verifiquem que o resultado está correto! Estudem um pouco o seu funcionamento até que tenham entendido como ele funciona. Caso ainda tenham dúvidas, enviem um comentário que irei tentar ajudar a compreender melhor a solução.

Até a próxima!