Números especiais

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

Re: Números especiais

Mensagempor Bruno Oliveira em Terça Fev 10, 2009 8:56 pm

Sim, Ivo, sou português de Portugal :lol: , e estou registado no PE, o nickname que uso é kuruma (a história deste nome, não tem mistério nenhum, precisava de um nome para registar uma conta de um jogo á muito tempo, que agora já nem jogo computador, e usei um gerador de nomes que lá estava, gerou este nome e olha, fiquei com ele :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: Números especiais

Mensagempor jap em Terça Fev 10, 2009 9:31 pm

Ivo_Timóteo Escreveu:(...)

Mas como saber que não há números maiores que N que satisfazem a condição? Que N é esse?
Embora ligeiramente fora do âmbito do Quark!, podem tentar demonstrar :) É mesmo muito fácil :D


Lazy, brute force approach:

Código: Seleccionar Todos
"""
Project Euler 30

Sum all numbers that are equal to the sum of the mth power of its digits

@jap-2009 having fun with Quark!
"""

m = 5

def sumdigits(n,m):
    "sum of the mth power of the digits of n"
    return sum(map(lambda c: int(c)**m,str(n)))

# Wild guess that the maximum number of digits is, at most, 10 and try to refine your guess to a smaller number...

for ndigits in range(1,10):
    if ndigits*9**m < 10**ndigits: break
else:
    print "Outch, the numbers can be really huge!!!"
   
# Now we hopefully know an upper bound for the number of digits...

print "Maximum number of digits to search", ndigits
print "Please wait..."

L = filter(lambda n: n == sumdigits(n,m), xrange(10,10**ndigits))

print "The numbers are", L
print "and their sum is", sum(L)
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: Números especiais

Mensagempor Bruno Oliveira em Terça Fev 10, 2009 9:36 pm

Gosto desta approach :D

É bastante gira e fácil de perceber :wink:
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: Números especiais

Mensagempor hexphreak em Terça Fev 10, 2009 9:38 pm

Por acaso está tecnicamente errada, já que não prova que não existam números com mais de dez dígitos para os quais a condição se verifique :P Mas é extremamente fácil mostrar que apenas números com até seis dígitos o podem fazer...
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Números especiais

Mensagempor jap em Terça Fev 10, 2009 9:44 pm

hexphreak Escreveu:Por acaso está tecnicamente errada, já que não prova que não existam números com mais de dez dígitos para os quais a condição se verifique :P Mas é extremamente fácil mostrar que apenas números com até seis dígitos o podem fazer...


Se existissem números com mais de 10 dígitos que satisfizessem as condições do problema ele não seria colocado no projecto Euler porque o tempo de computação dos ditos números, por qualquer algoritmo razoável, excederia o tempo de execução alocado. Experimenta percorrer simplesmente uma lista de 10000000000 números no teu PC... :lol:

Por isso a guess N=10 (deverei chamar-lhe ansatz?) e depois refiná-la para encontrar um upper bound menor parece-me *tecnicamente* bastante bom, embora insatisfatório, é claro, do ponto de vista matemático... :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: Números especiais

Mensagempor Bruno Oliveira em Terça Fev 10, 2009 9:52 pm

Pois, o tempo de execução é de apenas um minuto, e percorrer uma lista de 10000000000 números deve de certeza levar muito tempo, mesmo num pc bem artilhado :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: Números especiais

Mensagempor RicardoCampos em Quarta Fev 11, 2009 12:38 am

Bruno Oliveira Escreveu:Prof. de facto tanto o 0 como o 1, satisfazem as condições do problema, mas eles dizem para não contar com o 1, pois é uma soma de dígitos, então a resposta é 443839.

As1 = 1^4 is not a sum it is not included.


\sum_{i=1}^1 a_i = a_1
\emph{Ricardo Campos}\in \delta \bigcap q\overline{q}
O Matemático-Físico de 2008
Avatar do utilizador
RicardoCampos
top-Quark!
top-Quark!
 
Mensagens: 1280
Registado: Sexta Jun 01, 2007 3:49 pm
Localização: Figueira da Foz/Coimbra/DMUC/DFUC, Paris... E agora Zurique!

Re: Números especiais

Mensagempor Tharis em Quarta Fev 11, 2009 11:42 am

Bem, falando em termos de velocidade... É muito verdade que não se conseguem correr 10 000 000 000 iterações no PC em tempo útil, mas como até sou maluco, fui fazê-lo em C :), aqui ficam os resultados e o código:

tharis@tharis-lp:~$ time ./test

real 1m10.905s
user 1m1.104s
sys 0m0.156s


Código: Seleccionar Todos
int main() {
   unsigned long long i;
   const unsigned long long l=10000000000ULL;
   for (i=0;i<l;i++);
   return 0;
}


Não precisava de um unsigned long long, mas pronto, mais vale prevenir do que remediar.... (já agora, alguém me sabe dizer porque é que podia ter usado um long long (signed) em vez de um unsigned long long? :P Matemáticos, it's your turn! (apesar de não ser muito difícil) :P

Continuando, podemos reduzir em o MUITO o tempo de execução, cortando operações e usando cálculos que já efectuámos, bem como, o uso de um JIT (Just in Time Compiler), porque apesar de Python ser interpretado, também é compilado para bytecode... :)

Mostro-vos o JIT do Python que é o Psyco... Chega a reduzir tempos de execução bruscamente (provado por mim em exercícios de grafos). :D

E para o usarem, só precisam de o ter instalado e meter duas linhas de código:

Código: Seleccionar Todos
import psyco
psyco.full()


Atenção que não vou usar o PSYCO neste post. :)

Com o código do Prof. JAP , temos um tempo muito bom para o Python :hands: :
tharis@tharis-lp:~$ time python test.py
Maximum number of digits to search 6
Please wait...
The numbers are [4150, 4151, 54748, 92727, 93084, 194979]
and their sum is 443839

real 0m11.984s
user 0m11.517s
sys 0m0.052s


Mas, será que o podemos melhorar? Eu estou a escrever isto e ainda não fiz as modificações, por isso, estou como vocês: "será que vou conseguir melhorar o código em termos de execução de tempo?" Vamos ver! Pegando no código e assumindo que o Prof. o lançou em Open-Xor (OpenSource) e que podemos modificá-lo.

Aqui ficam os resultados, tal como eu esperava! :D Menos 10 segundos de execução! Acabei de usar programação dinâmica, que é uma das competências em que tenho mais dificuldade e que ando a treinar! Por isso, deixem-me só :hands: a mim próprio! :P

tharis@tharis-lp:~$ time python test.py
Maximum number of digits to search 6
Please wait...
The numbers are [4150, 4151, 54748, 92727, 93084, 194979]
and their sum is 443839

real 0m2.779s
user 0m1.760s
sys 0m0.168s


Aqui fica o código modificado:

Código: Seleccionar Todos
"""
Project Euler 30

Sum all numbers that are equal to the sum of the mth power of its digits

@jap-2009 having fun with Quark!

Modifications by Tharis: dictionary `d' and `sumdigits' function
"""

m = 5

d= dict( [(i,i**m) for i in range(10)] )

def sumdigits(n,m):
    "sum of the mth power of the digits of n"
    global d
    d[n]=d[n/10]+d[n%10]
    return d[n]

# Wild guess that the maximum number of digits is, at most, 10 and try to refine your guess to a smaller number...

for ndigits in range(1,10):
    if ndigits*9**m < 10**ndigits: break
else:
    print "Outch, the numbers can be really huge!!!"
       
# Now we hopefully know an upper bound for the number of digits...

print "Maximum number of digits to search", ndigits
print "Please wait..."

L = filter(lambda n: n == sumdigits(n,m), xrange(10,10**ndigits))

print "The numbers are", L
print "and their sum is", sum(L)


Alguém me consegue encontrar as modificações e explicar porque as fiz? :P :)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números especiais

Mensagempor jap em Quarta Fev 11, 2009 5:42 pm

Muito bem! :hands:

O velo truque da "look-up table" funciona sempre! :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

Anterior

Voltar para Pitónica

Quem está ligado

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