Introdução
Com o tempo tão bonito lá fora, você não está com a menor vontade de passar uma hora numa sala de aula.
Meio de mau humor, você entra na sala e repara num triângulo estranhamente satisfatório desenhado na lousa.
Enquanto espera o professor de matemática chegar, você não consegue deixar de notar alguns padrões no triângulo: os valores das bordas são todos 1, cada linha tem um valor a mais que a anterior e o triângulo é simétrico.
Que estranho!
Não muito depois de você se sentar, o professor entra na sala e explica que esse triângulo é o famoso triângulo de Pascal.
Ao longo da hora seguinte, o professor revela algumas coisas incríveis escondidas nesse triângulo:
- Ele pode ser usado para calcular de quantas maneiras você pode escolher K elementos entre N valores.
- Ele contém a sequência de Fibonacci.
- Se você colorir os números ímpares e pares de forma diferente, surge um padrão lindo chamado de triângulo de Sierpiński.
O professor pede que você e seus colegas pesquisem outros usos, e garante que existem muitos mais!
Nesse momento, o sinal da escola toca.
Você percebe que a última hora passou voando enquanto você aprendia sobre o triângulo de Pascal.
Você pega o notebook da mochila rapidinho e sai, para aproveitar tanto o sol quanto as maravilhas do triângulo de Pascal.
Instruções
Sua tarefa é produzir as primeiras N linhas do triângulo de Pascal.
O triângulo de Pascal é um array triangular de números inteiros positivos.
No triângulo de Pascal, a quantidade de valores em uma linha é igual ao número da linha (que começa em um).
Portanto, a primeira linha tem um valor, a segunda tem dois, e assim por diante.
A primeira linha (a do topo) tem um único valor: 1.
Os valores das linhas seguintes são calculados somando os números imediatamente à direita e à esquerda da posição atual na linha anterior.
Se a linha anterior não tiver um valor à esquerda ou à direita da posição atual (o que só acontece nas posições mais à esquerda e mais à direita), trate o valor dessa posição como zero (na prática, "ignorando-o" na soma).
Exemplo
Vamos ver as primeiras 5 linhas do triângulo de Pascal:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
A linha do topo tem um valor, que é 1.
Os valores mais à esquerda e mais à direita têm apenas uma posição anterior para considerar: a posição à sua direita, no primeiro caso, e à sua esquerda, no segundo.
Como o valor do topo é 1, conclui-se que todos os valores mais à esquerda e mais à direita também são 1.
Os outros valores têm duas posições para considerar.
Por exemplo, o valor do meio da quinta linha (1 4 6 4 1) é 6, já que os valores à sua esquerda e à sua direita na linha anterior são 3 e 3:
Como este exercício é implementado em Python: recursão
Este exercício foi projetado para ser resolvido com recursion, em vez de laços.
Uma função recursiva é uma função que chama a si mesma, o que é útil ao resolver problemas definidos em termos de si mesmos.
Para evitar a recursão infinita (ou, mais especificamente, evitar estourar a pilha), usa-se algo chamado de "caso base".
Quando o caso base é atingido, um valor não recursivo é retornado, o que permite que a chamada de função anterior se resolva e retorne seu valor, e assim por diante, propagando-se de volta pela pilha até que a primeira chamada de função retorne a resposta.
Poderíamos escrever uma função recursiva para encontrar a resposta de 5! (ou seja, 5 * 4 * 3 * 2 * 1) assim:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Por fim, vale notar que o Python limita o número de vezes que chamadas recursivas podem ser feitas (1000 por padrão) e não otimiza a recursão de cauda.
Mensagens de exceção
Às vezes é necessário lançar uma exceção.
Quando você faz isso, deve sempre incluir uma mensagem de erro significativa para indicar qual é a origem do erro.
Isso deixa seu código mais legível e ajuda muito na depuração.
Em situações em que você sabe que a origem do erro será de um tipo específico, você pode optar por lançar um dos tipos de erro internos, mas ainda deve incluir uma mensagem significativa.
Este exercício específico exige que você use a instrução raise para "lançar" vários ValueErrors se a função rows() receber um número negativo.
Os testes só passarão se você usar raise na exception e incluir uma mensagem com ela.
Para lançar uma ValueError com uma mensagem, escreva a mensagem como argumento para o tipo exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
