Логическая ошибка в последовательности 011212201 вопроса
Я пытаюсь решить следующую задачу:
Пример последовательности 011212201220200112... строится следующим образом:
Первый элемент последовательности равен 0.
Для каждой итерации повторите следующее действие: возьмите копию всей текущей последовательности, замените 0 на 1, 1 на 2 и 2 на 0 и поместите ее в конец текущей последовательности. Например. 0 -> 01 -> 0112 -> 01121220 -> ...
Создайте алгоритм, который определяет, какое число находится на N-й позиции в последовательности (с использованием индексации, отсчитываемой от 0).
Вход
Ваша программа должна читать строки из стандартного ввода. Каждая строка содержит целое число N такое, что 0 <= N <= 3000000000.
Выход
Выведите число, которое находится на N-й позиции в последовательности.
Я увидел логику и реализовал ее следующим образом:
def find_nth_element(N):
result = 0
while N > 0:
N -= 1
result = (result + 1) % 3 if N % 2 == 1 else result
N //= 2
return result
import sys
for line in sys.stdin:
N = int(line.strip())
print(find_nth_element(N))
Однако тестовые примеры с этим не справились.
Например, когда входное значение равно 11, ожидаемый результат — 0, но мой код возвращает 1.
Я думал, что уловил необходимую логику. Где моя ошибка?
Ответы 1
Логика многократного деления данного ввода на 2 действительно правильная, но ошибка в N -= 1.
Если число, которое нужно разделить на 2, нечетное, то целочисленное деление предполагает игнорирование 1, которая делает делимое нечетным, но:
- В этом нет необходимости, если в вашем распоряжении есть оператор целочисленного деления (
//), который вы используете - Даже если вы вычтете эту 1, это должно произойти только тогда, когда число нечетное, и это должно произойти только непосредственно перед делением, а не до того, как вы проверите четность, чтобы адаптировать результат.
В любом случае, чтобы исправить вашу попытку, вам просто нужно удалить этот оператор:
N -= 1
Другие замечания
Еще несколько замечаний по поводу этого алгоритма:
1. Сокращение кода
По сути, алгоритм добавляет единицу к результату (модуль 3) на каждую единицу в двоичном представлении N. Таким образом, вы можете использовать собственный метод bit_count, чтобы подсчитать их все:
def find_nth_element(N):
return N.bit_count() % 3
2. Тестирование вашего решения
Чтобы проверить свое решение самостоятельно, не полагаясь на какого-либо онлайн-судью, вы можете реализовать функцию, которая генерирует описанную последовательность.
def gen():
lst = [0]
i = 0
while True:
if i >= len(lst):
lst += [(i + 1) % 3 for i in lst]
yield lst[i]
i += 1
С его помощью вы можете написать цикл, который проверяет ваше решение и, если что-то не так, печатает первый ввод, для которого оно не удалось:
for n, expected in enumerate(gen()):
res = find_nth_element(n)
if res != expected:
print("wrong result for n = ", n)
break
if n > 1000:
print("The first 1000 inputs were verified")
break
Приятного кодирования!