Линейное изменение головоломки Иосифа - PullRequest
Новая
       25

Линейное изменение головоломки Иосифа

1 голос
/ 12 ноября 2010

Итак, вот проблема Иосифа на вики.Проблема, которая у меня есть, - это линейная вариация, но для ясности я переформулирую всю проблему.

(Числа = Натуральные числа)

Существует процесс, который устраняет числа вследующим образом: 

i=2
while 1:
    remove numbers that are *placed* at positions divisible by i
    i+=1

Вам также дается номер K, вы должны подтвердить, выживет ли этот номер K после исключения.

Например (при условии, что индекс начинается с 0) 

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
0,1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15 ...  (indices)

After step 1 ( elimination at i=2 )
2,4,6,8,10,12,14,16 ... 
0,1,2,3, 4, 5, 6, 7 ... (indices)

After step 2 (elimination at i=3 )
2,4,6,10,12,16 ... ( 8 and 14 got removed cause they were at index 3 and 6 resp. )
0,1,2, 3, 4, 5 ... (indices)

Как мы видим, 2,4,6 являются safe после этого шага, поскольку процесс будет выбирать все более и более высокие значения для исключения.

Итак, еще раз,учитывая K как вы определяете, будет ли K safe?

Ответы [ 2 ]

2 голосов
/ 12 ноября 2010

Вопрос не проясняет, что именно происходит с числом в позиции 0. В примере на шаге 1 число 1 (в позиции 0) исключается. Но затем на шаге 2 число 2 (в позиции 0) выживает.

В этом ответе я предполагаю, что пример ошибочен, а число в позиции 0 всегда сохраняется. Так что пример должен выглядеть так:

Исходная позиция 

 Number    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

После шага 1: 

 Number    1  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 32 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

После шага 2: 

 Number    1  2  4  8 10 14 16 20 22 26 28 32 34 38 40 44 46 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

Это приводит к последовательности 1, 2, 4, 8, 14, 20, 28, 40, ... которая не найдена в OEIS (но см. Добавление ниже).

Вот как вы можете определить, выживет ли конкретное число K, не вычисляя всю последовательность:

Пусть J₁ = K - 1 (начальная позиция K).

  • K исключается на шаге 1, если J₁> 0 и 2 | J₁, но если нет, его новый индекс составляет J₂ = J₁ - ⌊J₁ / 2⌋
  • K исключается на шаге 2, если J₂> 0 и 3 | J₂, но если нет, то его новый индекс составляет J₃ = J₂ - ⌊J₂ / 3⌋
  • и так далее, пока либо K не будет устранено, либо пока Ji

ДОПОЛНЕНИЕ

Я немного поспешил, когда пришел к выводу, что эта последовательность отсутствует в OEIS. Предположим, что мы пронумеровали позиции, начинающиеся с 1, а не с 0. Затем мы получили бы последовательность 1, 3, 7, 13, 19, 27, 39, ..., которая представляет собой последовательность OEIS A000960 , "Сито Флавия Иосифа". Тем не менее, пока нет решения в закрытой форме.

2 голосов
/ 12 ноября 2010

Одним из решений является отслеживание индекса K в списке на каждой итерации.

На каждом шаге мы сначала проверяем, делится ли индекс K на. Если это так, мы возвращаем false. В противном случае мы просто вычитаем количество элементов перед K, которые делятся на i, из индекса K (то есть K сдвигается так много раз влево).

Мы продолжаем делать это, пока не останется только один элемент.

...