Хороший связанный список с большим N

Question

Если у нас есть круговой связанный список такой, что:

и код:

Int SO(LIST *L)
{
  While (L->next != L){
       L->next=L->next->next;
        L=L->next;
                       }

   return L->Data;

}

я хочу рассчитать вывод кода выше с n=729, n=2200?

я думаю, что это именно из http://en.wikipedia.org/wiki/Josephus_problem проблемы. как я должен рассчитать выход и что такое выход.

кто-нибудь может мне помочь?

Answer 1

Если я правильно понял проблему, это обобщение известной загадки.

При каждом обходе связанного списка вы удаляете половину элементов. Итак, подумайте о ситуации, когда n является степенью 2.

В этом случае первый узел никогда не будет удален, и ответ будет 1.

Следовательно, при первом обходе после каждого удаления просто проверяйте количество оставшихся узлов. Если число оставшихся узлов является степенью двойки, то текущие L-данные должны быть ответом.