Project Euler

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:

What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

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é!

maquiavelbona wrote: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é!

E ao TopCoder.

Como pude me esquecer? Boa!

JavaEvangelist Membro desde: 23/04/2008 09:44:26 Mensagens: 304 Offline

http://projecteuler.net/index.php?section=scores&country=Brazil

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:

Como estão fazendo o segundo problema?
Não vele força bruta.

JavaEvangelist Membro desde: 28/11/2009 17:55:58 Mensagens: 411 Offline

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 é:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

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.

bezier curve wrote: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 é:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

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.

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.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

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%28int%29 ) 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?

entanglement wrote: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%28int%29 ) 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?

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.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

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.
http://www.guj.com.br/java/43972-off-topic#233496

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

entanglement wrote: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.
http://www.guj.com.br/java/43972-off-topic#233496

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

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

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Luiz Augusto Prado wrote:
vc tem uma tebela de numeros primos guardada?
sua tabela tem quantos numeros?

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:

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!

Notícias, artigos e o maior fórum brasileiro sobre Java