Feynman Riddle (muito fácil!!)

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

Feynman Riddle (muito fácil!!)

Mensagempor Bruno Oliveira em Terça Jul 06, 2010 8:38 am

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.
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: Feynman Riddle (muito fácil!!)

Mensagempor jap em Quarta Jul 07, 2010 8:50 pm

Excelente! :hands:
Obrigado, Bruno, por mais esta colaboração! :friends:
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: Feynman Riddle (muito fácil!!)

Mensagempor Bruno Oliveira em Quarta Jul 07, 2010 8:55 pm

É 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:
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: Feynman Riddle (muito fácil!!)

Mensagempor RicardoCampos em Quinta Jul 08, 2010 2:38 am

Hum, uma fórmula fechada para isto será simples?

Vou testar a minha linguagem favorita, pencil and paper
\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: Feynman Riddle (muito fácil!!)

Mensagempor Bruno Oliveira em Quinta Jul 08, 2010 7:56 am

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
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: Feynman Riddle (muito fácil!!)

Mensagempor Tharis em Quinta Jul 08, 2010 11:18 am

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?
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

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

Mensagempor Bruno Oliveira em Quinta Jul 08, 2010 11:33 am

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:
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: Feynman Riddle (muito fácil!!)

Mensagempor Tharis em Quinta Jul 08, 2010 11:42 am

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.
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

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

Mensagempor Bruno Oliveira em Quinta Jul 08, 2010 11:51 am

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
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: Feynman Riddle (muito fácil!!)

Mensagempor Tharis em Quinta Jul 08, 2010 12:28 pm

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

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

Mensagempor Bruno Oliveira em Quinta Jul 08, 2010 12:46 pm

Que estupidez, é o que dá responder à pressa...

Pois, temos de entrar com o quadrado exterior claro...Vou pensar um bocado no assunto.
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: Feynman Riddle (muito fácil!!)

Mensagempor pfc em Quinta Jul 08, 2010 1:21 pm

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
pfc
bottom-Quark!
bottom-Quark!
 
Mensagens: 35
Registado: Sexta Out 31, 2008 9:25 pm

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

Mensagempor Tharis em Quinta Jul 08, 2010 2:06 pm

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.

Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

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

Mensagempor pfc em Sábado Jul 10, 2010 5:40 am

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}
pfc
bottom-Quark!
bottom-Quark!
 
Mensagens: 35
Registado: Sexta Out 31, 2008 9:25 pm


Voltar para Pitónica

Quem está ligado

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

cron