Mesmo que você seja iniciante em programação, com certeza já se deparou com problemas como imprimir triângulos em forma de pirâmide, pirâmide invertida e pirâmide completa usando alguns caracteres. Uma variação dos problemas mencionados acima é o Triângulo de Pascal. Neste artigo, discutiremos o que é o Triângulo de Pascal e sua implementação em C++.
Antes de prosseguir, é esperado que você tenha um entendimento básico de declarações condicionais e loops.
O que é o Triângulo de Pascal?
O Triângulo de Pascal recebe esse nome em homenagem ao matemático francês Blaise Pascal. É um triângulo formado por números organizados de uma certa maneira. O triângulo é construído usando um princípio aditivo. O que queremos dizer com princípio aditivo? Bem, cada número dentro do triângulo é obtido somando os dois elementos adjacentes acima dele (isso ficará mais claro após ver a imagem abaixo). Essa regra de obtenção de novos elementos do Triângulo de Pascal se aplica apenas aos elementos internos do triângulo e não aos elementos das bordas. Esses elementos das bordas, exceto a base do triângulo, são iguais a 1.
Agora que sabemos o que é o Triângulo de Pascal, vamos discutir uma de suas propriedades matemáticas mais importantes que nos ajudará na implementação do Triângulo de Pascal por meio de código. Se você tiver um pouco de conhecimento matemático, deve estar familiarizado com o conceito de permutações e combinações. O número de maneiras pelas quais certos objetos podem ser escolhidos a partir de um grupo de objetos é conhecido como combinações.
Qual é a fórmula do Triângulo de Pascal?
A fórmula para calcular o número de maneiras pelas quais r objetos podem ser escolhidos a partir de n objetos é dada abaixo:
Agora, segure-se porque você ficará surpreso com esse fato. Cada elemento no Triângulo de Pascal pode ser calculado usando o número da linha e da coluna do elemento. Por exemplo, o valor do elemento na terceira linha e segunda coluna será igual a 2C1, que é 2. Observe como os números da linha e da coluna são subtraídos por 1 ao calcular o valor. Isso ocorre porque a contagem na programação começa a partir de 0 e não de 1. Veja a imagem abaixo para entender melhor.
Isso também pode ser entendido por meio de expansões binomiais, pois cada coeficiente binomial é igual a um valor no Triângulo de Pascal. Agora que entendemos o que é o Triângulo de Pascal e sua propriedade combinatória, vamos usar essa propriedade para escrever o código.
Como Imprimir o Triângulo de Pascal em Programação C++?
Se você já programou por algum tempo, deve ter implementado vários padrões triangulares usando declarações condicionais e de repetição. A implementação do Triângulo de Pascal é semelhante, com algumas alterações.
Para a implementação, usamos loops aninhados. O loop externo é responsável pela obtenção da indentação da linha. O primeiro loop dentro do loop externo cria a indentação adequada usando espaços para obtermos uma exibição triangular. O segundo loop dentro do loop externo calcula o valor do elemento atual usando o valor do elemento anterior com a ajuda da seguinte fórmula:
Tudo isso acontece dentro de uma função responsável por imprimir o Triângulo de Pascal, que recebe apenas um argumento, que é o número de linhas a serem impressas do Triângulo de Pascal.
Código C++ para o Triângulo de Pascal
// Código C++ aquiSaída:
Complexidade de Tempo
Esse algoritmo é eficiente e requer um tempo de O(n^2) devido ao uso de loops aninhados.
Complexidade de Espaço
Esse algoritmo não requer espaço auxiliar e, portanto, tem uma complexidade de espaço de O(n).
Conclusão
Problemas como esse desenvolvem a mente para a resolução de problemas e, portanto, tornam uma pessoa melhor na solução de problemas. Se você achou o Triângulo de Pascal um pouco difícil de entender, recomendamos que você primeiro tente imprimir a pirâmide completa e depois volte e tente o Triângulo de Pascal novamente. Outro ponto que gostaríamos de chamar sua atenção é que o Triângulo de Pascal pode ser impresso usando várias abordagens diferentes, mas neste artigo discutimos apenas a mais eficiente, juntamente com seu código em C++.
Para aprimorar suas habilidades em competições e em estruturas de dados e algoritmos (DSA, na sigla em inglês), experimente o problema "Palindrome Pairs".
