[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Algoritmos
Ola Pessoal,
Me parece que este problema ja foi proposto antes e, se nao me engano, o
Marcio ou o Duda derao uma solucao usando matrizes. Mas nao tenho certeza.
Bom, ja que o Vinicius fez a ( bela ) solucao inversa, vou dar as bases
matematicas para voces desenvolverem uma solucao direta. Me parece que este
problema ja foi proposto antes
Seja N o numero inicial de cartas, dispostas na forma de um monte. Como as
cartas sao numeradas a partir de 1 da base para o topo, segue que a carta do
topo e N.
O Algoritmo e iniciado :
A carta N vai para a base do monte, a carta N-1 fica no topo. Apos esta
primeira iteracao, se olhassemos as cartas da base para o topo, veriamos :
N,1,2,3, ...,N-1
O algoritmno segue ... A carta N-1 sera eliminada, a carta N-2 fica no topo.
Esta ultima carta sera entao conduzida a base do monte. Se apos este
movimento olhassemos o monte da base para o topo, veriamos :
N-2,N,1,2,3, ...,N-3.
Duas coisas sao evidentes :
1) A carta N esta "subindo" e, inevitavelmente, retornara ao topo do monte.
2) Quando a carta N retornar ao topo do monte o algoritmo tera eliminado
todas as cartas com paridade diferente da paridade da carta N.
Portanto, quando N retornar ao topo do monte, so haverao : cartas impares se
N e impar; cartas pares se N e par. Dai concluimos que a carta que sobra tem
a paridade de N. Como a carta que sobrou foi 2001, concluimos que N e impar.
Seja portanto N=2p+1, para algum p inteiro positivo.
Quando N RETORNAR ao topo, ela sera conduzida novamente a base do monte ou
sera eliminada ? SERA ELIMINADA ! Por que ? Porque a acao atual que o
algoritmo vai efetuar sobre a carta do topo, quando esta carta ja esteve no
topo anteriormente, DEPENDE UNICAMENTE DA PARIDADE DA QUANTIDADE DE CARTAS
QUE HAVIAM QUANDO A CARTA ESTEVE NO TOPO PELA ULTIMA VEZ ... complicou ?
Para ver isso claramente, IMAGINE o monte de cartas num momento qualquer de
execucao do algoritmo e suponha que a carta atual que esta no topo sera
conduzida a base do monte. Enumere mentalmente as cartas da base para o
topo, a partir de 1. Seja P a carta do topo do Monte. Associando 1 a acao de
conduzir a carta a base; 0, a acao de eliminar a carta.
Olhando da base para o topo teriamos :
C1,C2,C3,C4,C5,...,Cp-2,Cp-1,Cp
Associando as acoes as cartas :
(0,C1),(1,C2),(0,C3),(1,C4),...,(0,Cp-1),(1,Cp) se p e par
(1,C1),(0,C2),(1,C3),(0,C4),...,(0,Cp-1),(1,Cp) se p e impar
Esta simples observacao mostra claramente que se uma carta RETORNA ao topo
do monte, ela sera entao eliminada se na ultima vez que ela esteve no topo
havia um numero impar de cartas.
Ora, a carta 2001 e a carta que sobra ... e portanto a carta que fica no
topo do ultimo monte ... o monte com UMA carta ... alguma carta estava
portanto sobre ela e foi eliminada ... ela portanto jamais esteve no topo de
um monte com um numero impar de cartas ... ela portanto esteve no topo de um
monte com ... 2 cartas, 4 cartas, 8 cartas, 16 cartas, ... 2^X cartas
Bom, pra mim, depois destas observacoes, que foram simplesmente o registro
de fatos derivados do ato de acompanhar com a mente a visualizacao do
algoritmo em operacao, o problema esta resolvido.
Pois a carta 2001 e impar ! Quando ela esteve no topo pela primeira vez, se
olhassemos da base para o topo, veriamos :
2003, 2005, 2007, ..., N-4, N-2, N,1,2,3,4,...,2001
Assim, pelo que vimos, a sequencia acima deve ter uma potencia de 2 de
termos. So pode ser 2048=2^11 ( pois 4096 implica N > 500 ). Logo, a PA :
2003, 2005, 2007, ..., N-4, N-2, N
tem 47 termos ! Isto e : N=2003+46*2 => N=2095
Claramente que e trivial generalizar este raciocinio para ser aplicado em
qualquer circunstancia, desde que seja dado o limitante superior para o
monte ( neste caso N < 5000 ) e a carta final ( neste caso 2001 ).
Muitas questoes computacionais verdadeiramente interessantes tem esta
caracteristica... Elas pedem previamente uma solucao matematica ... O
algoritmo tao somente uma implementacao da solucao solucao.
No caso deste problema, um mero "printf" da a solucao. Esta a vantagem de um
ataque direto, deste que se tenha sucesso na solucao matematica. Fica como
exercicio alguem publicar o algoritmo direto !
Um abraco a todos !
Paulo Santa Rita
6,1849,190702
>From: Vinicius José Fortuna <ra992559@ic.unicamp.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Algoritmos
>Date: Fri, 19 Jul 2002 15:25:16 -0300 (EST)
>
>O problema reverso, de ter que descobrir qual carta sobra, dado o número
>de cartas é uma especialização do "Josephus Problem".
>
>Vejam em http://library.wolfram.com/examples/josephusproblem
>
>No caso do Josephus Problem o movimento é invertido e movimentam-se várias
>cartas. Retira-se a primeira carta e coloca-se n cartas em baixo do monte.
>(No problema da Fernanda, coloca-se *uma* carta em baixo do monte e
>retira-se a primeira)
>
>Bom, isso é só curiosidade. É que resolvi o problema da Fernanda
>utilizando o problema reverso. Escrevi um programa de computador que
>calculava a carta que sobra para pilhas de diversos tamanhos até encontrar
>a resposta. As duas primeiras pilhas em que sobram a carta 2001 são de
>tamanho 2095 e 6191, mas como se quer uma de tamanho menor que 5000, a
>solução é 2095
>
>Eu poderia ter feito o programa simulando os movimentos, mas, para um dado
>n, a complexidade seria O(n^2). Considerando que se calculava para todos
>os primeiros valores até encontrar a solução, a complexidade seria
>O(s^3), onde s é o valor da solução. Isso é proibitivo para valores
>altos como 2001.
>
>Dessa forma me baseei na recorrência
>T(n) = n , se T(n-1)==1
>T(n) = T(n-1)-1, caso contrário
>T(1) = 1
>T(n) significa a carta que sobra em uma pilha de n cartas.
>Observe que se temos uma pilha [1,..,n], ao se realizar o movimento do
>problema, teremos uma pilha [n,1,...,n-2], que tem n-1 elementos,
>reduzindo o problema a um menor e possibilitando o uso da indução. Fica
>fácil ver o porquê da recorrência acima.
>
>Assim programa ficou com complexidade O(s) e encontrou rapidamente a
>solução.
>
>Para quem se interessar, o código em linguagem C ficou bem simples e segue
>abaixo :
>-----------[ inicio ]--------------------------
>#include <stdio.h>
>#define MAX 10000
>
>int T[MAX+1];
>
>int main() {
> int i;
>
> T[1]=1;
> printf("T(1) = 1\n");
> for(i=2; i<=MAX; i++) {
> T[i] = T[i-1]==1 ? i : T[i-1]-1;
> printf("T(%d) = %d\n", i, T[i]);
> if(T[i]==2001) break;
> }
> return 0;
>}
>-------------------[ fim ]-------------
>
>Um abraço
>
>[ Vinicius José Fortuna ]
>[ vinicius.fortuna@ic.unicamp.br ]
>
>
>On Wed, 1 Jan 1997 ezer@ig.com.br wrote:
>
> > Um que foi enviado para esta lista ha algum tempo pela Fernanda (ola!),
>foi
> > o do baralho - que nao eh explicitamente um problema de computacao, mas
> > claramente um problema algoritmico.
> >
> > >Olá,gostaria de ajuda nesta questão:
> > >
> > >Temos um baralho especial de cartas. As cartas são numeradas e estão
> > >colocadas por ordem.A nº 1 é a que está por baixo,a nº 2 está por cima
>da
> > >nº
> > >1,e assim sucessivamente.Carta de nº mais alto é a que está por cima.O
> > >total de cartas é inferior a 5000.Toma-se a carta superior e coloca-se
>sob
> > >o
> > >baralho.Pega-se na seguinte,q sai fora do jogo.A nova carta superior do
> > >baralho é colocada sob o baralho e a seguinte sai fora do jogo.E
> > >continua-se
> > >assim até q resta apenas uma carta,que por sinal, tem o nº 2001.
>Quantas
> > >cartas tinha o baralho?
> > >Obrigada!
> > >Fê
> >
> > Nesse momento estou tentando resolve-lo
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================
_________________________________________________________________
Tenha você também um MSN Hotmail, o maior webmail do mundo:
http://www.hotmail.com/br
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================