GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

[RESOLVIDO] Otimizar código do triângulo de Pascal

java
programação
Tags: #<Tag:0x00007f8528667448> #<Tag:0x00007f8528667308>

#1

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?


#2

existe alguns teoremas

por exemplo, a primeira linha tem 1 numero, a linha mil vai ter mil numeros.

sabendo disso, existe um teorema q fala da quantidade de numeros IMPARES numa dada linha

https://www.math.hmc.edu/funfacts/ffiles/30001.4-5.shtml

THEOREM: The number of odd entries in row N of Pascal’s Triangle is 2 raised to the number of 1’s in the binary expansion of N.

Example: Since 83 = 64 + 16 + 2 + 1 has binary expansion (1010011), then row 83 has 24 = 16 odd numbers.

saca so, se vc pegar a linha 83, vc sabe quantos numeros impares vc tem, pra saber os pares vc subtrai. se a linha 83 tem 84 numeros (nesse teorema N começa em 0 e a primeira linha tem 1 elemento) e 16 sao impares, sobra 68 pares, certo?

vc faz um loop de i = 1 ate 1000
converte i pra binario
conta os numeros 1
eleva 2 ate esse numero
subtrai essa quantidade de i+1 (importante)
acumula essa quantidade

simples assim.

pra vc converter um numero para a forma binaria e calcular a quantidade de numeros 1 que isso tem, existem varias formas

por exemplo, vc pega todas as potencias de 2 uteis (1,2,4,8,16,32,64,128,256, 512, o proximo seria 1024 mas vc nao precisa ir tao longe se vc quer mil ) e pra cada um vc faz AND bit a bit com o numero e veja se o resultado eh diferente de zero.

exemplo, numero 5 eh: 00000101 onde temos 4 + 1 = 2 na segunda potencia + 2 na potencia zero

quantos 1 tem?

5 & 1 eh maior q zero? sim
5 & 2 eh maior q zero? nao
5 & 4 eh maior q zero? sim

pra vc visualizar

5 & 1 vc aplica o and para cada bit, como se fosse soma:

  00000101
& 00000001
----------
  00000001

fica como exercicio ao leitor fazer os outros bits.

outra forma eh vc fazer deslocamentos de bit e ver se o ultimo bit eh 1, ou seja ver se o numero eh impar (o modulo por 0 sobra algo)

(5 >> 0) % 2 sobra 1? sim
(5 >> 1) % 2 sobra 1? ano
(5 >> 2) % 2 sobra 1? sim

visualizar

101 >> 0 = 00000101
101 >> 1 = 00000010
101 >> 1 = 00000001

ou seja, se vc faz >> x vc empura x bits pra fora, e preenche o comeco com 0

uma ultima forma seria vc fatorar o numero com potencias de 2. etc, escolha uma forma

mas o importante eh que vc vai fazer K operacoes para ver esses bits por linha. o algoritmo sera O(n)

eu fiz um pequeno exemplo em Go que eh bem semelhante a Java em certos aspectos, de uma olhada

https://play.golang.com/p/oilU-Z8eEyi


#3

Ok, na parte onde você fala sobre a linha do código ser frescura do go, na verdade seria impares = bits?

Se for isso, fiz um teste com seis linhas, onde o resultado deveria ser 6, mas resultou 14. Estou fazendo certo?


#4

Rapaz, tá resolvido. Reli a propriedade que você comentou, e percebi que tinha que elevar 2 na variável bits. Resolvido, e bem mais rápido que a solução que eu tinha! Valeu!


#5

tem certeza? eu so testei contra o seu código usando n=1000, posso ter errado alguma soma

edit: ate a linha 6 retorna 6

https://play.golang.com/p/nR-iEzUuobH