Página 1 de 1

Feynman Riddle (muito fácil!!)

MensagemEnviado: Terça Jul 06, 2010 8:38 am
por Bruno Oliveira
Vou aqui deixar mais um problema, desta vez é do SPOJ e já o limpei!! É um problema simples, mas, como fala do Feynman, achei que seria interessante colocá-lo aqui:

Richard Phillips Feynman was a well known American physicist and a recipient of the Nobel Prize in Physics. He worked in theoretical physics and also pioneered the field of quantum computing. He visited South America for ten months, giving lectures and enjoying life in the tropics. He is also known for his books "Surely You're Joking, Mr. Feynman!" and "What Do You Care What Other People Think?", which include some of his adventures below the equator.

His life-long addiction was solving and making puzzles, locks, and cyphers. Recently, an old farmer in South America, who was a host to the young physicist in 1949, found some papers and notes that is believed to have belonged to Feynman. Among notes about mesons and electromagnetism, there was a napkin where he wrote a simple puzzle: "how many different squares are there in a grid of N ×N squares?".

In the same napkin there was a drawing which is reproduced below, showing that, for N=2, the answer is 5.


Imagem

Este problema no SPOJ, só é aceite em C++, mas fazê-lo em Python é igualmente interessante, e pode ser um bom desafio para quem quer aprender Python. :)

No entanto, como os valores dos casos de teste são baixos, o programa que fizerem (qualquer que ele seja) deve correr rapidamente, por isso, desafio os newbies, a fazerem um programa que dê o número de quadrados numa grid N x N numa única linha de código.

PS: Caso seja necessária tradução do enunciado, digam.

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quarta Jul 07, 2010 8:50 pm
por jap
Excelente! :hands:
Obrigado, Bruno, por mais esta colaboração! :friends:

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quarta Jul 07, 2010 8:55 pm
por Bruno Oliveira
É um prazer poder ligar a Física à programação, e poder fazê-lo num sitio onde as pessoas realmente se interessam e empenham (a prestação num problema deste tipo no fórum de Civil do IST, está até ao momento, situada em nula :P ) é um enorme privilégio :)

Sem dúvida que aprender Python foi uma das (muitas) excelentes coisas que aprendi estando ligado aqui ao Quark! e sempre que puder darei uma colaboração :wink:

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 2:38 am
por RicardoCampos
Hum, uma fórmula fechada para isto será simples?

Vou testar a minha linguagem favorita, pencil and paper

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 7:56 am
por Bruno Oliveira
Há uma fórmula simples, que se deduz muito facilmente a partir da análise dos primeiros 4/5 casos, e que foi a fórmula que usei para obter a resposta.

Não é uma fórmula fechada no entanto :P

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 11:18 am
por Tharis
Tenho uma fórmula fechada.

S(N) = \frac{1}{6}(2N^3 - 3N^2 + N) + N^2

S(1) = (2 - 3 + 1)/6 + 1 = 0 + 1 = 1
S(2) = (16 - 12 + 2)/6 + 4 = 1 + 4 = 5
S(3) = (54 - 27 + 3)/6 + 9 = 5 + 9 = 14
...

De onde se pode tirar a conclusão que:

S(N) = S(N-1) + N^2


- Quem quer chegar à fórmula inicial?
- Quem quer explicar a lógica desta recursão?

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 11:33 am
por Bruno Oliveira
Bom, a fórmula recursiva é praticamente uma maneira semelhante a fazer uma soma dos quadrados de 1 até N, que era a "fórmula" que tinha derivado inicialmente:

\displaystyle \sum_{i=1}^{i=N} i^2

O termo S(N-1) simplesmente condensa \displaystyle \sum_{i=1}^{i=N-1} i^2 num único valor recorrendo a ele para achar o valor para o N seguinte. De facto, a derivação de um somatório como fórmula estava mesmo a pedir uma recursão, mas, mais uma vez, não me apercebi disso... :twisted:

Está na altura de começar a elevar as minhas fasquias :lol:

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 11:42 am
por Tharis
Sim, mas porque é que a solução para N é a solução de N-1 somada com o quadrado de N? Aka explicar no contexto do problema o que é que cada um dos termos representa.

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 11:51 am
por Bruno Oliveira
Ah então é simples:

N^2 é o número de quadrados mais pequenos na grid de N x N (é a área de N se assim o quiseres entender);

O termo S(N-1) é, por analogia, a área de uma grid N-1 x N-1

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 12:28 pm
por Tharis
Bruno Oliveira Escreveu:Ah então é simples:

N^2 é o número de quadrados mais pequenos na grid de N x N (é a área de N se assim o quiseres entender);

O termo S(N-1) é, por analogia, a área de uma grid N-1 x N-1


Tens a certeza?

S(2) = 5
2 x 2 = 4
5 != 4

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 12:46 pm
por Bruno Oliveira
Que estupidez, é o que dá responder à pressa...

Pois, temos de entrar com o quadrado exterior claro...Vou pensar um bocado no assunto.

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 1:21 pm
por pfc
Bem, quando se passa de um quadrado de n-1 x n-1 para n x n acrescenta-se:
1 quadrado nx n
3 quadrados n-1 x n-1
5 quadrados (n-2) x (n-2)
até contarem os quadrados 1x1. Penso que isto é fácil de perceber desenhando os primeiros casos.

Sendo assim,
S(n)=S(n-1)+\displaystyle \sum_{i=1}^{n}(2i-1)\Leftrightarrow
\Leftrightarrow S(n) = S(n-1)+n^2

Agora S(n)=\dfrac{2n^3+3n^2+n}{6} ainda me escapa :P

Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Quinta Jul 08, 2010 2:06 pm
por Tharis
Awesome! :hands:

Digo isto porque eu interpretei de outra maneira, se calhar mais difícil de perceber.

Quando se passa de um quadrado N-1 x N-1 para um de NxN podemos reparar que cada sub-quadrado de lado n se "transforma" num sub-quadrado com um lado n+1.

Ou seja, S(N-1) é o número de sub-quadrados com comprimento maior que 1 que existem no quadrado de lado N. Para termos S(N) falta apenas juntar o número de quadrados de lado 1 aka N^2.

Tomemos por exemplo 3 -> 4.

Para N=3, na primeira linha temos 3 sub-quadrados de lado 1.
Para N=4, na primeira linha temos 3 sub-quadrados de lado 2.

Para N=3, na primeira linha temos 2 sub-quadrados de lado 2.
Para N=4, na primeira linha temos 2 sub-quadrados de lado 3.
...

Então, só falta adicionar todos os de lado 1, NxN. :D


Quanto à fórmula, se quiserem uma dica, abram o spoiler.


Re: Feynman Riddle (muito fácil!!)

MensagemEnviado: Sábado Jul 10, 2010 5:40 am
por pfc
Bem, sabendo a fórmula daria para demonstrar por indução.

S(1)=1=\dfrac{2\times 1^3+3\times 1^2+1}{6}
S(n+1)=S(n)+(n+1)^2\Leftrightarrow
\Leftrightarrow S(n+1)=\dfrac{2n^3+3n^2+n+6n^2+12n+6}{6}\Leftrightarrow
\Leftrightarrow S(n+1)=\dfrac{2n^3+9n^2+13n+6}{6}\Leftrightarrow
\Leftrightarrow S(n+1)=\dfrac{2(n+1)^3+3(n+1)^2+n+1}{6}

Outro caminho,
Seja S=\displaystyle \sum_{i=1}^{n}i^2
Se colocarmos quadrados de lado i lado a lado:
[][][]
[][][] [][]
[][][] [][] []
Vemos que (com n=3) S é a diferença entre a área do rectângulo 3x(3+2+1) e 1+(1+2):
S=n\displaystyle \sum_{i=1}^{n}i-\displaystyle \sum_{i=1}^{n-1}\sum_{j=1}^{i}k\Leftrightarrow
\Leftrightarrow S=n\dfrac{n(n+1)}{2}-\displaystyle \sum_{i=1}^{n-1}\dfrac{i^2+i}{2}\Leftrightarrow
\Leftrightarrow 2S=n^3+n^2-(S-n^2)-\displaystyle \sum_{i=1}^{n-1}i\Leftrightarrow
\Leftrightarrow 6S=2n^3+4n^2-(n^2-n)\Leftrightarrow
\Leftrightarrow S=\dfrac{2n^3+3n^2+n}{6}