Re: [obm-l] Algoritmos

[Vinicius José Fortuna <ra992559@xxxxxxxxxxxxx>]

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