Обезглавливание рыцарей, которые выживают?

  

У нас есть круглый стол рыцарей n, где n - некоторый положительный   целое число. Они не оправдали ожиданий безумного короля   и приговорены к смертной казни. Однако, как акт милосердия, он оборачивается   стол, убивающий каждого другого рыцаря (начиная со второго)   пока не останется только один рыцарь.

     

Вопрос: какое место вам нужно выбрать, чтобы выжить?

Я написал примитивный код ниже, чтобы решить эту проблему:

while True:
    temp_num = input("Enter the number of knights: ")
    try:
        temp_num = int(temp_num)
        if temp_num <= 0:  # if not a positive int print message and ask for input again
            print("Sorry, the number of knights must be a positive integer, try again")
        else:
            knights_num = temp_num
            break
    except ValueError:
        print("That's not an integer!")     
# else all is good, val is >=  0 and an integer

# Create a table of knights and a temp table
knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

i = 1
while len(knights_temp_table)>1:
# print("Knights =",knights_temp_table , "(",knights_temp_table[i],")")
    knights_temp_table.pop(i)
    i = (i+1)%len(knights_temp_table)
print( "The knight who survived was no.",knights_temp_table[0] )

Код работает нормально и выводит ожидаемые значения n=60> 57 и n=16 > 1 Однако из кода не ясно почему он работает. Итак, у меня были некоторые вопросы ниже

  • Можно ли сделать таблицу рыцарей с помощью генератора?
  • Является ли код с помощью try knights_temp_table[i+1] и knights_temp_table[i+2], а затем итерации по списку для исключения понятнее?
  • Можно ли реализовать связанный список, чтобы сделать код более понятным, а не по модулю?

Я знаю, что код очень прост и проблема, которую я решил почти тривиально. Тем не менее, любые предложения сильно усугубляются, так как я полузанялся /начинал на python.  * Существуют ли какие-либо другие общие рекомендации по улучшению кода или скорости работы?

37 голосов | спросил N3buchadnezzar 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 14 Sep 2015 17:50:21 +0300 2015, 17:50:21

4 ответа


28

Использовать функцию

Вы можете переместить весь цикл ввода в функцию. Назовите это чем-то разумным:

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
            if num <= 0:  # if not a positive int print message and ask for input again
                print("Sorry, the number of knights must be a positive integer, try again")
            else:
                return num
        except ValueError:
            print("That's not an integer!")             

Это хорошо по двум причинам: модульность всегда хороша, и теперь вам не нужно беспокоиться о столкновениях имен. Просто используйте num внутренне и return, когда закончите.

Два списка

Это:

knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

делает два list s. Первое - это понимание списка, которое создает список list, второй просто копирует его. Нет причин для дублирования. Кроме того,

range(1, knights_num + 1)

уже является списком в python2.7. В python3 это не так, но вы не отметили эту версию, но используете скобковый print.

Ноль индексации

Python индексируется нулем. Первым элементом списка lst является lst[0], а не lst[1]. Когда вы поместите первый элемент, вам нужно сделать pop(0) not pop(1). По этой причине ваш цикл pop() отключается по одному - вы начинаете со второго рыцаря вместо первого.

Улучшенное решение

knight_table = list(range(get_num_knights()))
i = 0
while len(knight_table) > 1:
    knight_table.pop(i)
    i = (i+1) % len(knight_table)
print( "The knight who survived was no.", knights_temp_table[0]+1 )

Избегание pop()

Теперь, для особо длинного числа рыцарей, возможно, что время pop() может доминировать над вашим временем выполнения кода. pop() является линейным временем в конце концов - мы должны перемещать элементы по одному. Таким образом, возможно, что следующее может работать лучше:

num = get_num_knights()
knight_table = [True] * num
i = 0
while num > 1:
    knight_table[i % len(knight_table)] = False
    num -= 1

    living = 0
    while living < 2:
        i += 1
        living += knight_table[i % len(knight_table)]

print( "The knight who survived was no.", i % len(knight_table))
ответил Barry 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 14 Sep 2015 18:07:14 +0300 2015, 18:07:14
50

Эти бедные рыцари ... что они сделали, чтобы заслужить это?

Но есть математическое рассмотрение, позволяющее решить эту проблему в O (1) время и пространство.

Что это значит? Это означает, что решение проблемы для 1-го рыцаря длится так же долго (и столько же памяти), как и решение для 10 или 1000, или 1000000000000000 рыцарей. Как это возможно?

Есть образец, который возникает, когда вы изучаете эту проблему. Если есть 1 рыцарь, то рыцарь 1 выживает. Если есть 2, то рыцарь 1 выживает, и, если мы наберем это, скажем, первые 32 рыцаря, получим:

1 -> 1
2 -> 1
3 -> 3
4 -> 1
5 -> 3
6 -> 5
7 -> 7
8 -> 1
9 -> 3
10 -> 5
11 -> 7
12 -> 9
13 -> 11
14 -> 13
15 -> 15
16 -> 1
17 -> 3
18 -> 5
19 -> 7
20 -> 9
21 -> 11
22 -> 13
23 -> 15
24 -> 17
25 -> 19
26 -> 21
27 -> 23
28 -> 25
29 -> 27
30 -> 29
31 -> 31
32 -> 1

Обратите внимание, что у сил-2 выживший рыцарь возвращается к рыцарю 1. Кроме того, между силами выживший рыцарь увеличивается на 2 (и всегда нечетно).

Шаблон также легко перечислить - найдите наибольшую мощность 2, которая меньше (или равна) счетчику. Найдите, сколько рыцарей есть после этой силы, удвойте его и добавьте.

Это будет выглядеть так:

import math

def low_power(input):
    return 1 << int(math.floor(math.log(input, 2)))

def survivor(count):
    return 1 + 2 * (count - low_power(count))

Итак, вызов survivor(16) вернется 1. survivor(60) возвращает 57.

Но теперь вы можете делать сумасшедшие цифры, например, survivor(98765432123456789) - 53415676171057707

Смотрите этот код на ideone: Рыцари

Обратите внимание, что вы подтвердили, что используете Python 3.4. Python 3.1 представил bit_length() . Это значительно упрощает определение мощности (с точки зрения программирования - битовая длина может рассматриваться как реализация журнала 2 ):

def low_power(input):
    return 1 << (input.bit_length() - 1)

Тот же код, выполняющий bit_length в python 3, показан здесь в ideone (также содержит правильную скобку для операторов печати python 3).

ответил rolfl 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 14 Sep 2015 19:52:10 +0300 2015, 19:52:10
17

Помните, что это круглый стол. Итак, если это круглый стол ... что лучше использовать, чем круговой буфер?

from collections import deque

knights_table = deque(range(1, knights_num + 1))

Затем вы можете эмулировать это гораздо проще:

while len(knights_table) != 1:
    knights_table.popleft()   # killed
    knights_table.rotate(-1)  # skipped

print("The knight who survived was no.", knights_table.pop())

Одно большое преимущество (кроме простоты), а pop(i) - O(i) = O(n) для list s, popleft() и rotate(-1) являются O(1) для deque s.

knights_num должен быть извлечен в функцию, как упоминалось выше. Однако этот код несовершенен:

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
            if num <= 0:  # if not a positive int print message and ask for input again
                print("Sorry, the number of knights must be a positive integer, try again")
            else:
                return num
        except ValueError:
            print("That's not an integer!")    

Ваш try охватывает гораздо больше, чем нужно, что опасно. Ограничьте его охват. Лично я также делал if not <wanted condition>, а не if <problematic condition>, поскольку белые списки обычно более простые и безопасные, чем черные списки. YMMV.

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
        except ValueError:
            print("That's not an integer!")
            continue

        if not num > 0:  
            print("Sorry, the number of knights must be a positive integer, try again.")
            continue

        return num
ответил Veedrac 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 00:03:14 +0300 2015, 00:03:14
10

Я отвечу на ваши вопросы, а затем даю более общие советы.

  1. То, как вы могли бы использовать генератор для этого, в любом случае включало бы список. Действительно, это не тот случай, когда генераторные выражения необходимы в любом случае, поскольку списки будут довольно маленькими и не занимают много места.

  2. Возможно, но я думаю, что умное решение хорошо, и вы должны просто объяснить это в комментариях. try except, становится грязным, а не полностью очистить либо, так как вы увеличиваете на 1, когда вам кажется, что вы должны подняться на 2 секунды, чтобы пропустить все остальные.

  3. Связанные списки обычно не используются в Python, поэтому я в основном ссылаюсь также на ответ 2.


Теперь для общих советов. Вам не следует использовать временные переменные, когда вам это не нужно. Нет никакой реальной причины для разделения temp_num и knights_num здесь. Возможно, вам уже понадобилось, но ваш текущий код не герметичен без него.

Кроме того, хорошо иметь как можно меньше строк в блоке try. Иногда во избежание ошибок, но и для хорошей читаемости. Вы можете использовать ключевое слово continue в своем предложении except, а затем переместить остальные строки ниже. Также я бы перевернул ваш if. Если номер действителен, вы можете break. В противном случае объясните, что число должно быть положительным. Таким образом, ваш print не должен находиться в блоке else.

Итак, вот как я переписал это открытие:

while True:
    knights_num = input("Enter the number of knights: ")
    try:
        knights_num = int(knights_num)
    except ValueError:
        print("That's not an integer!")
    if knights_num > 0:
        break
    print("Sorry, the number of knights must be a positive integer, try again")

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

Теперь у вас много избыточности:

knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

Для начала вы можете напрямую присваивать range список без понимания списка. Вам также не нужно делать копию knights_table, потому что вы используете только одну из этих переменных позже. Итак, снова отрежьте временную переменную.

ответил SuperBiasedMan 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 14 Sep 2015 18:56:29 +0300 2015, 18:56:29

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132