Josephus problem (recursive)

Question

Josephus problem (recursive)

Navigation

#1 by (1 votes)
#2 by (0 votes)

8

This is the recursively rendered resolution of the Josephus problem , where n is equal to the number of people in the circle, and k is the step number to be given to the next person.

#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;
}

As you can see the algorithm works, however I would like to know how it works, I did not understand how it arrives at the end result.

My problem is with f(n, k) = (f(n-1, k) + k-1)%n + 1) , I wonder how this can return the value corresponding to the last person to stay alive in the circle. I would also like to know what each return value of f(n-1, k) with each recursion means, because for me the only one that makes sense is the last, which is the end result.

c++

asked by anonymous 19.03.2015 / 16:52

2 answers

What is salt when it comes to password encryption? How to add more products?

score 1 · Answer 1

The value of f(n-1, k) is the position of the person to be saved with one less person, that is, the solution to the previous problem.

Example on Ideone

The program does the problem calculations, starting from the simplest problem to the final problem.

Basically, the solution to the problem is a sequence of consecutive odd numbers, which returns to 1 always that the number of people in the circle is a power of 2.

The result sequence is 1 (1), 1 (2), 3 (3), 1 (4), 3 (5), 5 (6), 7 (7), 1 (8 ), 3 (9), 5 (10) ...]

But this sequence is only when k = 2 . For k > 2 The sequence is different.

score 0 · Answer 2

I did not follow the example, I'm not going to say it's right or not, but let's talk about recursion quickly. I think this is the problem of understanding. When you make a recursive call the function checks whether the result can be found or whether to make a new call. If you make a new call, the system will stack the previous call, which is the same as when function A calls function B, A is waiting for the return of B to continue executing. But in the case of recursion the call is for the same function. When the value reaches 1 it is returned and the previous call can be calculated and also returns its result to the previous call. This happens successively until you reach the initial call that returns the value for printing.