algorithm - pascales - ¿Cómo calcular eficientemente una fila en el triángulo de pascal?

triangulo de pascal ejercicios

Question

Estoy interesado en encontrar la enésima fila del triángulo pascal (no un elemento específico sino toda la fila en sí). ¿Cuál sería la forma más eficiente de hacerlo?

Pensé en la forma convencional de construir el triángulo al resumir los elementos correspondientes en la fila de arriba que tomaría:

1 + 2 + .. + n = O(n^2)

Otra forma podría ser usando la fórmula de combinación de un elemento específico:

c(n, k) = n! / (k!(n-k)!)

para cada elemento en la fila, que supongo que tomaría más tiempo, el método anterior depende de la forma de calcular la combinación. ¿Algunas ideas?

Answer 1

Aquí hay un ejemplo rápido implementado en go-lang que calcula a partir de los bordes exteriores de una fila y se dirige al medio asignando dos valores con un solo cálculo ...

package main

import "fmt"

func calcRow(n int) []int {
    // row always has n + 1 elements
    row := make( []int, n + 1, n + 1 )

    // set the edges
    row[0], row[n] = 1, 1

    // calculate values for the next n-1 columns
    for i := 0; i < int(n / 2) ; i++ {
        x := row[ i ] * (n - i) / (i + 1)

        row[ i + 1 ], row[ n - 1 - i ] = x, x
    }

    return row
}

func main() {
    for n := 0; n < 20; n++ {
        fmt.Printf("n = %d, row = %v/n", n, calcRow( n ))
    }
}

la salida de 20 iteraciones tarda aproximadamente 1/4 milisegundos en ejecutarse ...

n = 0, row = [1]
n = 1, row = [1 1]
n = 2, row = [1 2 1]
n = 3, row = [1 3 3 1]
n = 4, row = [1 4 6 4 1]
n = 5, row = [1 5 10 10 5 1]
n = 6, row = [1 6 15 20 15 6 1]
n = 7, row = [1 7 21 35 35 21 7 1]
n = 8, row = [1 8 28 56 70 56 28 8 1]
n = 9, row = [1 9 36 84 126 126 84 36 9 1]
n = 10, row = [1 10 45 120 210 252 210 120 45 10 1]
n = 11, row = [1 11 55 165 330 462 462 330 165 55 11 1]
n = 12, row = [1 12 66 220 495 792 924 792 495 220 66 12 1]
n = 13, row = [1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1]
n = 14, row = [1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1]
n = 15, row = [1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1]
n = 16, row = [1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1]
n = 17, row = [1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1]
n = 18, row = [1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1]
n = 19, row = [1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1]

Answer 2

Aquí hay una solución de complejidad de espacio O (n) en Python:

def generate_pascal_nth_row(n):
    result=[1]*n
    for i in range(n):
        previous_res = result.copy()
        for j in range(1,i):
            result[j] = previous_res[j-1] + previous_res[j]
    return result

print(generate_pascal_nth_row(6))

Answer 3

El enfoque más eficiente sería:

std::vector<int> pascal_row(int n){
    std::vector<int> row(n+1);
    row[0] = 1; //First element is always 1
    for(int i=1; i<n/2+1; i++){ //Progress up, until reaching the middle value
        row[i] = row[i-1] * (n-i+1)/i;
    }
    for(int i=n/2+1; i<=n; i++){ //Copy the inverse of the first part
        row[i] = row[n-i];
    }
    return row;
}

Answer 4

En Ruby, el siguiente código imprimirá la fila específica del Triángulo de Pascales que desee:

def row(n)
  pascal = [1]
  if n < 1
    p pascal
    return pascal
  else
    n.times do |num|
      nextNum = ((n - num)/(num.to_f + 1)) * pascal[num]
      pascal << nextNum.to_i
    end
  end
  p pascal
end

Donde la row(0) llama row(0) devuelve [1] y la row(5) devuelve [1, 5, 10, 10, 5, 1]

Answer 5

En la programación de Scala: lo habría hecho de una manera tan simple como esto:

def pascal(c: Int, r: Int): Int = c match {
    case 0 => 1
    case `c` if c >= r => 1
    case _ => pascal(c-1, r-1)+pascal(c, r-1)
}

Lo llamaría dentro de esto:

for (row <- 0 to 10) {
    for (col <- 0 to row)
        print(pascal(col, row) + " ")
    println()
}

resultando a:

. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1

Para explicar paso a paso:

Paso 1: Nos aseguramos de que si nuestra columna es la primera, siempre devolvamos la figura 1.

Paso 2: desde cada fila X hay un número X de columnas. Así que decimos eso; la última columna X es mayor o igual a la X-ésima fila, luego la cifra de retorno 1.

Paso 3: De lo contrario, obtenemos la suma del pascal repetido de la columna justo antes de la actual y la fila justo antes de la actual; y el pascal de esa columna y la fila justo antes de la actual.

Buena suerte.

Answer 6

Esta es la otra forma mejor y más sencilla de diseñar un Triángulo Pascal dinámicamente usando VBA.

`1
11
121
1331
14641`

`Sub pascal()
Dim book As Excel.Workbook
Dim sht As Worksheet
Set book = ThisWorkbook
Set sht = book.Worksheets("sheet1")
a = InputBox("Enter the Number", "Fill")
For i = 1 To a
    For k = 1 To i
        If i >= 2 And k >= 2 Then
            sht.Cells(i, k).Value = sht.Cells(i - 1, k - 1) + sht.Cell(i-  1, k)
        Else
            sht.Cells(i, k).Value = 1
        End If
    Next k
Next i
End Sub`

Answer 7

La forma más eficiente de calcular una fila en el triángulo de Pascal es a través de la convolución. Primero elegimos la segunda fila (1,1) para ser un kernel y luego, para obtener la siguiente fila, solo tenemos que convertir la fila actual con el kernel.

Así que la convolución del núcleo con la segunda fila da la tercera fila [1 1]*[1 1] = [1 2 1] , la convolución con la tercera fila da la cuarta [1 2 1]*[1 1] = [1 3 3 1] y así sucesivamente

Esta es una función en julia-lang (muy simular a matlab):

function binomRow(n::Int64)
baseVector = [1] #the first row is equal to 1. 
kernel = [1,1]   #This is the second row and a kernel. 
row = zeros(n)
for i = 1 : n
    row = baseVector 
    baseVector = conv(baseVector, kernel) #convoltion with kernel
end
return row::Array{Int64,1}
end

Answer 8

Una manera fácil de calcularlo es notar que el elemento de la fila siguiente se puede calcular como una suma de dos elementos consecutivos en la fila anterior.

[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

Por ejemplo 6 = 5 + 1 , 15 = 5 + 10 , 1 = 1 + 0 y 20 = 10 + 10 . Esto proporciona un algoritmo simple para calcular la siguiente fila de la anterior.

def pascal(n):
    row = [1]
    for x in xrange(n):
        row = [l + r for l, r in zip(row + [0], [0] + row)]
    # print row
    return row

print pascal(10)

Answer 9

Una sola fila se puede calcular de la siguiente manera:

First compute 1.               -> N choose 0
Then N/1                       -> N choose 1
Then N*(N-1)/1*2               -> N choose 2
Then N*(N-1)*(N-2)/1*2*3       -> N choose 3
.....

Observe que puede calcular el siguiente valor desde el valor anterior, simplemente multiplicando por un solo número y luego dividiéndolo por otro número.

Esto se puede hacer en un solo bucle. Muestra de pitón.

def comb_row(n):
   r = 0
   num = n
   cur = 1
   yield cur
   while r <= n:
      r += 1  
      cur = (cur* num)/r
      yield cur
      num -= 1

Answer 10

Usé Ti-84 Plus CE

El uso de -> en la línea 6 es el botón de valor de la tienda

Forloop syntax is 
:For(variable, beginning, end [, increment])
:Commands
:End

nCr syntax is 
:valueA nCr valueB

Los índices de la lista comienzan en 1, por eso lo configuro en R + 1

N= row
R= column

PROGRAM: PASCAL
:ClrHome
:ClrList L1
:Disp "ROW
:Input N
:For(R,0,N,1)
:N nCr R–>L1(R+1)
:End
:Disp L1

Esta es la forma más rápida que se me ocurre para hacer esto en la programación (con un ti 84), pero si quiere poder calcular la fila usando lápiz y papel, simplemente dibuje el triángulo porque los factores son un problema.

Answer 11

>>> def pascal(n):
...   line = [1]
...   for k in range(n):
...     line.append(line[k] * (n-k) / (k+1))
...   return line
... 
>>> pascal(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

Esto utiliza la siguiente identidad:

C(n,k+1) = C(n,k) * (n-k) / (k+1)

Así que puedes comenzar con C(n,0) = 1 y luego calcular el resto de la línea usando esta identidad, multiplicando cada vez el elemento anterior por (nk) / (k+1) .