E aí manos, tudo certo? Tenho uma questão pra resolver aqui sobre o triângulo de Pascal, aquele onde os números são sempre a soma dos números pais, mas os de fora são sempre 1:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Pois bem, preciso escrever um algoritmo que calcule quantos números pares tem nas primeiras mil linhas desse triângulo. Eu já tenho um algoritmo com O(n2), mas queria saber se algum de vocês conhece alguma forma ou propriedade desse triângulo que me permita otimizar esse algoritmo ainda mais:
import java.sql.Date;
import java.text.SimpleDateFormat;
public class TerceiroDesafio {
private static int [][] matriz;
private static int i, j, n;
public static void main(String[] args)
{
long inicio = System.currentTimeMillis();
n = 0; // Numero de pares;
matriz = new int[1000][1000];
for (i = 0; i < 1000; i++) {
for (j = 0; j < 1000; j++) {
matriz[i][j] = 0;
}
}
matriz[0][0] = 1;
matriz[1][0] = 1;
matriz[1][1] = 1;
for (i = 2; i < 1000; i++) {
matriz[i][0] = 1;
matriz[i][i] = 1;
for (j = 1; j < i; j++) {
matriz[i][j] = matriz[i-1][j-1]+matriz[i-1][j];
if ( matriz[i][j] % 2 == 0 ) {
n++;
}
}
}
System.out.println( "Quantidade de números pares = " + n );
long fim = System.currentTimeMillis();
System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));
}
}
Aqui ele está rodando a 0,015 milissegundos, mas meu professor disse que pode ser mais rápido. Alguma ideia?