Escreva um programa que leia um número inteiro positivo
e em seguida imprima
linhas do chamado Triangulo de Pascal:
1
1 1
121
1 3 3 1
14641
1 5 10 10 5 1
1
1 1
121
1 3 3 1
14641
1 5 10 10 5 1
Passo 1
A gente precisa ler um inteiro positivo n e imprimir as primeiras n linhas do Triângulo de Pascal, onde cada linha i (contando de 0) tem os coeficientes binomiais
. Esse exercício cai em combinatória e otimização de cálculo de coeficientes binomiais.
Passo 2
O Triângulo de Pascal é formado pelos coeficientes binomiais, que podem ser definidos pela fórmula em bloco:
Mas usar fatoriais diretos fica caro. Uma forma mais eficiente é gerar cada linha iterativamente:
- Começamos com
para . - A cada novo
, atualizamos por
Isso evita overflow rápido e calcula cada coeficiente em tempo constante por elemento.
Passo 3
O algoritmo geral fica assim:
- Ler
. - Para cada linha
de 0 até :
a) Inicializar.
b) Para cada posiçãode 0 até : - Se
, imprimir um espaço antes de . - Imprimir
. - Atualizar
.
c) Após o laço de k, imprimir fim de linha.
- Se
Passo 4
Agora, implementamos o programa em C de acordo com esse algoritmo. Ele lê
de stdin e escreve no formato pedido sem espaço extra no final de cada linha.
Resposta
#include <stdio.h>
int main() {
int n;
if (scanf("%d", &n) != 1 || n <= 0) return 0;
int n;
if (scanf("%d", &n) != 1 || n <= 0) return 0;
for (int i = 0; i < n; i++) {
long long C = 1;
for (int k = 0; k <= i; k++) {
if (k > 0) printf(" ");
printf("%lld", C);
C = C * (i - k) / (k + 1);
}
printf("\n");
}
return 0;
}