Triángulo de Pascal

Consideremos el siguiente triángulo de Pascal:

1
1 1
1 2 1
1 3 3 1
4 6 4 1

Los elementos pueden generarse bien directamente mediante números combinatorios, siendo (i j) el elemento j-ésimo de la fila i-ésima (para 0>=j<=i).

Cada elemento puede generarse sumando los dos elementos situados sobre él:

1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Y sabiendo ésto, tenemos que hallar un algoritmo que localice los números impares de un Triángulo de Pascal.

Solución

Una de las posibles soluciones para este algoritmo es la de tabular los números combinatorios. Esto en Java se haría así (veamos el método línea por línea, para entenderlo mejor):

public ArrayList<Long> hallaImparesPascal(int filas, int columnas){
long[][] tablaCombinatorios = new long[filas+1][columnas+1];

}

Ahora, la fila superior, la número 0, se rellena fácilmente de la siguiente manera:

for(int j=0;j<=columnas;j++){
tablaCombinatorios[0][j];
}

Y las siguientes se completan así:

for(int i=1;i<=filas;i++){
tablaCombinatorios[i][0] = 1;
for(int j=1;j<=columnas;j++){
tablaCombinatorios[i][j]=tablaCombinatorios[i][j-1]+tablaCombinatorios[i-1][j];

}
}

Y para comprobar cuales son impares, debemos crear otro array para almacenarlos, y luego recorrer la matriz que acabamos de crear, y hacer las comprobaciones:

ArrayList<Long> pascalImpares = new ArrayList<Long>();

for (int i = 0; i <= filas; i++) {
for (int j = 0; j <= columnas; j++) {
if (tablaCombinatorios[i][j] % 2 != 0) {
pascalImpares.add(tablaCombinatorios[i][j]);
}
}
}

return pascalImpares;

Y el método completo sería:

public ArrayList<Long> hallaImparesPascal(int filas, int columnas) {
long[][] tablaCombinatorios = new long[filas + 1][columnas + 1];

for (int j = 0; j <= columnas; j++) {
tablaCombinatorios[0][j] = 1;
}

for (int i = 1; i <= filas; i++) {
tablaCombinatorios[i][0] = 1;
for (int j = 1; j <= columnas; j++) {
tablaCombinatorios[i][j] = tablaCombinatorios[i][j – 1] + tablaCombinatorios[i – 1][j];

}
}

ArrayList<Long> pascalImpares = new ArrayList<Long>();

for (int i = 0; i <= filas; i++) {
for (int j = 0; j <= columnas; j++) {
if (tablaCombinatorios[i][j] % 2 != 0) {
pascalImpares.add(tablaCombinatorios[i][j]);
}
}
}

return pascalImpares;
}

 No olvides, que es muy recomendable realizar las excepciones y comprobaciones.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s