Introdução
Com este tempo esplêndido, não estás nada com vontade de passar uma hora numa sala de aula.
Irritado, entras na sala e reparas numa forma triangular estranhamente satisfatória no quadro.
Enquanto esperas que o teu professor de matemática chegue, não consegues deixar de reparar em alguns padrões no triângulo: os valores das extremidades são todos uns, cada linha seguinte tem mais um valor do que a anterior e o triângulo é simétrico.
Que estranho!
Pouco depois de te sentares, o teu professor entra na sala e explica que este triângulo é o famoso triângulo de Pascal.
Ao longo da hora seguinte, o teu professor revela algumas coisas incríveis escondidas neste triângulo:
- Pode ser usado para calcular de quantas maneiras podes escolher K elementos entre N valores.
- Contém a sequência de Fibonacci.
- Se pintares os números ímpares e pares com cores diferentes, obténs um padrão bonito chamado triângulo de Sierpiński.
O professor apela a ti e aos teus colegas para procurar outras utilizações, e garante que há muitas mais!
Nesse momento, toca o sinal da escola.
Dás-te conta de que, durante a última hora, estiveste completamente absorvido a aprender sobre o triângulo de Pascal.
Agarras rapidamente o portátil da mochila e sais para fora, pronto para aproveitar tanto o sol como as maravilhas do triângulo de Pascal.
Instruções
A tua tarefa é apresentar 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, o número de valores numa linha é igual ao número da linha (que começa em um).
Por isso, a primeira linha tem um valor, a segunda tem dois valores, e assim sucessivamente.
A primeira linha (a do topo) tem um único valor: 1.
Os valores das linhas seguintes calculam-se 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), considera 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 a considerar: a posição à sua direita e à sua esquerda, respetivamente.
Como o valor do topo é 1, conclui-se que todos os valores mais à esquerda e mais à direita também são 1.
Todos os outros valores têm duas posições a considerar.
Por exemplo, o valor central da quinta linha (1 4 6 4 1) é 6, pois 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 concebido para ser resolvido com recursion, em vez de ciclos.
Uma função recursiva é uma função que se chama a si própria, o que é útil para resolver problemas que se definem em termos de si mesmos.
Para evitar recursão infinita (mais concretamente, para evitar o transbordamento da pilha), usa-se aquilo a que se chama um "caso base".
Quando se atinge o caso base, é devolvido um valor não recursivo. Isso permite que a chamada anterior se resolva e devolva o seu valor, e assim sucessivamente, propagando-se pela pilha até a primeira chamada devolver a resposta.
Podíamos escrever uma função recursiva para calcular o fatorial de 5, ou seja, 5! (isto é, 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, convém notar que o Python limita o número de vezes que se podem fazer chamadas recursivas (1000 por predefinição) e não otimiza a recursão de cauda.
Mensagens de exceção
Por vezes é necessário lançar uma exceção.
Quando o fazes, deves incluir sempre uma mensagem de erro significativa que indique qual é a origem do erro.
Isso torna o teu código mais legível e ajuda bastante na depuração.
Nos casos em que sabes que a origem do erro é de um determinado tipo, podes optar por lançar um dos tipos de erro incorporados, mas deves continuar a incluir uma mensagem significativa.
Este exercício em particular exige que uses a instrução raise para "lançar" vários ValueErrors se à função rows() for passado um número negativo.
Os testes só passam se fizeres raise da exception e incluíres uma mensagem com ela.
Para lançar um ValueError com uma mensagem, escreve a mensagem como argumento do tipo de exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
