8

Esta é a resolução, feita de forma recursiva em C++, do problema de Josephus, onde n é igual ao numero de pessoas no círculo, e k é o numero do passo a ser dado para a próxima pessoa.

#include <iostream>

using namespace std;

int f(int n, int k){
    if(n==1) return 1;
    return (((f(n-1, k) + k-1)%n)+1);   
}

int main(){
    unsigned int n, k;
    cin >> n >> k;
    cout << f(n, k) << endl;
}

Como podem ver o algoritmo funciona, porém eu gostaria de saber como o mesmo funciona, eu não entendi como ele chega no resultado final.

Meu problema é com f(n, k) = (f(n-1, k) + k-1)%n + 1), gostaria de saber como pode isto retornar o valor correspondente à última pessoa a ficar viva no círculo. Gostaria de saber também o que cada valor de retorno de f(n-1, k) a cada recursão significa, pois para mim o único que faz sentido é o ultimo, que é o resultado final.

2 Respostas 2

1

O valor de f(n-1, k) é a posição da pessoa a ser salva com uma pessoa a menos, isto é, a solução do problema anterior.

Exemplo no Ideone

O programa faz os cálculos do problema, começando do problema mais simples até o problema final.

Basicamente, a solução do problema é uma sequência de números ímpares consecutivos, que volta a 1 sempre que o número de pessoas no circulo for uma potência de 2.

A sequência de resultados é [1(1), 1(2), 3(3), 1(4), 3(5), 5(6), 7(7), 1(8), 3(9), 5(10)...]

Mas essa sequência é somente quando k = 2. Para k > 2 a sequência é diferente.

4
  • Não consegui entender, você esta dizendo que o numero de retorno é a posição da pessoa com relação a quantas a no circulo na recursão atual? Commented 19/03/2015 às 19:32
  • Exatamente isso.
    – mutlei
    Commented 19/03/2015 às 21:00
  • Acredito que não seja isso, eu fiz manualmente todos os retornos e eles não batem com a pessoa que deveria ser retirada naquela vez, e chega um ponto que até o 5 é retirado nesta logica... Commented 20/03/2015 às 13:51
  • Editei a resposta.
    – mutlei
    Commented 20/03/2015 às 14:26
0

Eu não rodei o exemplo não vou afirmar que esteja certo ou não, mas vamos falar rapidamente sobre recursão. Acho que esse é o problema de entendimento. Quando você faz uma chamada recursiva a função verifica se o resultado pode ser encontrado ou se deve fazer uma nova chamada. Se fizer uma nova chamada o sistema empilha a chamada anterior, é o mesmo que acontece quando a função A chama a função B, A fica esperando o retorno de B para continuar executando. Só que no caso da recursão a chamada é para a mesma função. Quando o valor chega a 1 é retornado e a chamada anterior pode ser calculada e retorna também seu resultado para a anterior. Isso acontece sucessivamente até chegar na chamada inicial que retorna o valor para impressão.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .