Introdução
Com um tempo tão bom, não estás com grande vontade de passar uma hora numa sala de aula. Irritado, entras na sala e reparas num triângulo estranhamente satisfatório desenhado 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 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 formas podes escolher K elementos entre N valores.
- Contém a sucessão de Fibonacci.
- Se colorires os números ímpares e os pares de forma diferente, obténs um padrão bonito chamado triângulo de Sierpiński.
O professor pede-te a ti e aos teus colegas para procurar outras aplicações, e garante-te que há imensas mais! Nesse momento, toca o sinal da escola. Dás-te conta de que, durante a última hora, estiveste completamente absorto a aprender sobre o triângulo de Pascal. Agarras rapidamente o portátil da mochila e sais para a rua, pronto para aproveitar o sol e 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:
