Блог пользователя waidfj

Автор waidfj, история, 4 часа назад, По-английски

Hello! I was studying Josephus Problem (in a circle of n people, each round the kth person is killed until one person is left, find out who survives)

I am aware of the O(n) solution, the recursive and the iterative solutions. I understand that the survivor of the circle is obtained from getting the survivor of the smaller cicle and adjusted by k positions.

However I just found the O(klogn) solution on cp algorithms. I understand that we are skipping n/k steps when k is less than n to save time but I don't understand how is the value of it is adjusted to give the answer for the current circle size?

Would someone be able to help me on this point please?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится