lunes, 30 de abril de 2018

Triángulo de Pascal o triángulo de Tartaglia en JavaScript

El triángulo de Pascal o también denominado triángulo de Tartaglia se forma comenzando en 1 en el vértice superior y luego sumando los dos superiores.


Podemos programarlo en JS (Java Script) por varios métodos.

Método 1

Usando números combinatorios.

Los elementos del triángulo se obtienen con los números combinatorios indicando su fila-1 y columna -1. Así el vértice, que es un 1, es el número combinatorio 0 sobre 0, que da como resultado 1.


Siendo la fórmula para obtener las combinaciones de n sobre k la siguiente.


También hemos tenido que programar el cálculo del factorial de un número.

Factorial(n) = n! = n × (n-1) × (n-2) × ··· ×1

siendo el factorial de cero igual a 1.

0! = 1

Veamos el archivo index.html y el archvio index.js.

index.html

 <!DOCTYPE html>  
 <html>  
  <head>  
   <meta charset="utf-8">  
   <meta name="triangulo Pascal" content="width=device-width">  
   <title>Triángulo de Pascal o triángulo de Tartaglia</title>  
   <link href="index.css" rel="stylesheet" type="text/css" />  
  </head>  
  <body>  
   <h2>Triángulo de Pascal o triángulo de Tartaglia</h2>  
   <p id="resultado"></p>  
   <script src="index.js"></script>  
  </body>  
 </html>  

index.js

 var n=20; //número de filas  
 //creamos la matriz bidimensional A(n,n)  
 var A=new Array(n);  
 for (var i=1;i<=n;i++) {  
  A[i] = new Array(n);  
 }  
 //alimentamos la matriz  
 for(i=1;i<=n;i++){  
  for(j=1;j<=i;j++){  
   A[i][j]=combina(i-1,j-1);  
  }  
 }  
 //imprimimos los resultados  
 var texto='';  
 for(i=1;i<=n;i++){  
  for(j=1;j<=i;j++){  
   texto+=A[i][j];  
   texto+= " ";  
  }  
  texto+= "<br>";  
 }  
 document.getElementById("resultado").innerHTML =  
 texto;  
 //función que calcula el número combinatorio p sobre q  
 function combina(p,q){  
  return  Math.round(fact(p)/(fact(q)*fact(p-q)));   
 }  
 //función que calcula el factorial  
 function fact(h){  
  var f=1;  
  if (h!==0){  
   for (k=1;k<=h;k++){  
    f*=k;  
   }  
  }  
  return f;  
 }  


El resultado para 20 filas es el siguiente.

Triángulo de Pascal o triángulo de Tartaglia

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
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1


Método 2

Acudiendo a la idea de que cada número se obtiene sumando los dos superiores.

Utilizamos dos vectores A(n) y B(n).
El vector A contiene una fila del triángulo, inicialmente únicamente contiene el vértice A[1]=1.
Antes de pasar a calcular la fila siguiente copiamos el contenido del vector A en el vector B, de esta forma B contiene los valores de la fila anterior a la que vamos a calcular ahora.
La nueva fila quedará calculada en el vector A. Cada elemento de este nuevo vector A se obtiene sumando los elementos del vector anterior, que es B. Si queremos calcular la posición j del vector B usaremos las posiciones j-1 y j del vector A y las sumaremos, así:

B[j]=A[j-1]+A[j]

De esta forma, la segunda fila será:

B[1]=A[0]+A[1]=0+1=1
B[2]=A[1]+A[2]=1+0=1

La tercera fila será:

B[1]=A[0]+A[1]=0+1=1
B[2]=A[1]+A[2]=1+1=2
B[3]=A[2]+A[3]=1+0=1


La cuarta fila será:

B[1]=A[0]+A[1]=0+1=1
B[2]=A[1]+A[2]=1+2=3
B[3]=A[2]+A[3]=2+1=3
B[4]=A[3]+A[4]=1+0=1

La quinta fila será:

B[1]=A[0]+A[1]=0+1=1
B[2]=A[1]+A[2]=1+3=4
B[3]=A[2]+A[3]=3+3=6
B[4]=A[3]+A[4]=3+1=4
B[5]=A[4]+A[5]=1+0=1

En cada cambio de fila lo que hacemos es almacenar en el vector A los valores que tiene el vector B. De esta forma, al saltar a la fila siguiente almacenaremos los valores de la fila precedente en A, usándose ahora B para calcular los valores de la nueva fila.

Esta forma de trabajar tiene el inconveniente de que usamos el valor A[0] al que no hemos asignado previamente ningún valor y al usarle en la suma, el código nos dará NaN ya que A[0] está undefined.

Para que esto funcione A[0] debe ser cero. Y no solo sucede con A[0], sino con todos los valores extremos de la fila anterior que deseamos sumar y cuyo valor debería ser cero. Por este motivo, lo que hacemos previamente es rellenar con ceros todo el vector A, usando el siguiente código.

for(var k=0;k<=n;k++){  
   A[k]=0;  
 } e

Veamos cómo queda el procedimiento empleado. El archivo index.html es el mismo que en el método 1, y el archivo index.js es el siguiente.

index.js

 var n=20; //número de filas  
 var texto='';  
 //creamos las matrices A(n) y B(n)  
 var A=new Array(n);   //vector antiguo, es el previo  
 var B=new Array(n);   //vector nuevo  
 //convertimos en cero todos los elementos del vector A(n)  
 for(var k=0;k<=n;k++){  
  A[k]=0;  
 }   
 //alimentamos la matriz  
 A[1]=1; //El primer 1 del vértice del triángulo  
 texto=A[1]+'<br>';      //imprimimos el vértice  
 for(var i=2;i<=n;i++){    //i nos da la fila  
  for(var j=1;j<=i;j++){   //j nos da la columna  
   B[j]=A[j-1]+A[j];    //los elementos de B se forman sumando 2 elementos de A  
   texto+=B[j]+" ";     //imprimimos un elemento  
  }   
  for(j=1;j<=i;j++){  
   A[j]=B[j];        //el vector B se convierte en antiguo  
  }  
 texto+= "<br>";      //salto para una nueva fila  
 }
 document.getElementById("resultado").innerHTML = texto;

Método 3.1

Vamos a generar una tabla en HTML generada desde código Java Script que contenga nuestro triángulo de Pascal. Vamos a utilizar dos formas de generar la tabla uno será el método 3.1 y el otro será el método 3.2.

Tanto el método 3.1 como el 3.2 general la matriz A que contiene el triángulo de Pascal usando los números combinatorios que se usaron en el método 1. Una vez conseguida la matriz A lo que haremos es entregársela a la función de Java Script que la organiza en forma de tabla, creando ésta de forma automática en HTML. El resultado será un triángulo de Pascal más estructurado visualmente, ya que se pueden apreciar que los números están incluidos en las columnas de una tabla.

Nos hemos basado en la información contenida en el siguiente enlace de Stack Overflow.

https://stackoverflow.com/questions/15164655/generate-html-table-from-2d-javascript-array


En el método 3.1 la tabla se genera con appendChild.



Observe que en el códgio HTML anterior únicamente se llama al script y que no existe ningún elemento más en el body. Por el contrario en el método 3.2 el HTML ha de contener un elemento que es el que contiene la tabla entera.

Método 3.2

Este método genera automáticamente la tabla HTML usando código Java Script usando una construcción más elemental ya que vamos a ir metiendo las etiquetas del código HTML que definen la tabla en una variable string y luego se la vamos a pasar al código HTML para que genere la tabla. Le pasaremos etiquetas como <table> <td> <tr> ente otras.



Generamos 20 filas.


1
11
121
1331
14641
15101051
1615201561
172135352171
18285670562881
193684126126843691
1104512021025221012045101
1115516533046246233016555111
1126622049579292479249522066121
11378286715128717161716128771528678131
11491364100120023003343230032002100136491141
11510545513653003500564356435500530031365455105151
116120560182043688008114401287011440800843681820560120161
1171366802380618812376194482431024310194481237661882380680136171
118153816306085681856431824437584862043758318241856485683060816153181
1191719693876116282713250388755829237892378755825038827132116283876969171191

1 comentario:

  1. Hola tu artuculo me fue util, pero no entiendo porque usas el Math.round, yo no lo uso y aun asi obtengo el mismo resultado

    ResponderEliminar