Jump to content

Simplificar


xtrm0
 Share

Recommended Posts

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>

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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>

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.