Como imprimir o triângulo de Pascal em Python

Este tutorial irá ensiná-lo a imprimir triângulo de Pascal em Python para um determinado número de linhas.

Você começará aprendendo a construir o triângulo de Pascal. Em seguida, você escreverá uma função Python e aprenderá a otimizá-la ainda mais.

▶️ Vamos começar!

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, número da linha eu tem eu 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 isto.

A figura a seguir explica como construir o triângulo de Pascal com cinco linhas.

Observe como você pode preencher zeros quando tiver apenas um número acima de um determinado número.

Como um 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 em IDE Python da Tecnologico diretamente do seu navegador – conforme você avança 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 fundamentais a considerar:

• Como expressar as entradas no triângulo de Pascal?
• Como imprimir o triângulo de Pascal com espaçamento e formatação apropriados?

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 lembra da matemática da escola, nCr denota o número de maneiras que você pode escolher r itens de um conjunto de n Unid.

A fórmula para nCr é dado abaixo:

fórmula nCr (Imagem do autor)

Agora vamos expressar as entradas no triângulo de Pascal usando o nCr Fórmula.

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á numRows - i espaços na linha #i. E você pode usar o Python range funcionar em conjunto com for loop para fazer isso.

Enquanto o range função exclui o endpoint 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 as entradas e também a ajustar o espaço ao imprimir o triângulo de Pascal, vamos 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 pendência?

• 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 factorial função do built-in do Python math módulo.

▶️ Execute a seguinte célula de código para importar factorial 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.
• Há numRows linhas ao todo. Para cada linha inós adicionamos numRows - i espaços iniciais antes da primeira entrada na linha.
• Nós então usamos nCr fórmula para calcular as entradas individuais. para linha ias entradas são iCj onde j = {0,1,2,..,i}.
• Observe que usamos // que executa a divisão inteira, pois gostaríamos que as entradas fossem inteiras.
• Depois de calcular todas as entradas em uma linha, imprima a próxima linha em uma nova linha.

Como adicionamos um docstring você pode usar o built-in do Python help função ou o __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 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, como 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 as entradas em duas linhas consecutivas.

Na verdade, usamos a linha anterior para calcular as entradas na linha subsequente. Podemos não usar isso e criar um recursivo implementação da função pascal_tri?

Sim, vamos fazer isso!

Em um recursivo implementação, uma função chama repetidamente a si mesma até que o caso base é cumprida. Na construção do triângulo de Pascal, começamos com a primeira linha com uma entrada 1e, em seguida, crie as linhas subsequentes.

Portanto, a chamada de função para pascal_tri(numRows) por sua vez chama pascal_tri(numRows-1) e assim por diante, até o caso base pascal_tri(1) é atingido.

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 colocadas na 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 recursivamente as linhas do triângulo de Pascal.

  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 vale a pena observar:

• Usamos uma lista aninhada como estrutura de dados, onde cada linha no triângulo de Pascal é uma lista em si, assim: ((linha 1), (linha 2),…,(linha n)).
• A chamada de função pascal_tri(numRows) dispara uma série de chamadas recursivas com numRows - 1, numRows - 2 todo o caminho até 1 como os argumentos. Essas chamadas são colocadas em uma pilha.
• Quando numRows == 1chegamos ao caso base e a função retorna ((1)).
• Agora a lista retornada é usada pelas funções subseqüentes na pilha de chamadas — para computar a próxima linha.
• Se cur_row é a linha atual, cur_row(i) = prev_row(i) + prev_row(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 for no máximo 5, você pode usar uma técnica direta.

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 quarta potência de 11. Ou seja, 11 elevado às potências {0, 1, 2, 3, 4} fornece as entradas nas linhas 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:

• 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 inteiros por padrão, converta-as em uma string usando str(). Agora você tem as potências de 11 como cordas.
• As strings em Python são iteráveis ​​- portanto, você pode percorrê-las e acessar um caractere por vez.
• Em seguida, você pode usar o join() método com a sintaxe: <sep>.join(<iterable>) juntar elementos em <iterable> usando <sep> como separador.
• Aqui você precisa de um solteiro espaço entre os caracteres, então <sep> vai ser ' ', <iterable> é 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ê entenda como pode facilmente imprimir o triângulo de 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 de linhas dado. Cada número em cada linha é a soma dos dois números diretamente acima dele.
• 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 um 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 o potências de 11.

Se você deseja aprimorar suas habilidades em Python, aprenda a multiplique matrizes verifique se um número é primo e resolva problemas em operações de string . Codificação feliz!