Задача: "Считалка". Приемлемое решение?
От: TheGrey Украина http://www.uoi.kiev.ua
Дата: 26.11.02 09:04
Оценка:
Здравствуй, All!

Задача. Вокруг ведущего стоят N человек, один из которых считается первым, а остальные пронумерованы по часовой стрелке начиная с первого и т.д. до N-го. Ведущий отсчитывает, начиная с первого, M человек. Тот, на ком остановится счет — выбывает из круга. Ведущий продолжает счет со следующего от выбывшего человека. Необходимо определить по двум числам M и N номер человека, который останется в круге последним.

Кто-нибудь знает какое наилучшее найденное решение для этой задачи? Я знаю два: одно использует структуру данных кольцо, и моделирует счет; другое — линейное по N и не использует дополнительной памяти.

Может кому-то встречались ссылки на исследование этой задачи?

Заранее благодарен.


16.01.03 23:38: Перенесено из 'Алгоритмы'
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.