Помогите решить задачу на python
Друзья, всех приветствую. В Учебе столкнулся с такой задачей:
Есть N кол-во человек, стоящих условно в кругу. начинается считалка с K кол-вом тактов. То есть - каждый K-й человек выбывает и считалочка начинается со следующего после выбывшего.
Самый простой пример, чтобы было проще понять:
Есть пять человек и считалочка в два такта. первый-второй = выбывает второй. Далее третий-четвертый = выбывает четвертый. Далее пятый-первый = выбывает первый.
По условиям задачи нужно вывести номер того, кто останется. В данном выше примере им будет третий, то есть выводом будет просто 3.
итак, на вход поступает два числа - первое N и второе K, оба от 1 до 500.
Решить задачу нужно и рекурсией и циклом. с циклом проблем не вижу, а вот с рекурсией такая беда. Все тесты проходит, кроме одного, когда на вход поступают числа 500 и 500. Мой код выводит 271, а должен вывести 69.
Надеюсь сможете мне помочь)
Хорошего всем дня!
НЕОБЯЗАТЕЛЬНО К ПРОЧТЕНИЮ:
Друзья, в коде мне нужно было увеличивать счетчик на одно и то же число при каждом вызове функции, но я не знал, как записать это число так, чтобы оно соответствовало аргументу в функции - takt, но не изменялось вместе с ним с каждым вызовом функции, поэтому на первое время я использовал константу. Подскажите пожалуйста способ получше)
Помимо этого, буду рад услышать и другие замечания к коду. Всем спасибо
Конечно, я могу помочь вам с этой задачей. Примеры рекурсивного решения подобных задач могут быть сложными, и иногда проще использовать циклы для более эффективного выполнения.
Вот пример простого циклического решения задачи:
```python
def find_survivor(N, K):
people = list(range(1, N + 1))
current_index = 0
while len(people) > 1:
current_index = (current_index + K - 1) % len(people)
del people[current_index]
return people[0]
# Пример использования
N = 500
K = 500
result = find_survivor(N, K)
print(result)
```
Этот код создает список людей с номерами от 1 до N и затем с помощью цикла "считает" в кругу, удаляя каждый K-й элемент, пока не останется только один человек.
Если вы все равно хотите использовать рекурсию, вот пример:
```python
def find_survivor_recursive(N, K):
if N == 1:
return 1
else:
return (find_survivor_recursive(N - 1, K) + K - 1) % N + 1
# Пример использования
N = 500
K = 500
result = find_survivor_recursive(N, K)
print(result)
```
Обратите внимание, что рекурсивное решение может быть менее эффективным, чем циклическое, из-за глубины рекурсии при больших значениях N и K.