Este tutorial ensinará como imprimir o triângulo de Pascal em Python para um determinado número de linhas.
Você começará aprendendo a construir o triângulo de Pascal. Você então escreverá uma função Python e aprenderá a otimizá-la ainda mais.
▶️ Vamos começar!
últimas postagens
O que é o Triângulo de Pascal e como construí-lo?
Imprimir o triângulo de Pascal para um determinado número de linhas é uma pergunta popular em entrevistas.
No triângulo de Pascal com n linhas, o número da linha i tem i elementos.
Então a primeira linha tem um elemento, e é 1. E cada elemento nas linhas subseqüentes é a soma dos dois números diretamente acima dela.
A figura a seguir explica como construir o triângulo de Pascal com cinco linhas.
Triângulo de Pascal para numRows = 5 (Imagem do autor)
Observe como você pode preencher zeros quando tiver apenas um número acima de um determinado número.
📝Como exercício rápido, siga o procedimento acima para construir o triângulo de Pascal para n = 6 e n = 7.
Em seguida, vamos continuar a escrever algum código. Você pode optar por executar os trechos de código no Python IDE do etechpt.com diretamente do seu navegador — enquanto você trabalha no tutorial.
Função Python para imprimir o triângulo de Pascal
Nesta seção, vamos escrever uma função Python para imprimir o triângulo de Pascal para qualquer número de linhas.
Há duas questões-chave a serem consideradas:
- Como expressar as entradas no triângulo de Pascal?
- Como imprimir o triângulo de Pascal com espaçamento e formatação adequados?
Vamos respondê-las agora.
#1. Qual é a expressão para cada entrada no triângulo de Pascal?
Acontece que as entradas no triângulo de Pascal podem ser obtidas usando a fórmula para nCr. Se você se lembrar da matemática da escola, nCr denota o número de maneiras pelas quais você pode escolher r itens de um conjunto de n itens.
A fórmula para nCr é dada abaixo:
Fórmula nCr (Imagem do autor)
Agora vamos expressar as entradas no triângulo de Pascal usando a fórmula nCr.
Entradas de triângulo de Pascal usando nCr (Imagem do autor)
Agora encontramos uma maneira de expressar as entradas na matriz.
#2. Como ajustar o espaçamento ao imprimir o padrão?
No triângulo de Pascal com numRows, a linha #1 tem uma entrada, a linha #2 tem duas entradas e assim por diante. Para imprimir o padrão como um triângulo, você precisará de numRows – i espaços na linha #i. E você pode usar a função range do Python em conjunto com o loop for para fazer isso.
Como a função de intervalo exclui o ponto de extremidade por padrão, certifique-se de adicionar + 1 para obter o número necessário de espaços à esquerda.
Agora que você aprendeu a representar entradas e também a ajustar o espaço ao imprimir o triângulo do Pascal, vamos em frente e definir a função pascal_tri.
Analisando a definição da função
Então, o que você quer que a função pascal_tri faça?
- A função pascal_tri deve aceitar o número de linhas (numRows) como argumento.
- Deve imprimir o triângulo de Pascal com numRows.
Para calcular o fatorial, vamos usar a função fatorial do módulo matemático integrado do Python.
▶️ Execute a seguinte célula de código para importar fatorial e use-o em seu módulo atual.
from math import factorial
O trecho de código abaixo contém a definição da função.
def pascal_tri(numRows): '''Print Pascal's triangle with numRows.''' for i in range(numRows): # loop to get leading spaces for j in range(numRows-i+1): print(end=" ") # loop to get elements of row i for j in range(i+1): # nCr = n!/((n-r)!*r!) print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ") # print each row in a new line print("n")
A função funciona da seguinte forma:
- A função pascal_tri tem um parâmetro obrigatório numRows: o número de linhas.
- Existem linhas numRows em todos. Para cada linha i, adicionamos numRows – i espaços iniciais antes da primeira entrada na linha.
- Em seguida, usamos a fórmula nCr para calcular as entradas individuais. Para a linha i, as entradas são iCj onde j = {0,1,2,..,i}.
- Observe que usamos // que realiza a divisão de inteiros, pois gostaríamos que as entradas fossem inteiras.
- Depois de computar todas as entradas em uma linha, imprima a próxima linha em uma nova linha.
🔗 Como adicionamos um docstring, você pode usar a função de ajuda integrada do Python ou o atributo __doc__ para acessar a docstring da função. O trecho de código abaixo mostra como fazer isso.
help(pascal_tri) # Output Help on function pascal_tri in module __main__: pascal_tri(numRows) Print Pascal's triangle with numRows. pascal_tri.__doc__ # Output Print Pascal's triangle with numRows.
Agora vamos em frente e chamar a função com o número de linhas como argumento.
pascal_tri(3) # Output 1 1 1 1 2 1
As primeiras 3 linhas do triângulo de Pascal são impressas, conforme esperado.
Imprima o triângulo de Pascal usando recursão
Na seção anterior, identificamos a expressão matemática de cada entrada no Triângulo de Pascal. No entanto, não utilizamos a relação entre entradas em duas linhas consecutivas.
Na verdade, usamos a linha anterior para calcular as entradas na linha subsequente. Não podemos usar isso e criar uma implementação recursiva da função pascal_tri?
Sim, vamos fazer isso!
Em uma implementação recursiva, uma função chama a si mesma repetidamente até que o caso base seja atendido. Na construção do triângulo de Pascal, começamos com a primeira linha com uma entrada 1 e depois construímos as linhas subsequentes.
Assim, a chamada de função para pascal_tri(numRows) por sua vez chama pascal_tri(numRows-1) e assim por diante, até que o caso base pascal_tri(1) seja alcançado.
Considere o exemplo em que você precisa imprimir as 3 primeiras linhas do triângulo de Pascal. A imagem a seguir explica como as chamadas recursivas são enviadas para a pilha. E como as chamadas de funções recursivas retornam as linhas do triângulo de Pascal.
Pilha de chamadas durante chamadas recursivas (Imagem do autor)
▶️ Execute o trecho de código abaixo para gerar as linhas do triângulo de Pascal recursivamente.
def pascal_tri(numRows): '''Print Pascal's triangle with numRows.''' if numRows == 1: return [[1]] # base case is reached! else: res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri # use previous row to calculate current row cur_row = [1] # every row starts with 1 prev_row = res_arr[-1] for i in range(len(prev_row)-1): # sum of 2 entries directly above cur_row.append(prev_row[i] + prev_row[i+1]) cur_row += [1] # every row ends with 1 res_arr.append(cur_row) return res_arr
Aqui estão alguns pontos que merecem atenção:
- Usamos uma lista aninhada como estrutura de dados, onde cada linha no triângulo de Pascal é uma lista em si, assim: [[row 1], [row 2],…,[row n]].
- A chamada de função pascal_tri(numRows) aciona uma série de chamadas recursivas com numRows – 1, numRows – 2 até 1 como argumentos. Essas chamadas são colocadas em uma pilha.
- Quando numRows == 1, chegamos ao caso base e a função retorna [[1]].
- Agora, a lista retornada é usada pelas funções subsequentes na pilha de chamadas — para calcular a próxima linha.
- Se cur_row for a linha atual, cur_row[i] = linha_anterior[i] + linha_anterior[i+1]—a soma de 2 elementos diretamente acima do índice atual.
Como o array retornado é uma lista aninhada (lista de listas), precisamos ajustar o espaçamento e imprimir as entradas, conforme mostrado na célula de código abaixo.
tri_array = pascal_tri(5) for i,row in enumerate(tri_array): for j in range(len(tri_array) - i + 1): print(end=" ") # leading spaces for j in row: print(j, end=" ") # print entries print("n") # print new line
A saída está correta, como visto abaixo!
# Output 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Função Python para imprimir o triângulo de Pascal para numRows ≤ 5
Ambos os métodos que você aprendeu funcionarão para imprimir o triângulo de Pascal para um número arbitrário de linhas numRows.
No entanto, há momentos em que você precisa imprimir o triângulo de Pascal para um número menor de linhas. E quando o número de linhas que você precisa imprimir é no máximo 5, você pode usar uma técnica simples.
Percorra a figura abaixo. E observe como as potências de 11 são idênticas às entradas do triângulo de Pascal. Além disso, observe que isso funciona apenas até a 4ª potência de 11. Ou seja, 11 elevado às potências {0, 1, 2, 3, 4} fornece as entradas nas linhas de 1 a 5 do triângulo de Pascal.
Vamos reescrever a definição da função, conforme mostrado abaixo:
def pascal_tri(numRows): '''Print Pascal's triangle with numRows.''' for i in range(numRows): print(' '*(numRows-i), end='') # compute power of 11 print(' '.join(str(11**i)))
Veja como a função pascal_tri funciona:
- Assim como nos exemplos anteriores, ajustamos o espaçamento.
- E então, usamos o operador de exponenciação do Python (**) para calcular as potências de 11.
- Como as potências de 11 são números inteiros por padrão, converta-as em uma string usando str(). Agora você tem as potências de 11 como strings.
- Strings em Python são iteráveis, então você pode percorrê-las e acessar um caractere por vez.
- Em seguida, você pode usar o método join() com a sintaxe:
.join( ) para unir elementos em usando como separador. - Aqui, você precisa de um único espaço entre os caracteres, então
será ‘ ‘, é string: potência de 11.
Vamos verificar se a função funciona como pretendido.
pascal_tri(5) # Output 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Como outro exemplo, chame a função pascal_tri com 4 como argumento.
pascal_tri(4) # Output 1 1 1 1 2 1 1 3 3 1
Espero que você saiba como você pode imprimir facilmente o triângulo Pascal para numRows no intervalo de 1 a 5.
Conclusão
Aqui está o que aprendemos:
- Como construir o triângulo de Pascal com o número dado de linhas. Cada número em cada linha é a soma dos dois números diretamente acima dela.
- Escreva uma função Python usando a fórmula nCr = n!/(nr)!.r! para calcular as entradas do triângulo de Pascal.
- Você então aprendeu uma implementação recursiva da função.
- Finalmente, você aprendeu o método ideal para construir o triângulo de Pascal para numRows até 5 — usando as potências de 11.
Se você deseja aprimorar suas habilidades em Python, aprenda a multiplicar matrizes, verifique se um número é primo e resolva problemas em operações com strings. Boa codificação!