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:
