Josephus

["Michel Leonard Goldstein" <mgoldstein@mailbr.com.br>]

Olá,

    Encontrei uma solução para o Problema de Josephus... Ela não entra para
o concurso dos Toblerones, pois é dependente de m, mas estou colocando aqui,
pois é a que menos gasta memória das que eu consegui descobrir...

    A idéia por trás da solução é que os mortos iniciais são os múltiplos de
m, mas quando i.m > n, deve-se subtrair n e somar o número de mortos entre a
primeira pessoa e a pessoa (i.m - n). O valor dessa quantidade a ser somada
pode ser retirada do fato que (supondo ainda que i.m < 2n) deve-se somar uma
pessoa quando existir um múltiplo de m que existir neste intervalo e mais 1
a cada intervalo de m vivos (retirando os múltiplos de m), pois esses já
devem ter sido retirados.
    Esta "transformação" é conseguida aplicando a fórmula (retirada fazendo
alguns cálculos e através de algumas observações empíricas):

    x = floor(m(x-n)/(m-1) - 1/(m-1))

    onde x inicialmente é iniciado como x = i.m e é o número da pessoa a ser
morta.

    Até agora, aparentemente, esta observação só serviria para i.m < 2n,
mas, fazendo um pouco mais de cálculo, é possivel observar que, se após a
primeira aplicação da equação x > n, pode-se aplicar novamente ela até que o
valor caia no intervalo desejado. Sem números, este resultado se deve ao
fato de, quando é subtraído pela primeira vez n, é somada a "correção". Se
este valor não estiver no intervalo de pessoas possivelmente vivas, ao
aplicar a correção novamente, essas correções se somam caindo no intervalo
desejado (soma 1 a cada múltiplo de m, mais 1 a cada múltiplo de m nos que
restaram, e assim por diante).

    Bom, qualquer pergunta ou sugestão sobre o algoritmo (por exemplo, como
gerar a próxima pessoa a partir da anterior sem ter uma expressão de tamanho
crescente e, portanto, de tempo de processamento também crescente) é só
fazer!

    Aí vai o programa (que repito, não atende as especificações do concurso
valendo os Toblerones):

#include <stdio.h>

main()
{
  int n,x,i,m;
  printf("\n\n   SOLUCAO DO PROBLEMA DE JOSEPHUS \n\n");
  printf("Entre com o numero de pessoas (n): ");
  scanf("%d",&n);
  printf("Entre com o valor do \"passo\" (m): ");
  scanf("%d",&m);
  printf("\n A sequencia de pessoas a serem mortas é:\n");
  for (i=1;i<=n;i++)
  {
    x=m*i; // se n fosse infinito seria a i-esima pessoa a ser morta
    while (x>n)  // ajusta x enquanto x > n
      x=(m*(x-n)-1)/(m-1); // arredonda para baixo!
    printf("%d, ",x);
  }
  printf("\b\b.\n\n");
  return(0);
}

    É isso aí!

[]'s
Michel Leonard Goldstein