Até é útil, pois no próprio algorítimo citado, se usa fatoração internamente.
Boom Shankar 8)
Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf
O Tiago Peczenyj tinha postado uma vez o livro do Tao Pang, nesse tópico http://www.guj.com.br/posts/list/69379.java:
“An Introduction to Computational Physics, 2nd Edition”
Exercícios do livro:
http://www.physics.unlv.edu/~pang/cp2_j.html
Ajuda a validar seus algoritmos de cálculo numérico… 
[quote=mfjeng]Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf
[/quote]
É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.
Sim. Mas a partir daí…
[quote=sergiotaborda][quote=mfjeng]Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf
[/quote]
É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.[/quote]
Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter
[quote=cassio][quote=sergiotaborda][quote=mfjeng]Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf
[/quote]
É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.[/quote]
Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)[/quote]
Se não fizessem isso não teriam trabalho. Muito poucos conhecem OO, para começo de conversa.
[quote=sergiotaborda][quote=cassio][quote=sergiotaborda][quote=mfjeng]Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf
[/quote]
É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.[/quote]
Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)[/quote]
Se não fizessem isso não teriam trabalho. Muito poucos conhecem OO, para começo de conversa.[/quote]
Infelizmente isso é um fato. E vários dos que conhecem não usam, pelos motivos (na opinião deles) que eu já citei.
hehe,
legal esse link do livro do Tao, vou incluir em meus favoritos…
segue uma classe utilitária para Matrizes, eu utilizo em uma disciplina de Estrutura de Dados:
[code]public class MatrizUtils {
public static String toText(Integer[][] m) {
StringBuilder sb = new StringBuilder();
int linhas = m.length;
for(int i=0; i<linhas ; i++ ) {
int colunas = m[i].length;
sb.append("[ ");
for(int j=0; j<colunas; j++) {
if( j==0 ) {
sb.append( m[i][j] );
} else {
sb.append( ", "+m[i][j] );
}
}
sb.append(" ]\n");
}
return sb.toString();
}
/**
* A transposta de uma Matriz A<sub>mxn</sub> é uma matriz A<SUP>t</SUP><SUB>nxm</SUB>
* onde cada elemento de A<SUP>t</SUP><SUB>ij</SUB> = A<SUB>ji</SUB>
*
* @param m - matriz a ser calculada a transposta
* @return matriz transposta
*/
public static Integer[][] transposta(Integer[][] m) {
int linhas = m.length;
int colunas = m[0].length;
Integer[][] t = new Integer[ colunas ][ linhas ];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
t[j][i] = m[i][j];
}
}
return t;
}
/**
* matrizIgual - verifica a igualdade de duas matriz. Duas matrizes são ditas iguais
* quando todos os elementos A<sub>ij</sub> forem iguais aos elementos B<sub>ij</sub>.
*
* @param A - primeira matriz a ser comparada
* @param B - segunda matriz a ser comparada
* @return true se todos os elementos de A<sub>ij</sub> forem iguais aos elementos de B<sub>ij</sub>
*/
public static boolean matrizIgual(Integer[][] A, Integer[][] B) {
int linhasA = A.length;
int linhasB = B.length;
int colunasA = A[0].length;
int colunasB = B[0].length;
if( linhasA != linhasB || colunasA != colunasB )
return false;
for(int i=0; i<linhasA ; i++ ) {
for(int j=0; j<colunasA; j++) {
if( A[i][j] != B[i][j] ) {
return false;
}
}
}
return true;
}
/**
* Matriz Zero é uma matriz em que todos os elementos possuem o valor 0
*
* @param linhas - número de linhas da nova matriz
* @param colunas - número de colunas da nova matriz
* @return matrizZero - matriz com todos os elementos com valor 0.
*/
public static Integer[][] matrizZero(int linhas, int colunas) {
Integer[][] m = new Integer[linhas][colunas];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
m[i][j] = 0;
}
}
return m;
}
/**
* matrizDiagonal é a matriz em que todos os elementos a<sub>ij</sub>=0 para os elementos de índices i!=j.
* @param mat que será extraida a matriz diagonal
* @return matrizDiagonal
*/
public static Integer[][] matrizDiagonal(Integer[][] mat) {
int linhas = mat.length;
int colunas = mat[0].length;
Integer[][] m = new Integer[linhas][colunas];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
if( i != j ) {
m[i][j] = 0;
} else {
m[i][j] = mat[i][j];
}
}
}
return m;
}
/**
* matrizIdentidade é a matriz em que os elementos da diagonal principal tem o
* valor 1 e os elementos que não fazem parte da matriz diagonal tem valor 0.
* @param linhas - número de linhas da matriz Identidade
* @param colunas - número de colunas da matriz Identidade
* @return matriz identidade
*/
public static Integer[][] matrizIdentidade(int linhas, int colunas) {
Integer[][] m = new Integer[linhas][colunas];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
if( i != j ) {
m[i][j] = 0;
} else {
m[i][j] = 1;
}
}
}
return m;
}
/**
* Cria uma matriz identidade nas mesmas dimensões da mat informada.
* @param mat matriz em que será copiado as dimensões
* @return matriz identidade
*/
public static Integer[][] matrizIdentidade(Integer[][] mat) {
int linhas = mat.length;
int colunas = mat[0].length;
Integer[][] ret = matrizIdentidade(linhas,colunas);
return ret;
}
/**
* MatrizTriangularSuperior é a matriz em que os elementos i<j são zero.
* @param mat
* @return
*/
public static Integer[][] matrizTriangularSuperior(Integer[][] mat) {
int linhas = mat.length;
int colunas = mat[0].length;
Integer[][] ret = new Integer[linhas][colunas];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
if( i>j ) {
ret[i][j] = 0;
} else {
ret[i][j] = mat[i][j];
}
}
}
return ret;
}
/**
* MatrizTriangularInferior é a matriz em que os elementos i>j são zero.
* @param mat
* @return
*/
public static Integer[][] matrizTriangularInferior(Integer[][] mat) {
int linhas = mat.length;
int colunas = mat[0].length;
Integer[][] ret = new Integer[linhas][colunas];
for(int i=0; i<linhas ; i++ ) {
for(int j=0; j<colunas; j++) {
if( i<j ) {
ret[i][j] = 0;
} else {
ret[i][j] = mat[i][j];
}
}
}
return ret;
}
/**
* A matriz é chamada de simetrica quando A = A<sup>t</sup>.
*
* @param A
* @return
*/
public static boolean matrizSimetrica(Integer[][] A) {
Integer[][] At = transposta(A);
return matrizIgual(A, At);
}
/**
* A multiplicação de duas matrizes A e B, que são compatíveis no sentido que o
* número de colunas de A é igual o número de linhas B, é definida por:
* Se A=(a<sub>ij</sub>) é uma matriz m x n e B=(b<sub>jk</sub>) é uma matriz n x p,
* então seu produto de matrizes C=AB é a matriz mxp C=(cik), onde:
* c<sub>ik</sub>=somatório(j=1,n)a<sub>ij</sub>b<sub>jk</sub>
*
* @param A primeira matriz, nas dimensões m x n.
* @param B segunda matriz, nas dimensões n x p.
*
* @return C - a matriz contendo o produto de A por B
*/
public static Integer[][] produto(Integer[][] A, Integer[][] B) {
int m = A.length;
int n = A[0].length;
int n2 = B.length;
int p = B[0].length;
// verifica a compatibilidade
if( n != n2 ) {
throw new RuntimeException("Matriz incompátiveis para serem multiplicadas.");
}
Integer[][] C = new Integer[m][p];
for(int i=0 ; i<m ; i++) {
for(int j=0 ; j<p ; j++) {
C[i][j] = 0;
for(int k=0 ; k<n ; k++) {
C[i][j] = A[i][k] * B[k][j];
}
}
}
return C;
}
/**
* verifica se uma matriz é quadrada. Diz-se matriz quadrada para as matrizes em que
* o número de linhas é igual o número de colunas.
*
* @param A
* @return true se matriz for quadrada.
*/
public static boolean matrizQuadrada(Integer[][] A) {
int m = A.length;
int n = A[0].length;
return m == n;
}
/**
* Retorna o determinante, utilizando a decomposição LU.
*
* técnica descrita em Algoritmos de Cormen, Leiserson, Rivest e Stein.
* @param A matriz a ser calculado o determinante
* @return determinante da matriz informada.
*/
public static Integer determinante(Integer[][] A) {
int linhas = A.length;
int colunas = A[0].length;
if( linhas != colunas ) {
throw new RuntimeException("Não é possível calcular o determinante de matriz não quadrada.");
}
int J = 1;
int[] permutacoes = new int[linhas];
for(int i=0 ; i<linhas ; i++) {
permutacoes[i] = i;
}
// método de decomposição LU
int[][] lu = new int[linhas][colunas];
for(int col=0 ; col<colunas ; col++) {
int soma = 0;
// triangulo superior (U)
for(int lin=0 ; lin<col ; lin++) {
soma = lu[lin][col];
for(int i=0 ; i<lin ; i++) {
soma -= lu[lin][i] * lu[i][col];
}
lu[lin][col] = soma;
}
// triangulo inferior (L)
int max = col; // permutation row
int maior = 0;
for (int lin=col; lin<linhas; lin++) {
soma = lu[lin][col];
for (int i=0; i<col; i++) {
soma -= lu[lin][i] * lu[i][col];
}
lu[lin][col] = soma;
if (Math.abs(soma) > maior) {
maior = Math.abs(soma);
max = lin;
}
}
if( Math.abs(lu[max][col]) < 10E-12) {
lu = null;
return 0; // matriz singular possui determinante igual a 0
}
if (max != col) {
int tmp = 0;
for(int i = 0; i<colunas; i++) {
tmp = lu[max][i];
lu[max][i] = lu[col][i];
lu[col][i] = tmp;
}
int temp = permutacoes[max];
permutacoes[max] = permutacoes[col];
permutacoes[col] = temp;
J = -J;
}
for (int lin = col + 1; lin < linhas; lin++) {
lu[lin][col] /= lu[col][col];
}
}
int determinante = J;
for(int i=0; i<linhas; i++) {
determinante *= lu[i][i];
}
return determinante;
}
}[/code]
E parabéns ao Ironlynx pela iniciativa, as coisas estavam realmente calmas por aqui…
fw
[quote=cassio]
Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)[/quote]
Para muita coisa OO é simplesmente desnecessária ou cria um overhead indesejado. Tratamento de imagens, por exemplo, é uma área que Java e OO simplesmente não ajudam. Você quer que seu código seja o mais eficiente possível e para isso é necessário estar muito mais próximo do hardware do que é permitido com Java.
Dou como exemplo implementar os vários algoritmos de composição Porter-Duff, por mais que se tente, a versão java vai ser muito mais lenta que uma feita em C sem muita preocupação com performance.
Olá
E que tal se a forma recursiva implementasse uma uma forma simples da chamada “Tail Recursion”?
Não sei se todos aqui sabem, mas o Scala é simplesmente uma espécie de front end para o Java. O compilador Scala gera bytecode Java. Mas a linguagem é muito mais poderosa do que o Java e inclui um monte de facilidades a mais para o programador. Uma das facilidades é que o compilador Scala otimiza a recursão quando a última instrução chama a função novamente. Ele percebe isto e simplesmente volta para a instrução inicial sem precisar carregar nada na stack.
Vejam como ficaria o fatorial em Scala:
def fatorial(x: BigInt): BigInt =
if (x == 0) 1 else x * fatorial(x - 1)
[]s
Luca
[quote=Luca]Olá
E que tal se a forma recursiva implementasse uma uma forma simples da chamada “Tail Recursion”?
Não sei se todos aqui sabem, mas o Scala é simplesmente uma espécie de front end para o Java. O compilador Scala gera bytecode Java. Mas a linguagem é muito mais poderosa do que o Java e inclui um monte de facilidades a mais para o programador. Uma das facilidades é que o compilador Scala otimiza a recursão quando a última instrução chama a função novamente. Ele percebe isto e simplesmente volta para a instrução inicial sem precisar carregar nada na stack.
Vejam como ficaria o fatorial em Scala:
def fatorial(x: BigInt): BigInt =
if (x == 0) 1 else x * fatorial(x - 1)
[]s
Luca[/quote]
Luca, desculpa ser chato, mas teu exemplo não é tail recursive. A última instrução é “x * ___” e não uma chamada a outra função. Uma implementação de fatorial que é tail recursive fica assim:
def fatorial(x: BigInt): BigInt =
fatorial (1, x)
def fatorial(cur : BigInt, x: BigInt) : BigInt =
if (x == 0) cur else fatorial(cur * x, x - 1)
Agora um desafio, como implementar fibonacci de maneira tail recursive e que não tenha performance quadrática.
Olá
Certo, na verdade eu dei uma forçada de barra. O exemplo que ia copiar e colar do livro de Scala era este que realmente é tail recursive para o Scala
def approximate(guess: Domain) : Domain =
if (isGoodEnough(guess)) guess
else approximate(improve(guess))
Mas como o papo era sobre fatorial, forcei a barra para mostrar que o Scala tem muita coisa legal.
[]s
Luca (que hoje instalou o yaws para tentar usar o yaws com o rails através do fuzed, alguém já fez isto por aqui?)
Legal - se você, em Scala, usar “tail call” (não é exatamente como o Luca fez, mas um pouco mais complicado) o Scala remove a recursão na hora de gerar os bytecodes.
package example;
import scala.collection.mutable.ListBuffer
object Factorial {
// Implementando o método "List.range" para BigInt.
def range (start: BigInt, end: BigInt): List[BigInt] = {
val b = new ListBuffer[BigInt]
var i = start
while (i < end) {
b += i
i += 1
}
b.toList
}
// Fatorial sem recursão
// A inferência de tipos indica que este método poderia
// ser declarado como "def fact1 (n : BigInt) : BigInt"
def fact1 (n : BigInt) = {
range(1,n + 1).reduceLeft[BigInt] {_*_}
}
// Fatorial sem "tail call"
// Note que como o Scala não consegue inferir os tipos,
// precisamos declará-los explicitamente.
def fact2 (n : Int) : BigInt = {
n match {
case 0 => 1
case 1 => 1
case _ => BigInt(n) * fact2 (n - 1)
}
}
// Fatorial com "tail call"
// Para usar "tail call" devemos usar um acumulador.
// Usando "tail call", o Scala compila isto para um código não-recursivo
// algo parecido com:
/*
public scala.BigInt factN(int, scala.BigInt);
Code:
0: aload_0
1: astore_3
2: iload_1
3: istore 4
5: iload 4
7: tableswitch{ //0 to 1
0: 47;
1: 51;
default: 28 }
28: iload_1
29: iconst_1
30: isub
31: getstatic #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
34: iload_1
35: invokevirtual #63; //Method scala/BigInt$.apply:(I)Lscala/BigInt;
38: aload_2
39: invokevirtual #68; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
42: astore_2
43: istore_1
44: goto 2
47: aload_2
48: goto 52
51: aload_2
52: areturn
*/
def fact3 (n : Int) : BigInt = {
// Note a função interna...
def factN (n: Int, acc: BigInt) : BigInt = {
n match {
case 0 => acc
case 1 => acc
case _ => factN (n - 1, BigInt(n) * acc)
}
}
factN (n, 1)
}
def main(args : Array[String]) : Unit = {
Console.println (fact1 (10))
Console.println (fact2 (10))
Console.println (fact3 (10))
}
}o Post me fez fuçar código velho. Alguém uns posts atrás calculou o numero de combinações, esse algoritmo calculas As combinações propriamente ditas.
T+
/**
* Construtor de FullKNSubset. C(n,p)
* @param n Numero do conjunto.
* @param p Numero das partes.
*/
public FullKNSubset(int n, int p) {
this.n = n;
this.p = p;
x = new int[p];
y = new int[p+1];
}
private int sum(int k, int j, int z) {
for(i=0;i <= j;i++)
z += y[i];
return z+k;
}
private void combiner(int i) {
for(x[i]=sum(i,i,0);x[i]<=n-(p-i);x[i]++)
if (i != p-1)
combiner(i+1);
else
show();
y[i+1]=0;
y[i]++;
}
/**
* Invoca o metodo de combinatoria.
*/
public void combinatoriaAlgorithm() {
combiner(0);
}
// Coloca o vetor de combinacao em uma string.
private void show() {
for(i=0; i < p;i++)
System.out.print(x[i]+" ");
System.out.println();
} public static boolean isPar( int num )
{
return ( num & 1 ) == 0;
}
public static boolean isPrimo( int x )
{
for( int i = 2; i < x; i++ )
{
if( x % i == 0 )
{
return false;
}
}
return true;
}
Há algum outro método melhor que esse para números primos?
[code] public static String intTo32bitBinary( int num )
{
int comparer = 1<<31;
String resultValue = “”;
while( !( comparer == 0 ) )
{
resultValue += ( num&comparer )==0 ? "0" : "1";
comparer >>>= 1;
}
return resultValue;
}[/code][code]MathUtils extends MakerMath {
}[/code]
Ganhei.
[quote=Carnevalli] public static boolean isPrimo( int x )
{
for( int i = 2; i < x; i++ )
{
if( x % i == 0 )
{
return false;
}
}
return true;
}
Há algum outro método melhor que esse para números primos?[/quote]
Eu diria que existem alguns mais eficientes em certos casos:
T+
[quote=Carnevalli] public static boolean isPrimo( int x )
{
for( int i = 2; i < x; i++ )
{
if( x % i == 0 )
{
return false;
}
}
return true;
}
Há algum outro método melhor que esse para números primos?[/quote]
Não é necessário testar de 2 até x, basta de 2 até o piso da raiz de x.