Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.
Определить
a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;
b) номер человека c которого начинался счет, если известно M и номер оставшегося человека L.

можно определить за количество итераций меньше O(N)?

С уважением, Naf

RT183.1Если m = 2, то можно найти так:
n записывается в бинарном виде, делается left rotate на одну позицию,
полученное число и будет ответом. Например,
как получили, если не секрет?

RAndrewNaf
можно определить за количество итераций меньше O(N)?


Определяется за O(N-1) итераций, следуя описанному а формулировке задачи алгоритму :)такого понятия нет, точнее это все равно O(N)

JartisanRT183.1> как получили, если не секрет?

плин, вычитал конечно где-то (не сам ведь открыл ) To get a(n), write n in binary, rotate left 1 place.

Могу ошибаться за давностью чтения, но по моему это подробно разбирается в "Конкретной математике" Кнута и Ко. называется задача Иосифа Флавияточно! и как всегда выручает вики: http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%98%D0%BE%D1%81%D0%B8%D1%84%D0%B0_%D0%A4%D0%BB%D0%B0%D0%B2%D0%B8%D1%8F