Archive for the ‘java’ Category

Como escrever números por extenso

julho 30, 2009

Precisei escrever uma rotina para escrever números por extenso de até R$ 999.999,99 por extenso. Fiz um programinha em Java e depois converti para VBA, para ser usado no Excel. A rotina não está otimizada e nem muito genérica. Mas se alguém precisar de algo mais genérico (para números maiores), é só pegar o código e estender, está bem simples.

Código em Java:

extenso java

Saída:

extenso saida
Código em VBA:

extenso vba

Como usar no Excel:

extenso vba uso 1

extenso vba uso 2

Anúncios

Como calcular a área de um polígono irregular

dezembro 5, 2008

Recentemente precisei calcular a área de um polígono irregular. Mas como? Fiz uma pesquisa sobre geometria computacional, e uma das formas que encontrei foi em dividir o polígono em vários triângulos e, após isso, calcular a área de cada triângulo. Tudo bem, mas como dividir o polígono em vários triângulos menores? Por exemplo, como dividir automaticamente o polígono da figura 1 em triângulos? Existem algoritmos para isso, para fazer a triangulação de polígonos.

triangulacao

Figura 1 – Um polígono dividido em vários triângulos

Basicamente o algoritmo funciona da seguinte forma. Divide o polígono em vários polígonos monotone* e depois faz a triangulação de cada um desses algoritmos usando um algoritmo para fazer a triangulação.

Essa é uma das formas de se fazer isso. Uma outra forma é baseada na técnica descrita no post “Como calcular computacionalmente o valor de PI“. Nesse caso podemos fazer o seguinte. Desenhamos o polígono em cima de um outro polígono já conhecido, no caso um retângulo. Sabemos como calcular a área do retângulo. Depois disso, começamos a gerar pontos aleatórios dentro do retângulo (o polígono que queremos calcular a área está em cima do retângulo). Para cada ponto, vemos se o ponto caiu dentro do polígono irregular. Se dividirmos a quantidade de pontos que caiu dentro do polígono pela quantidade de pontos gerada, temos a relação entre a área do polígono e a área do retângulo. Como a área do retângulo é conhecida, fica simples calcular a área do polígono, basta fazer uma multiplicação.

No entanto, fica a questão: Como saber se um ponto está dentro do polígono?  Para efeitos práticos para o cálculo da área dessa forma, podemos traçar uma semi-reta paralela ao eixo x em direção a +x. Se essa semi-reta interceptar um número ímpar de arestas, podemos dizer que ele está dentro do polígono – Figura 2.

dentroforaFigura 2 – Ponto dentro e fora do polígono

Agora que sabemos quando um ponto está dentro de um polígono, precisamos saber que essa semi-reta interceptou uma das arestas. Isso pode ser feito da seguinte forma:

Primeiro, calculamos a equação da aresta. Considerando que os vértices da aresta são (x1, y1) e (x2,y2), temos que a equação é:

x = x1 + (y-y1)\frac{(x2-x1)}{(y2-y1)}

Aplicando a coordenada y do ponto nessa equação, temos um valor de x. Se esse valor for maior que o valor da coordenada x do ponto, sabemos então que o ponto está a esquerda da aresta.

Além disso, se verificarmos que a coordenada y está entre min(y1,y2) e max(y1,y2), então sabemos que a semi-reta intercepta a aresta.

Com isso já podemos calcular a área de um polígono irregular.

Para ilustrar, segue um código Java para isso.

Classe Ponto

classe-ponto

Classe Aresta

classe-aresta

Classe Poligono

classe-poligono

Como primeiro teste, desenhei um polígono e gerei vários pontos aleatórios para testar se o método para verificar se está dentro do polígono está funcionando. Os pontos verdes estão fora do polígono e os amarelo dentro. Desenhei pequenos círculos em volta do ponto gerado, para aproveitar uma rotina que já tenho aqui. Podemos ver que a rotina se mostra adequada para o problema.

teste-ponto-esta-dentro-do-poligono

Figura 3 – Teste do método para verificar se pontoe stá dentro do polígono

Resta agora testar se isso funciona para calcular a área. Para isso, vamos criar um quadrado de lado 1 e gerar pontos aleatórios dentro de um quadrado de lado 2 e calcular a relação entre a quantidade de pontos dentro do quadrado e a quantidade de pontos gerada. Esse valor multiplicado pela área do quadrado maior (4), deve dar a área do quadrado, que sabemos que é 1. Na verdade, como esse método não é exato, a área deve ser próxima de 1, e não exatamente 1. Segue trecho de código usado para teste:

teste-calculo-da-area

Uma das saídas desse programa é mostrada na figura abaixo. Note que o valor da área calculado por esse método é muito próximo ao valor real. Na verdade, podemos aumentar a precisão do algoritmo aumentando o número de pontos gerados.

saida-do-programaFigura 4 – Resultado do programa

A Figura 5 mostra uma figura de exemplo para esse teste, com os pontos gerados:

exemplo-de-pontos-gerados

Figura 5 – Exemplo do teste efetuado

* – optei por não fazer a tradução dessa palavra pois não sei como ela é traduzida em geometria computacional.

Problema das 3 portas

novembro 9, 2008

Probabilidade é um assunto interessante. Em um post antigo falamos sobre o problema dos aniversários e vimos que para um grupo de apenas 30 pessoas a probabilidade de termos 2 aniversariantes no mesmo dia é de mais de 70%, o que não é muito o senso comum.

Outro problema interessante de probabilidade é o problema das 3 portas. Um apresentador de um programa de televisão chama para o palco uma pessoa que deve escolher entre 3 portas. Uma dessas portas tem prêmios e as outras 2 não tem nada. Inicialmente a pessoa escolhe uma porta e, em seguida, o apresentador abre uma porta vazia. Como sempre tem 2 portas que não tem nada atrás delas, sempre haverá uma porta para o apresentador abrir. Feito isso ele pergunta se você quer trocar de porta. E agora?

A grande maioria das pessoas nao troca de porta. Talvez por supertição, pois escolheu seu número da sorte. Mas o que é melhor, trocar de porta ou não? Ou tanto faz? Vamos resolver o problema sem fazer contas…..

Obviamente a chance de você acertar a porta na primeira escolha é de 1/3, 33,33%. Vamos verificar então o que acontece se você trocar de porta.

Inicialmente temos 3 portas, P1, P2 e P3. E você escolheu a porta P1. Temos 3 possibilidades:

  • O prêmio está atrás da porta P: Nesse caso o apresentador abre uma das portas P2 ou P3. Se você trocar você estará trocando o prêmio por nada.
  • O prêmio está atrás da porta P2: Nesse caso o apresentador abrirá a porta P3. Se você trocar de porta você estará trocando pela porta P1, ou seja, estará trocando nada pelo prêmio.
  • O prêmio está atrás da porta P3: Nesse caso o apresentador abrirá a porta P2. Se você trocar de porta você estará trocando pela porta P1, ou seja, estará trocando nada pelo prêmio.

Observe que das 3 possibilidades, 2 são vencedoras. Sendo assim, a probabilidade de ganhar o prêmio caso você troque de porta é de 2/3, ou 66,67%, ou seja, o dobro de chance de levar para casa o prêmio.

Bom, para facilitar, vamos ver um pequeno programa em Java que faz uma simulação sobre esse problema e nos mostra o resultado. É mais fácil de acreditar…

problema-3-portas1

Obs.: O código acima foi construído de forma a diminuir seu tamanho para publicação nesse blog, por isso o uso de operadores não muito indicado por alguns livros, como o operador ternário (?:).

Como converter um número em base b para um número no sistema de numeração decimal

setembro 18, 2008

No mundo da computação é muito comum vermos números escritos em sistemas de numeração diferentes do sistema decimal. Atenção especial são dadas para os sistemas de base 2 (binário) e de base 16 (hexadecimal). Mas para muitos de nós o sistema decimal é mais palpável do que qualqer outro. Você sabe como converter qualquer sistema escrito numa base b qualquer para o sistema decimal?

Um número N em uma base b qualquer pode ser escrito da seguinte forma:

N = b_n...b_3b_2b_1b_0

onde b_i é uma letra do alfabeto (dígito) que compõe o sistema de numeração. Para um sistema de numeração binário (base 2), b_i pode ser 0 ou 1. Para um sistema de numeração de base 8 b_i pode ser 0, 1, 2, 3, 4, 5, 6, 7. Para um sistema de numeração de base 16 b_i pode ser 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F e assim por diante.

Para converter o número b_n...b_3b_2b_1b_0 para a base 10 é simples. Basta aplicar a seguinte forma:

D = {b_0}B^{0} + {b_1}B^{1} + {b_2}B^{2} + ....{b_n}B^{n}

onde B é a base do sistema. Para o sistema binário B = 2 e a fórmula se reduz em:

D = {b_0}2^{0} + {b_1}2^{1} + {b_2}2^{2} + ....{b_n}2^{n}

Para ilustrar, o seguinte trecho de código na linguagem Java converte uma string que possui os números em binário para um número em decimal:

Geração de números aleatórios

novembro 23, 2007

A forma mais comum de se obter números pseudorandômicos em um computador digital é usando o seguinte gerador:

{R}_{i} = (A{R}_{i-1}+C) mod M, i = 1, 2, 3, ...

onde {R}_{0} é a semente, ou valor inicial, M o divisor, C uma constante aditiva e A um multiplicador. A notação mod M significa que a aritimética é feita módulo M, ou seja, {R}_{i} é o resto da divisão de A{R}_{i-1}+C por M. A seqüência resultante terá boa propriedades estatísticas e produzirá longas seqüências sem repetição dependendo dos números escolhidos.

Bons valores para M, Asão:

M = {2}^{31}

A = 764261123

{R}_{0} é escolhido como um número ímpar.

A implementação dessa rotina em matlab é

R0=1;
A=764261123;
C=0;
M=2^31;

R=zeros(1000,1);
R(1)=mod(A*R0+C,M);
for i=2:1000
R(i)=mod(A*R(i-1)+C,M);
end

plot(R);

Esse mesmo código, em linguagem Java, é

double[] R = new double[1000];
double A=764261123;
double C=0;
double M=Math.pow(2, 31);

R[0] = 1;
for (int i=1; i<1000; i++)
R[i]=(A*R[i-1]+C) % M;

Cabe ressaltar que esse gerador é um gerador de números pseudorandômicos. Isso significa que, dada as mesmas condições (semente, A, C e M), a mesma seqüência será gerada. Verdadeiros geradores randômicos devem usar eventos realmente randômicos, como por exemplo o ruído de dispositivos eletrônicos ou o sinal captado por um microfone em um ambiente natural.

Fonte: Random Signal Analysis in Engineering Systems, John J. Komo

Como calcular computacionalmente o valor de PI

novembro 15, 2007

Apesar de existirem vários meios de se obter o valor de \pi, talvez a mais simples é a que usa alguns conceitos básicos de estatística. Considere a figura abaixo que mostra um círculo de raio 1 inscrito em um quadrado de lado 2. A área do círculo e a área do quadrado são dadas pelas equações

{A}_{circulo} = \pi{r}^{2} = \pi , r = 1

{A}_{quadrado} = {l}^{2} = 4 , l = 2

 

Circulo inscrito em um quadrado

 

Obviamente, a relação entre {A}_{circulo} e {A}_{quadrado} é

\frac{{A}_{circulo}}{{A}_{quadrado}} = \frac{\pi}{4}

Ou seja, \pi vale

\pi = 4\frac{{A}_{circulo}}{{A}_{quadrado}}

Feito isso, para calcular \pi basta gerar vários pontos aleatórios dentro do quadrado. O valor de \pi será dado pela quantidade de pontos que estão dentro do círculo dividido pela quantidade de pontos que estão dentro do quadrado (quantidade de pontos gerados). Em Matlab, isso pode ser feito com o seguinte código

amostras = 5000000; px = 2 * rand(amostras,1) - 1; py = 2 * rand(amostras,1) - 1; ptosDentroDoCirculo = sum(px.^2 + py.^2 <= 1); estimadorPi = 4 * ptosDentroDoCirculo/amostras

Em Java, este mesmo código pode ser escrito como

int amostras = 5000000;
int pontosDentroDoCirculo = 0;
for (int i = 0; i < amostras; i++) {

double px = 2*Math.random()-1;
double py = 2*Math.random()-1;
if (Math.pow(px,2) + Math.pow(py,2) <= 1) {

pontosDentroDoCirculo++;

}

}
System.out.println("PI: " + 4*(double)pontosDentroDoCirculo/(double)amostras);

Apesar de não ser a forma mais efeciente de se calcular \pi, mas é uma das mais simples de entender.