Isso aqui tá meio parado, vamos agitar um pouco.
Seguinte, vou criar uma classe de funções matemáticas, cada um vai incrementando com algo (converte de Hex para decimal,Fibonacci…)Começando com algo simples:
[code]
public class MathUtils{
public long fatorial(long n){
if (n==0)
return 1;
else
return n*fatorial(n-1);
}
}[/code]
Vamos lá pessoal! 
Pô, sinto a "animação" de vcs como a do Tibet torcendo pela China nas Olimpíadas… :lol:
Aumentando… de decimal para binario, de binario para decimal:
[code]
public class MathUtils{
public long fatorial(long n){
if (n==0)
return 1;
else
return n*fatorial(n-1);
}
public String decimalToBinary(int d){
String result="";
while(d>0){
result =(d&1)+result;
d>>=1;
}
return result;
}
public int binaryToDecimal(String b){
int i, result=0;
for(i=0;i<b.length();i++){
result><<=1;
if(b.charAt(i)==‘1’) result++;
}
return result;
}
}[/code]
Eh meio dificil imaginar alguem pulando e dando gritinhos de felicidade ao ver uma classe chamada MathUtils…
so pra animar… :lol:
public static int soma(int x, int y) {
return x + y;
}
public static int subtraiint x, int y) {
return x - y;
}
public static void naoFazPorraNenhuma(String porraNenhuma) {
}
Prefiro alterar o fatorial() para isso:
public long fatorial(long n) {
if (n < 0)
throw new IllegalArgumentException("deu chabu");
long[] fat = new long[n];
fat[0] = 1;
for (long i = 1; i < fat.length; i++)
fat[i] = i * fat[i - 1];
return fat[n];
}
[quote=Schuenemann]Prefiro alterar o fatorial() para isso:
public long fatorial(long n) {
if (n < 0)
throw new IllegalArgumentException("deu chabu");
long[] fat = new long[n];
fat[0] = 1;
for (long i = 1; i < fat.length; i++)
fat[i] = i * fat[i - 1];
return fat[n];
}[/quote]
A verificação do n é uma boa
[quote=sergiotaborda][quote=Schuenemann]Prefiro alterar o fatorial() para isso:
public long fatorial(long n) {
if (n < 0)
throw new IllegalArgumentException("deu chabu");
long[] fat = new long[n];
fat[0] = 1;
for (long i = 1; i < fat.length; i++)
fat[i] = i * fat[i - 1];
return fat[n];
}[/quote]
A verificação do n é uma boa [/quote]
também não vejo vantagens em fazer deste modo. até o código fica mais poluído.
Já que é para rodar em uma JVM, vamos lá:
package example;
object Factorial {
// Calcula o fatorial de 10
def main(args : Array[String]) : Unit = {
Console.println ((1 to 10).reduceRight[Int] {_ * _})
}
}Calculo do numero de combinações calculando apenas o menor factorial necessário
public int combinations (int n , int k ){
if (n <= 0 || k < 0 || k > n ){
throw new IllegalArgumentException();
}
if (k==0 || k == n){
return 1;
}
final int max = Math.max(k, n-k);
final int min = n - max;
int produto=1;
for (int i = n ; n > max; i--){
produto *= i;
}
return produto / factorial(min);
}
melhor como:
public class MathUtils{
public long fatorial(long n){
retunr n<=1 ? 1 : n*fatorial(n-1);
}
}A forma recursiva é apenas ruim porque polui o stack. Tlv melhor seja assim
public class MathUtils{
public long fatorial(long n){
if (n<0){
throw new IlegalArgumentException();
}
F f = new F(n);
while(!f.isFinished()){
f.factorize();
}
return f.value;
}
private class F {
long n;
long value=1;
F(long n){
this.n =n;
}
boolean isFinished(){
return n<=1;
}
void factorize(){
value *= n;
n--;
}
}
}Hummm, prefiro a primeira opção, a segunda esta apenas mais difícil de ler.
[quote=sergiotaborda]
[code]
public class MathUtils{
public long fatorial(long n){
if (n<0){
throw new IlegalArgumentException();
}
F f = new F(n);
while(!f.isFinished()){
f.factorize();
}
return f.value;
}
private class F {
long n;
long value=1;
F(long n){
this.n =n;
}
boolean isFinished(){
return n<=1;
}
void factorize(){
value *= n;
n–;
}
}
}
[/code][/quote]
De 8 linhas de código passamos a 30, e com uma private class.
Oba! A idéia agora passou a ser complicar ao máximo o código.
Como fatorial cresce muito rapidamente, seria interessante usar BigInteger, não?
Eh meio dificil imaginar alguem pulando e dando gritinhos de felicidade ao ver uma classe chamada MathUtils…[/quote]
Só se alguem implementar ao menos uma Transformada de Fourier. Se não fica difícil alguem dar uns gritinho de euforia mesmo.
[quote=xandroalmeida]
De 8 linhas de código passamos a 30, e com uma private class.
Oba! A idéia agora passou a ser complicar ao máximo o código. [/quote]
Eficiencia do Código não se mede em linhas de codigo :twisted: . A ideia era ser mais eficiente ao não pesar no stack. A ideia era aumentar a eficiencia.
A ideia do BigInteger seria interessante tb se houver interesse em aumentar o contra-dominio da função.
Para implementar FFT precisa de numeros complexos. Implemente numeros complexos primeiro :lol:
(nota: tudo isto existe no commons-math , e suponho que com implementações inteligentes e eficientes, estamos só exercitando)
A idéia é justamente o contrário(hahah), para podermos termos um link de referência para os iniciantes, que vivem perguntando essas coisas…
certamente, algo + ou - do tipo:
public BigInteger fatorial(String s){
BigInteger cont=BigInteger.ONE;
BigInteger resultado=BigInteger.ONE;
BigInteger valor=new BigInteger(s);
while(cont.compareTo(valor)<0){
cont= cont.add(BigInteger.ONE);
resultado=resultado.multiply(cont);
}
return resultado;
}
Mas pode levar um zilhão de anos se o número for muito grande…aí só com algoritmos específicos para otimizar o troço.
Colocando um fibonacci(rec) para aumentarmos a nossa classe:
public static long fibonacci(int n){
if(n<=1) return n;
else return fibonacci(n-1) + fibonacci(n-2);
}
[quote]
(nota: tudo isto existe no commons-math , e suponho que com implementações inteligentes e eficientes, estamos só exercitando) [/quote]
A idéia é essa(Exercício), pq TODO dia tem alguem perguntando sobre fatorial,exponencial…aí taca tudo logo num tópico e quando alguém perguntar, referencia esse, e economiza a banda de criar 123456790 tópicos! :lol:
Hmm… Já que estamos falando em fatorial, deixa eu postar um problema aqui que envolve fatorial (e que até poderíamos colocar na MathUtils, apesar de eu não conhecer nenhuma utilidade para a função que irei apresentar).
A função Z(n) é uma função que recebe um número natural como parâmetro e retorna o número de zeros presentes no final do fatorial desse número. Por exemplo:
Z(5): 5 * 4 * 3 * 2 * 1 = 120. O número de zeros no final de 120 é 1, então Z(5) é igual a 1.
Z(10): 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. O número de zeros no final é 2, então Z(10) é igual a 2.
Outros exemplos: Z(60) = 14, Z(100) = 24, etc. O n pode ser um número muito grande. Posso querer saber Z(1000), por exemplo.
Como resolver esse problema? Obviamente, calcular o fatorial e contar o número de zeros não é viável. A minha solução foi a seguinte: o número de zeros no final vai depender do número de 10 presentes na multiplicação, por exemplo:
Z(5): 5 * 4 * 3 * 2 * 1 => 10 * 4 * 3 * 1 => Um 10, então possui um zero no final.
Z(10): 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 => 10 * 9 * 8 * 7 * 6 * 10 * 4 * 3 * 1 => Dois 10, então possui dois zeros no final.
Mas é possível simplificar isso dizendo que o número de zeros no final é igual ao número de 5s na multiplicação, tendo em vista que o número de 2s que existem na multiplicação é bem maior que o de 5s e esses 2s que sobram não influenciam no número de 10s, pois o 2 precisa estar com o 5 pra produzir um 10.
Exemplo:
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Z(10!) = (2*5 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) = Dois cincos, dois zeros no fim.
30! = 30 * 29 * 28 * 27 * … * 6 * 5 * 4 * 3 * 2 * 1
Z(30!) = 30 * 25 * 20 * 15 * 10 * 5 (descartamos o restante pois precisamos apenas dos múltiplos de 5)
Z(30!) = 65 * 55 * 45 * 35 * 2*5 * 5 = Sete cincos, implica em 7 zeros no final.
Pra contar o número de 5s, eu fiz essa função:
public static int z(int n) {
int cincos = 0; // o número de cincos
int aux;
while (n > 0) {
aux = n;
while (aux > 0) {
if (aux%5 == 0)
cincos++;
else
break;
aux /= 5;
}
n--;
}
return cincos;
} Esse código está retornando o resultado certo, mas ele tem complexidade O(n log n) e o local onde eu vi o problema dizia que dava pra fazer com O(log n). Alguém tem alguma idéia de como fazer isso?
[quote=jingle][quote=sergiotaborda][quote=Schuenemann]Prefiro alterar o fatorial() para isso:
public long fatorial(long n) {
if (n < 0)
throw new IllegalArgumentException("deu chabu");
long[] fat = new long[n];
fat[0] = 1;
for (long i = 1; i < fat.length; i++)
fat[i] = i * fat[i - 1];
return fat[n];
}[/quote]
A verificação do n é uma boa [/quote]
também não vejo vantagens em fazer deste modo. até o código fica mais poluído.[/quote]
Se livrar da recursão é uma vantagem e tanto. Tenta ver até que número consegue calcular na primeira forma. Não sei nem pra que o argumento é um long, acho que não vai nem conseguir extrapolar um byte 
A idéia do array era só organizar melhor, usando o valor como índice do array. Poderia usar um List e gravar os resultados, talvez.
O exemplo de fibonacci recursivo é ainda pior, porque você recalcula várias vezes a mesma coisa. Além de ser recursivo, claro.
David, nesse link tem uma fórmula pra calcular essa quantidade de zeros ( nem me pergunte entendi a fórmula mas não entendi sua origem )
Acho que a complexidade dela é bem menor q n log(n)
iterar é humano, recorrer é divino.
Agora alguém poste uma implementação do block-lanczos, pois fatorial já perdeu a graça e pq não algo útil.