CODEWITHSUNDEEP
mathrecurrencejosephus
Green goblin
Green goblin

Reputation: 9996

Recurrence relation in Josephus p‌r‌o‌b‌l‌e‌m

The josephus problem can be solved by the below recursion: 

 josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
 josephus(1, k) = 1

How this recurrence relation has been derived?

Upvotes: 3

Views: 1920

Answers (2)

user1412066
user1412066

Reputation: 155

josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1 ...... (1)

To put it in simple words - starting with the "+1" in the formula. It implies that 1 iteration of the recurrence has already been done. Now, we would be left with n-1 persons/elements. We need to process n-1 elements recursively at intervals of k. But, now, since the last element to be removed was at kth location, we would continue from thereof. Thus, k-1 added. Further, this addition might upset the indexing of the array. Thus %n done to keep the array index within the bounds. Hope it is lucid and elaborate enough :) .

Upvotes: 1

Bhavuk Mathur
Bhavuk Mathur

Reputation: 1078

This paragraph is sufficient from wikipedia..

When the index starts from one, then the person at s shifts from the first person is in position ((s-1)\bmod n)+1, where n is the total number of persons. Let f(n,k) denote the position of the survivor. After the k-th person is killed, we're left with a circle of n-1, and we start the next count with the person whose number in the original problem was (k\bmod n)+1. The position of the survivor in the remaining circle would be f(n-1,k) if we start counting at 1; shifting this to account for the fact that we're starting at (k\bmod n)+1 yields the recurrence

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,

Upvotes: 0

Related Questions