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.