Versão eficiente do Fibonacci recursivo usando programação dinâmica:
public static long fibonacci(int n, long [] cache){
if(cache[n] == -1){
if(n < 2) cache[n] = n;
else cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
}
return cache[n];
}Fibonacci com tail calls e outras coisas (em Scala)
package example
import scala.collection.mutable._
object Fibonacci {
// A definição boba de Fibonacci.
def fibo1 (n : Int) : BigInt = {
n match {
case 0 => 0
case 1 => 1
case _ => fibo1 (n - 1) + fibo1 (n - 2)
}
}
// Tail call
def fibo2 (n : Int) : BigInt = {
def fibo (n: Int, current: BigInt, next: BigInt) : BigInt = {
n match {
case 0 => current
case _ => fibo (n - 1, next, current + next)
}
}
fibo (n, 0, 1)
}
// "Memoizing" simples. Não tem tail calls, mas é útil quando
// é complicado transformar um algoritmo recursivo
// em outro com tail calls. Neste caso, definimos
// um mapa com os valores precalculados.
// (Não sou Scala-man, então esta maneira de "memoizing" é bem ingênua.)
var f = Map.empty[Int,BigInt]
f(0) = BigInt (0)
f(1) = BigInt (1)
def fibo3 (n : Int) : BigInt = {
if (!(f contains n))
f(n) = fibo3(n - 1) + f(n - 2)
f(n)
}
def main(args : Array[String]) : Unit = {
println (fibo1 (20))
println (fibo2 (20))
println (fibo3 (20))
}
}Esses códigos em Scala, e esse tópico aqui: http://guj.com.br/posts/list/86101.java me lembraram do tempo em que eu mexia com Haskell( http://osereojava.blogspot.com/2006/02/um-pouco-de-haskellrepost.html )… bateu um saudosismo. :-o
Alguém tinha falado de “fatoriaisrápidas”, parece que um dos melhores algoritmos é o Prime Swing.Veja aqui(códigos em java e C++):
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
Aliás, essa página é bacana ( http://www.luschny.de/math/ ) pena que a parte em Alemão, eu não entendo bulhufas… 
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.
[/quote]
Esse algoritmo apenas combina numeros. Existe algum algoritmo para , dado um conjunto populado com objetos criar as combinações ? algo como
combinacao ({"A","B","C"} , 2 )
// produz
AB
AC
BC
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.
[/quote]
Esse algoritmo apenas combina numeros. Existe algum algoritmo para , dado um conjunto populado com objetos criar as combinações ? algo como
combinacao ({"A","B","C"} , 2 )
// produz
AB
AC
BC
[/quote]
ué, mas aí basta voce usar os números gerados no algoritmo como índices.
int[] letras = {'A', 'B', 'C'}
int[] indices = {0,1,2}e aplique o algoritmo em indice[] e evoque como indice[] em letras
letras[indices[i]];Com isso voce consegue combinar qualquer coisa enumerável. Tipo:
Object[] objs = { new T1(), new T2(), new T3() ;
objs[indices[i]];T+
Ok, mas eu me referia a algoritmos que não calculem primeiro os indices mas que usem estruturas como Set ou List.
Repare que, usando indices, o algoritmo é cego aos elementos. Se eu passar {A,A,A} o resultado seria AA, AA, AA.
mas isso é errado. Na realidade só tenho um elemento no conjunto. Sim, sim… poderia filtrar usando set ou alguma coisa… eu so achei que poderia existir um algoritmo famoso (desses que até têm nome) que fosse mais inteligente e já tomasse contas dessas coisas sem ter que “filtrar na mão”.
Vixi isso tudo é vontade de programar? perai que eu vou mandar uns casos de usos pra vocês, vou aproveitar, programação na faixa. 
Acho que você está confundindo as estruturas. Se você ter um algoritmo que leve em consideração multiplicidade ((A,A,A) tem multiplicidade 3), você não está falando de combinações, e sim falando de String Theory, ou se a multiplicidade dos elementos tiverem uma estrutura bem definida, pode se enquadrar na família das partições ou composições. Numa estrutura de conjuntos, no caso de combinações, a mutiplicidade é ignorada
O que tem de famoso nisso é mudar a estrutura 
se voce tem (A,A,A), voce pode trata-lo como a estrutura que lhe convier. A mais abrangente nesse caso seria o objeto combinatorial String, e para (A, A, A), ele teria o alfabeto com um símbolo e dimensão 3, como o número de possibilidades de Strings é m^n, com m = numero de símbolos e n a dimensao da String, ficaria, nesse caso, 1^3 = 1. Em outro termos, voce só tem arranjo (A,A,A) dentro dessa definição.
Eu explico mais dessas coisas e sobre outras familias de estruturas aqui
T+
Esqueci de mencionar, mas se voce acha que tem alguma estrutura mais genérica que consiga transformar uma estrutura em outra, existe sim, (definida por um grafo, sendo mais exato), ela é descrita no capitulo 13 deste livro…mais ainda assim, ela tem uma fase de “encoding” e “decoding” de uma estrutura para outra.
T+
[quote=Proteu Alcebidiano][quote=sergiotaborda]
Ok, mas eu me referia a algoritmos que não calculem primeiro os indices mas que usem estruturas como Set ou List.
Repare que, usando indices, o algoritmo é cego aos elementos. Se eu passar {A,A,A} o resultado seria AA, AA, AA.
mas isso é errado.
[/quote]
Acho que você está confundindo as estruturas. Se você ter um algoritmo que leve em consideração multiplicidade ((A,A,A) tem multiplicidade 3), você não está falando de combinações, e sim falando de String Theory,
[/quote]
A não é uma string. É um objeto qualquer. A letra foi so para identificar o objeto sem usar numeros.
{A,A,A} é um conjunto formado por três instancias de A. Contudo, elas são a mesma instancia , logo é equivalente a {A} apenas. Combinações de 1 elemento 3 a 3 não são possiveis. Logo, o algoritmo de combinações teria que levar em conta isso. É só disso que estou a falar.
O n de C(n,k) é o tamanho do conjunto de elementos diferentes. não ?
A String que estou a definir não é exatamente a String tipo de dado, É uma estrutura combinatorial =D
Combinações de 1 elemento 3 a 3 não são possiveis justamente porque a definição de combinação é considerar os elementos de uma dada dimensão como diferentes.
Repetindo o que escrevi lá em cima, se voce tem {A,A,A} isso não é uma estrutura de combinação, é uma estrutura de String (lembre que a String que falo aqui é String do link que te passei ;)). Você não pode efetuar combinações em uma estrutura que não obedece a definição de KN-Subsets (objetos combinados). E como falei também, voce pode, usando a definição do livro que mencionei no post anterio, jogar uma estrutura qualquer (inclusive essa do seu exemplo) no grafo que ele saberá direcionar para a familia combinatorial desejada =)
T+
T+