PERMUTAÇÃO DE JOSEPHUS
- Author:
- LISBETE MADSEN BARBOSA
O Problema de Josephus é um problema clássico no estudo de computação:
São n pessoas (numeradas de 1 a n) sentadas em círculo e a partir da pessoa 1, conta-se k pessoas. A pessoa onde caiu a contagem é retirada do círculo e recomeça-se a contagem de k pessoas a partir da pessoa seguinte. Novamente, a pessoa onde caiu a contagem é retirada e recomeça-se a contagem de k pessoas a partir da pessoa seguinte. O processo é repetido até retirarmos todas as n pessoas do círculo.
A ordem em que as pessoas são removidas do círculo define a permutação de Josephus(n,k) dos inteiros 1,2,3...,n.
Por exemplo, a permutação de Josephus(7,3) é (3,6,2,7,5,1,4).
Problema:
Dados n, k, inteiros positivos, k menor que ou igual a n, obter a permutação de Josephus(n,k).
Um problema semelhante:
Se o processo de remoção é repetido até restar uma única pessoa, qual a pessoa sobrevivente?
![No livro Algoritmos teoria e prática, de Cormen e outros, 3[sup]a [/sup]ed. capítulo 14 - Aumentando estruturas de dados, problema 14-2, pg 260.](https://beta.geogebra.org/resource/nD8Dp27a/WRPqj2zOweuiRcSr/material-nD8Dp27a.png)