# Simplificar

## 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>

##### 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.

##### Share on other sites

Sim, exactamente isso, no entanto os numeros têm que € ]2*10^6;10^9].

Ps:sim, é o 372: http://projecteuler.net/problem=372 .

<Signature goes here>

##### 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.

##### 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>

##### 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): ##### 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):

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!

## Create an account

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...