Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

xtrm0

Simplificar

Mensagens Recomendadas

xtrm0

Boas. Alguem me pode ajudar a simplificar o seguinte código?:

import math
ans=0
i=2000000 #2*10^6
j=2000000 #2*10^6
isq=0
while (i<1000000000): #10^9
    i+=1
    isq=i*i
    j=2000000 #2*10^6
    while (j<1000000000): #10^9
        j+=1
        if (((math.floor((j*j)/(isq)))%2)==0): #se chao(j^2/i^2) for par, entao ans+=1
            ans+=1

print ans


<Signature goes here>

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Não se trata de simplificar código, trata-se de arranjar outro algoritmo para fazer o que pretendes.

Queres contar o número de pares menores que 1000000000 cujo floor(j^2/i^2) seja par?

PS: Cheira-me a problema do project euler.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

O problema não é fácil, e infelizmente não tenho tempo para pensar sobre ele.

Os meus primeiros dois pensamentos foram para teoria dos números e para programação dinâmica.

Não sei se não arranjas uma fórmula simples de calcular R(N). Acho que R(N, M) = R(N) - R(M), pelo que simplificas o problema.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
xtrm0

Acho que essa igualdade e falsa.

Pois repara que para:

R(N=3), tens os pares:

1,1/1,2/1,3/2,1/2,2/2,3/3,1/3,2/3,3

R(M=2), tens os pares:

1,1/1,2/2,1/2,2

R(M,N=2,3), tens os pares:

2,2/2,3/3,2/3,3

E para R(N)-R(M):

2,2/2,3/3,2/3,3/3,1/3,1

Dá para simplificar como anteriormente, tendo em conta este pormenor?

Acabei também de reparar, que se f(x<y,y) for impar, então f(y,x) é par, já que o resultado da divisão será inferior a um.

O mesmo acontece para se f(x<y,y) for par, então f(y,x) é par, já que o resultado da divisão será menor que um.


<Signature goes here>

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Pedro Ribeiro

xtrm0, o problema é interessante, mas devias realmente ter colocado o enunciado e não apenas dar o código e pedir para te "simplificarem".

Não tenho tempo agora para isso, mas parece-me obviamente um problema cheio de "padrões". Por exemplo, se x<=y, então o floor(y^2/x^2)=0 e logo não é ímpar. Já experimentaste "desenhar" (computacionalmente) o espaço de soluções? Além de uma diagonal inferior "vazia" intuitivamente parece dar uns "triângulos" giros que te poderão dar mais ideias.

E já agora, não é a única maneira de "atacar" o problema, mas os padrões habituais de resolução de problemas em matrizes (ex: somas acumuladas) dão-te logo a intuição de como resolver eventualmente via PD. Neste caso, considera R(A,B,C,D) como sendo o espaço de soluções para os pontos(x,y) com A<x<=B e C<y<=D tal que floor(y^2/x^2) é ímpar. Então:

- R(M,N) = R(M,N,M,N)

- R(M,N) = R(0,N,0,N) - R(0,N,0,M) - R(0,M,0,N) + R(0,M,0,M)

Se realmente for mais "fácil" pensar nas soluções para os quais o limite inferior é zero, então tens aí uma nova igualdade. Nota que somei R(0,M,0,M) porque essa parte é subtraída duas vezes

nas parcelas anteriores.

EDIT: uma pesquisa rápida deu-me a imagem que estava a pensar criar. Este é o espaço de soluções de R(0,500):

9awxkw.png

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

EDIT: uma pesquisa rápida deu-me a imagem que estava a pensar criar. Este é o espaço de soluções de R(0,500):

Bah para o google!

Eu não pesquisei ... fui logo para o desenho: R(0, 1000)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.