Алгоритм Иосифа частичного успеха

Question

Мой друг рассказал мне о проблеме Иосифа, где у вас есть 41 люди сидят в кругу. Номер человека 1 имеет меч, убивает человека справа и передает меч следующему человеку. Это продолжается до тех пор, пока не останется в живых только один человек. Я пришел с этим решением в Python:

print('''There are n people in the circle. You give the knife to one of 
       them, he stabs person on the right and
       gives the knife to the next person. What will be the number of whoever
       will be left alive?''')

pplList = []
numOfPeople = int(input('How many people are there in the circle?'))


for i in range(1, (numOfPeople + 1)):
    pplList.append(i)
print(pplList)

while len(pplList) > 1:
    for i in pplList:
        if i % 2 == 0:
            del pplList[::i]
    print(f'The number of person which survived is {pplList[0]+1}')
    break

Но это работает только до 42 люди. Что я должен сделать, или как я должен изменить код, чтобы он работал, например, 100, 1000 и больше людей в кругу?

Я посмотрел на проблему Иосифа и нашел другие решения, но мне любопытно, может ли мой ответ быть правильным после некоторой незначительной корректировки или я должен начать с нуля.

Answer 1

Я вижу две серьезные ошибки.

1. Я гарантирую, что del ppList[::i] не делает ничего похожего на то, что вы надеетесь сделать.
2. Когда вы обернетесь вокруг круга, важно знать, убили ли вы последнего человека в списке (снова убивает первый в списке) или нет (первый человек в списке умирает).

И вопреки вашему утверждению, что он работает до 42, он не работает для многих меньших чисел. Первое, для чего он не работает - это 2. (Это дает 3 в качестве ответа вместо 1.)

Answer 2

Проблема в том, что вы не рассматриваете парня в конце концов, если его не убьют. Например, если есть 9 человек, после убийства 8 у 9 есть меч, но вы только начинаете с 1, а не с 9 в следующем цикле. Как уже упоминалось, это не работает и для меньших чисел. На самом деле, если вы присмотритесь, вы убиваете нечетные числа в самом первом цикле вместо четных. что очень неправильно.

Вы можете исправить свой код следующим образом

while len(pplList )>1:
    if len(pplList )%2 == 0:
        pplList  = pplList [::2] #omitting every second number
    elif len(pplList )%2 ==1:
        last = pplList [-1] #last one won't be killed
        pplList  = pplList [:-2:2]
        pplList .insert(0,last) # adding the last to the start

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