Project Euler 100

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Project Euler 100

Mensagempor Bruno Oliveira em Terça Jun 02, 2009 6:36 pm

Não sei se já alguém aqui, o tentou sequer resolver, mas vou deixar aqui o enunciado e apresentar a minha solução em Python:

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 10^{12} = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
última vez editado por Bruno Oliveira s Terça Jun 02, 2009 6:50 pm, editado 1 vez no total
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Project Euler 100

Mensagempor Bruno Oliveira em Terça Jun 02, 2009 6:46 pm

Vou então deixar a minha tentativa de solução (que está errada :? ) neste novo post:

Considerando que a é o número de bolas azuis que existem de entre o total e sendo t o número total de bolas, creio que é correcto escrevermos que:
P(aa)={a \over t} \times {a-1 \over t-1}.

Mas como queremos que a probabilidade de tirar duas bolas azuis, uma depois da outra seja { 1 \over 2}, ficamos com a equação:
{a \over t} \times {a-1 \over t-1}={1 \over 2}, obviamente queremos resolver esta equação em ordem a a.

Efectuando umas contas:
{a^2-a \over t^2-t}={1 \over 2}

Depois será correcto montar a equação a^2-a-{t^2-t \over 2}=0 e tratá-la como uma quadrática em que:

a=1
b=-1
c=-{t^2-t \over 2}

?

Usando este método, o meu programa facilmente resolve o caso de exemplo, mas dá erro no caso pedido... :roll:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Project Euler 100

Mensagempor jap em Terça Jun 02, 2009 9:56 pm

Coloca aqui o teu programa para nós corrigirmos! :D
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Project Euler 100

Mensagempor Tharis em Terça Jun 02, 2009 10:05 pm

jap Escreveu:Coloca aqui o teu programa para nós corrigirmos! :D


"Corrigir" ? :roll:

Se ele foi por brute-force sem optimizações, e mesmo um brute-force com optimizações, duvido que exista algo a corrigir para um limite tão grande. :?

Mas pronto, o professor pode ter aí alguma na manga. :D :p
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Project Euler 100

Mensagempor jap em Terça Jun 02, 2009 10:12 pm

Acho que a resposta é (por brute force e sem problemas! :lol:):

707106783028

Estarei errado? :roll: É que me parece muito fácil! :wink:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Project Euler 100

Mensagempor Tharis em Terça Jun 02, 2009 10:14 pm

jap Escreveu:Acho que a resposta é (por brute force e sem problemas! :lol:):

707106783028

Estarei errado? :roll: É que me parece muito fácil! :wink:


Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Project Euler 100

Mensagempor jap em Terça Jun 02, 2009 10:20 pm

Tharis Escreveu:(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...


Bom, eu comecei em 10**12, o que está para trás não interessa... :lol:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Project Euler 100

Mensagempor Bruno Oliveira em Terça Jun 02, 2009 10:22 pm

jap Escreveu:Acho que a resposta é (por brute force e sem problemas! :lol:):

707106783028

Estarei errado? :roll: É que me parece muito fácil! :wink:


Não prof. a resposta do project euler não é essa, aliás, a resposta certa (consegui entretanto encontrar um código em VB, que executei) é um número bastante maior:

756872327473

Acho que o erro no meu programa se deve a não conseguir arranjar uma precisão de muitas casas decimais só com o float... :roll:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Project Euler 100

Mensagempor Tharis em Terça Jun 02, 2009 10:27 pm

jap Escreveu:
Tharis Escreveu:(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...


Bom, eu comecei em 10**12, o que está para trás não interessa... :lol:


Claro que sim, mas mesmo assim.... O professor, fez um ciclo em que a variável de iteracção é o total de CDs ou o número de CDs azuis?


@Bruno Oliveira, NUNCA DUVIDES DA PRECISÃO DO PYTHON. Python tem BigInts, floats tudo implementado out-of-the-box e com as melhores optimizações.... ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Project Euler 100

Mensagempor Bruno Oliveira em Terça Jun 02, 2009 10:32 pm

Tharis Escreveu:
jap Escreveu:
Tharis Escreveu:(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...


Bom, eu comecei em 10**12, o que está para trás não interessa... :lol:


Claro que sim, mas mesmo assim.... O professor, fez um ciclo em que a variável de iteracção é o total de CDs ou o número de CDs azuis?


@Bruno Oliveira, NUNCA DUVIDES DA PRECISÃO DO PYTHON. Python tem BigInts, floats tudo implementado out-of-the-box e com as melhores optimizações.... ;)


Não duvido, claro, até estive a ler sobre o modulo decimal e tudo, assim que o conseguir implementar como deve de ser no meu programa, tenho-o feito...bem, ou quase, depois tenho de fazer um ciclo entre 1 bilião e 2 biliões para obter a resposta por brute force :lol:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Project Euler 100

Mensagempor Bruno Oliveira em Terça Jun 02, 2009 10:38 pm

Aqui vai o meu código, para tratar do caso de exemplo:
Código: Seleccionar Todos
from math import *
a=1
b=-1
for t in range(100,150):
    c=-(t**2-t)/2
    s=(-b+sqrt(b**2-4*a*c)/(2*a)
    if float(str(s))-float(int(str(s)))==0:
       print t, "soluçao",s


Eu sei que não é pitónico, não tenham um ataque :P , agora estou a obter erro nesta linha:
Código: Seleccionar Todos
if float(str(s))-float(int(str(s)))==0:


Antes funcionava... :x
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Project Euler 100

Mensagempor Tharis em Terça Jun 02, 2009 11:07 pm

O teu código como o tens seria mais assim:

Código: Seleccionar Todos
from math import *
a = 1; b = -1

for t in range(100, 150):
    c = -(t**2 - t) / 2.
    s = (-b + sqrt(b**2-4*a*c) / (2. * a)
    if (float(s) - int(s)) == 0:
       print t, "soluçao",s


Atenção que não estou a corrigir o método de resolução.
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Project Euler 100

Mensagempor jap em Quarta Jun 03, 2009 2:41 am

Sorry, o meu programa tinha de facto um bug mas já corrigi, aliás arrangei uma solução mais elegante! :lol:

Aqui vai a minha solução (altamente não ortodoxa!):


Código: Seleccionar Todos
"""
EULER Project #100
Elegant solution, avoiding brute force methods
Map equation

a*(a-1)
------  = 0.5
t*(t-1)

into the well known diophantine equation z^2-2y^2 = -1
using the following transformations:

y = 2a-1
z = 2t-1

Solution of the above equation can be expressed from odd powers of
(1+sqrt(2))  and  (1-sqrt(2))
see, eg,  Wolfram Research or work it out yourself!

@jap 2009, who could not go to sleep before solving this problem! :)
"""

from math import *

# To test precision/roundoff errors you may uncomment the following lines to test the results with a precision of 50 decimals!
# (you may need to install the multiprecision math module in your system)
# Tested OK: math and mpmath with 50 decimals give the same results. ;)

#from mpmath import *
#mp.dps = 50


LIMIT = 10**12

n = 3
while True:
    z = ((1+sqrt(2))**n+(1-sqrt(2))**n)/2.
    y = ((1+sqrt(2))**n-(1-sqrt(2))**n)/(2*sqrt(2))
    t = int(round((z+1)/2))
    a = int(round((y+1)/2))
    print "Total discs",t,"blue disks",a,"red disks",t-a
    n += 2
    if t > LIMIT:
       print "\nFound the solution: number of blue disks is",a
       break


cujo output é

Código: Seleccionar Todos
Total discs 4 blue disks 3 red disks 1
Total discs 21 blue disks 15 red disks 6
Total discs 120 blue disks 85 red disks 35
Total discs 697 blue disks 493 red disks 204
Total discs 4060 blue disks 2871 red disks 1189
Total discs 23661 blue disks 16731 red disks 6930
Total discs 137904 blue disks 97513 red disks 40391
Total discs 803761 blue disks 568345 red disks 235416
Total discs 4684660 blue disks 3312555 red disks 1372105
Total discs 27304197 blue disks 19306983 red disks 7997214
Total discs 159140520 blue disks 112529341 red disks 46611179
Total discs 927538921 blue disks 655869061 red disks 271669860
Total discs 5406093004 blue disks 3822685023 red disks 1583407981
Total discs 31509019101 blue disks 22280241075 red disks 9228778026
Total discs 183648021600 blue disks 129858761425 red disks 53789260175
Total discs 1070379110497 blue disks 756872327473 red disks 313506783024

Found the solution: number of blue disks is 756872327473
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Project Euler 100

Mensagempor Tharis em Quarta Jun 03, 2009 10:57 am

Ui, muito fixe.... :D Tenho de ir ver isso ao Wolframalpha.;) :hands:
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Project Euler 100

Mensagempor jap em Quarta Jun 03, 2009 1:41 pm

Ainda mais fixe! :lol:

Uma nova solução, mais elegante (mais pitónica!), usando recursão e apenas aritmética inteira... ;)

Código: Seleccionar Todos
"""
EULER Project #100
Elegant solution, avoiding brute force methods, solution 2
much simpler and cleaner!


Map equation

a*(a-1)
------  = 0.5
t*(t-1)

into the well known diophantine equation z^2-2y^2 = -1
using the following transformations:

y = 2a-1
z = 2t-1

Solution of the above equation can be expressed recursively
from the fundamental solution z=1,y=1!

@jap 2009, Can't get much simpler than this! :)
"""

LIMIT = 10**12

z,y = 1,1

while True:
    z,y = 3*z +4*y,2*z + 3*y
    t,a = (z+1)/2,(y+1)/2
    print "Total discs",t,"blue disks",a,"red disks",t-a

    if t > LIMIT:
       print "\nFound the solution: number of blue disks is",a
       break


Resultado deste programa (confere com o anterior!):
Código: Seleccionar Todos
Total discs 4 blue disks 3 red disks 1
Total discs 21 blue disks 15 red disks 6
Total discs 120 blue disks 85 red disks 35
Total discs 697 blue disks 493 red disks 204
Total discs 4060 blue disks 2871 red disks 1189
Total discs 23661 blue disks 16731 red disks 6930
Total discs 137904 blue disks 97513 red disks 40391
Total discs 803761 blue disks 568345 red disks 235416
Total discs 4684660 blue disks 3312555 red disks 1372105
Total discs 27304197 blue disks 19306983 red disks 7997214
Total discs 159140520 blue disks 112529341 red disks 46611179
Total discs 927538921 blue disks 655869061 red disks 271669860
Total discs 5406093004 blue disks 3822685023 red disks 1583407981
Total discs 31509019101 blue disks 22280241075 red disks 9228778026
Total discs 183648021600 blue disks 129858761425 red disks 53789260175
Total discs 1070379110497 blue disks 756872327473 red disks 313506783024

Found the solution: number of blue disks is 756872327473


Isn't Python Beautiful? :P
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Próximo

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron