Olá:
Dando uma olhada neste fórum descobri uma referência ao Project Euler. Nele são propostos uma série de desafios matemáticos para serem resolvidos via programação:
Atualmente existem 253 problemas propostos. Ao se cadastrar você pode colocar a resposta aos desafios e, caso acerte, você pode ver como os outros usuários resolveram.
Divirtam-se
Não é só acertar, é acertar no tempo que eles permitem.
É um dos sites mais usados para estudar para maratona de computação, junto ao UVA (http://uva.onlinejudge.org) e ao SPOJ (http://br.spoj.pl).
Até!
[quote=maquiavelbona]Não é só acertar, é acertar no tempo que eles permitem.
É um dos sites mais usados para estudar para maratona de computação, junto ao UVA (http://uva.onlinejudge.org) e ao SPOJ (http://br.spoj.pl).
Até![/quote]
E ao TopCoder.
Como pude me esquecer? Boa!
Eu vi esse site no site da Loiane Groner e achei bacana a ideia.
Alguem tem feito os problemas de lá?
http://ideiasdeprogramacao.blogspot.com/2011/12/desafios-de-programacao-project-euler.html
solucao do primeiro problema:
<script>
function solucao( razao_a, razao_b, limite)
{
var num_termos_a = ( limite - (limite % razao_a)) / razao_a;
var num_termos_b = ( limite - (limite % razao_b)) / razao_b;
var razao_ab = razao_a*razao_b;
var num_termos_ab = ( limite - (limite % razao_ab)) / razao_ab;
var soma_r3 = razao_a *num_termos_a *(num_termos_a +1)/2;
var soma_r5 = razao_b *num_termos_b *(num_termos_b +1)/2;
var soma_r15= razao_ab*num_termos_ab*(num_termos_ab+1)/2;
return (razao_a<=limite?soma_r3:0) + (razao_b<=limite?soma_r5:0) - (razao_ab<=limite?soma_r15:0) ;
}
// numeros menores que 1000. Tente outros limites
alert(solucao(3,5,999));
</script>Como estão fazendo o segundo problema?
Não vele força bruta.
Vou dar um exemplo de como se resolve o problema 3. De quebra, você tem de saber que:
a) Os problemas do Project Euler não têm limitação de tempo para executar, a única restrição é que você realmente consiga executá-los em tempo razoável. Muitas vezes se você for pelo caminho errado, você teria de esperar a criação e a recriação do universo várias vezes para seu algoritmo acabar de executar.
b) Você precisa saber um pouquinho de matemática para muitos desses problemas.
O problema 3 é:
Se você fatorar esse número, vai ver que seus fatores primos são 71, 839, 1471, e 6857, portanto a resposta é 6857.
Mas como é que você sabe que 1) 6857 é o maior fator primo, e 2) que 6857 em si é primo?
A primeira coisa que você tem de fazer é determinar qual seria o maior divisor possível desse número, se ele fosse quadrado. Nesse caso, o valor seria sqrt (600851475143) = 775146. Ou seja, qualquer fator primo desse número não deve ultrapassar o número 775146.
Uma forma muito simples de determinar se um número é primo é gerar uma tabela de números primos e achá-lo na tabela. Se alguém der uma busca nesse fórum, vai encontrar uma implementação do Crivo de Eratóstenes (a classe se chama “Sieve” se não me engano) que permite gerar tabelas grandes, do tipo um milhão de elementos, de modo que ocupe só um milhão de bits (128K). o que é bastante tolerável em termos de espaço.
A seguir, você vai fatorando o número 600851475143 percorrendo essa tabela de números primos e fazendo divisões, até que você ache todos os fatores. O último fator encontrado é o maior fator primo.
[quote=bezier curve]Vou dar um exemplo de como se resolve o problema 3. De quebra, você tem de saber que:
a) Os problemas do Project Euler não têm limitação de tempo para executar, a única restrição é que você realmente consiga executá-los em tempo razoável. Muitas vezes se você for pelo caminho errado, você teria de esperar a criação e a recriação do universo várias vezes para seu algoritmo acabar de executar.
b) Você precisa saber um pouquinho de matemática para muitos desses problemas.
O problema 3 é:
Se você fatorar esse número, vai ver que seus fatores primos são 71, 839, 1471, e 6857, portanto a resposta é 6857.
Mas como é que você sabe que 1) 6857 é o maior fator primo, e 2) que 6857 em si é primo?
A primeira coisa que você tem de fazer é determinar qual seria o maior divisor possível desse número, se ele fosse quadrado. Nesse caso, o valor seria sqrt (600851475143) = 775146. Ou seja, qualquer fator primo desse número não deve ultrapassar o número 775146.
Uma forma muito simples de determinar se um número é primo é gerar uma tabela de números primos e achá-lo na tabela. Se alguém der uma busca nesse fórum, vai encontrar uma implementação do Crivo de Eratóstenes (a classe se chama “Sieve” se não me engano) que permite gerar tabelas grandes, do tipo um milhão de elementos, de modo que ocupe só um milhão de bits (128K). o que é bastante tolerável em termos de espaço.
A seguir, você vai fatorando o número 600851475143 percorrendo essa tabela de números primos e fazendo divisões, até que você ache todos os fatores. O último fator encontrado é o maior fator primo.
[/quote]
Eu fiz o problema 3
dá uma olhada na minha solução:
http://www.ideiasdeprogramacao.blogspot.com/2011/12/project-euler-problema-3.html
para facilitar o trabalho eu prefiro colocar os primos em um array qye tiro daqui:
http://primes.utm.edu/lists/small/100000.txt
Eu estudo Teoria de Numeros e por isso não tenho interesse nas soluções com força bruta.
Agora estou tentando fazer o problema 2 por esse caminho:
phi^n - phi + 1/phi - 1/phi^2 + 1/phi^3 … 1/phi^n
Onde n é o termo da sequencia. Alguem já viu algo assim?
Eu cheguei a uma conclusão que pode ajudar:
Supondo que os 3 ultimos numeros da sequencia sejam:
impar, impar, par
e supondo que a somatoria dessa sequencia seja S eu posso dizer que o resultado da soma dos pares é S/2.
Uma coisa legal do uso da classe BitSet do Java é que ela é especialmente apropriada para guardar uma tabela de números primos.
É que ela tem um método chamado nextSetBit ( http://docs.oracle.com/javase/6/docs/api/java/util/BitSet.html#nextSetBit(int) ) e que, em alguns processadores, é diretamente compilada pela JVM para uma instrução especial do microprocessador que faz exatamente isso (indicar o índice do primeiro bit setado - na verdade a instrução conta o número de bits zero no começo do inteiro). Curioso, não?
[quote=entanglement]Uma coisa legal do uso da classe BitSet do Java é que ela é especialmente apropriada para guardar uma tabela de números primos.
É que ela tem um método chamado nextSetBit ( http://docs.oracle.com/javase/6/docs/api/java/util/BitSet.html#nextSetBit(int) ) e que, em alguns processadores, é diretamente compilada pela JVM para uma instrução especial do microprocessador que faz exatamente isso (indicar o índice do primeiro bit setado - na verdade a instrução conta o número de bits zero no começo do inteiro). Curioso, não?[/quote]
Descupa, mas não entendi o que vc disse. Isso pode acelerar a solução de algum destes problemas?
Como usar isso?
Se possivel, por favor manda outos links pra eu entender como isso funciona.
Para criar uma tabela de números primos você pode olhar uma classe que o Thingol escreveu há alguns anos atrás. Ela é um exemplo clássico do uso de BitSet.
Para saber se um número N é primo, após o preenchimento da tabela, verifique se o bit N está setado (bs.get(N) == true no código citado).
Por favor, procure por “Eratosthenes sieve” ou “Crivo de Eratóstenes”. Não precisa procurar muito no Google 
[quote=entanglement]Para criar uma tabela de números primos você pode olhar uma classe que o Thingol escreveu há alguns anos atrás. Ela é um exemplo clássico do uso de BitSet.
Para saber se um número N é primo, após o preenchimento da tabela, verifique se o bit N está setado (bs.get(N) == true no código citado).
Por favor, procure por “Eratosthenes sieve” ou “Crivo de Eratóstenes”. Não precisa procurar muito no Google :)[/quote]
Opa!
vc tem uma tebela de numeros primos guardada?
sua tabela tem quantos numeros?
Valeu pela dica. Vou dar uma olhada sobre isso mais tarde.
[]'s
Usando a classe acima, sua tabela é limitada pela quantidade de memória disponível e pelo maior índice que pode ser usado em um BitSet (que é um int). Nesse caso, você teria no máximo 2 bilhões de números (ou seja, 105097565 primos) o que dá cerca de 256 MB para a memória usada pelo BitSet. ).
Consegui resolver o problema do n termo da sequencia de Fibonacci.
Quem tiver mais questões interessantes sobre Phi por favor posta ai.
prq quem tiver interesse, as funções mais importantes não essas:
<script>
// Phi and phi conjugate
// Phi * phi = 1
var Phi= (1+Math.sqrt(5))/2;
var phi= (1-Math.sqrt(5))/2;
// Find the n number Fibonacci where sequence starting with 0
function Fib(n)
{
return Math.round(( Math.pow(Phi, n) - Math.pow(phi, n) ) / Math.sqrt(5));
}
// Find the sum of the n first numbers of Fibonacci where sequence starting with 0
function sumPhi(n)
{
return Fib(n+2)-1;
}
// Find position n of the value where Fib(n)=value
function FindPosition(value)
{
return Math.floor(Math.log(value*Math.sqrt(5))/Math.log(Phi));
}
document.write("Sum = "+sumPhi(8));
</script>Eu adoro os problemas de lá!
É tão gostoso resolver!
Apenas uma correção, diferente do UVa, Spoj e TopCoder, você não precisa obedecer a um tempo para resolver os problemas do Project Euler.
Eles dão o enunciado, e você resolve da melhor maneira que puder. Se quiser, pode até tentar resolver os problemas na mão mesmo e depois entrar com a resposta.
Eu gosto de fazer com algoritmos para treinar problemas de lógica.
Até postei alguns no blog, mas estou sem tempo de escrever post para todos que já resolvi!
[quote=Loiane]Eu adoro os problemas de lá!
É tão gostoso resolver!
Apenas uma correção, diferente do UVa, Spoj e TopCoder, você não precisa obedecer a um tempo para resolver os problemas do Project Euler.
Eles dão o enunciado, e você resolve da melhor maneira que puder. Se quiser, pode até tentar resolver os problemas na mão mesmo e depois entrar com a resposta.
Eu gosto de fazer com algoritmos para treinar problemas de lógica.
Até postei alguns no blog, mas estou sem tempo de escrever post para todos que já resolvi![/quote]
Eu também gostei muito do site. Não conhecia.
Fazia tempo que não estudava matematica dessa forma.
Eu tive problema pra resolver o Problem 2. Não lmbrava da formula da soma.
Mas pesquizando na internet achei um video muitissimo legal sobre numero de ouro:
Quem tiver no Euler vão gostar disso:
<script>
var tela = [ 08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08,
49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00,
81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65,
52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91,
22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80,
24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50,
32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70,
67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21,
24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,
21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95,
78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92,
16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57,
86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58,
19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40,
04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66,
88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69,
04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36,
20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16,
20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54,
01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48];
function getNumber(x, y)
{
return tela[20*y+x]
}
document.write("<body bgcolor='#000000'>")
document.write("<table border='0' cellspacing='0'>")
var cor;
for(var y=0; y<20; y++)
{
document.write("<tr>")
for(var x=0; x<20; x++)
{
cor=(getNumber(x, y)*2+55).toString(16);
document.write("<td bgcolor='#"+cor+"0000'>")
document.write(getNumber(x, y))
document.write("</td>")
}
document.write("</tr>")
}
document.write("</table>")
</script>