Почему в этом решении используется остаток для деления?
Есть такая задача и есть ее, на мой взгляд, очень хорошее решение. Сама задача:
N человек, пронумерованных числами от 1 до N, стоят в кругу. Они начинают играть в считалку на выбывание, где каждый K-й по счёту человек выбывает из круга, после чего счёт продолжается со следующего за ним человека. На вход подаётся количество человек N и номер K. Напишите программу, которая выводит число от 1 до N — это номер человека, который останется в кругу последним.
Решение:
number = int(input('Какое число в считалке? '))
print('Значит, выбывает каждый', number, 'человек.')
mens_list = list(range(1, num + 1))
out = 0
for _ in range(num - 1):
print('Текущий круг людей', mens_list)
start_count = out % len(mens_list)
out = (start_count + number - 1) % len(mens_list)
print('Начало счёта с номера', mens_list[start_count])
print('Выбывает человек под номером', mens_list[out])
mens_list.remove(mens_list[out])
print()
print('Остался человек под номером', mens_list)
Суть вопроса: Как начинающему понять, что для решения задачи подошла бы формула out = (start_count + number - 1) % len(mens_list) с остатком от деления?
Можете объяснить логику размышлений именно для написания такой формулы, а не для кода?
Ответы (2 шт):
Не совсем понятно, что вы понимаете под "как понять". Как догадаться, что здесь пригодится остаток? Очень просто - накопить опыт.
Почему используется остаток: потому что в данном случае нас не интересует какое количество полных кругов пройдет считалка.
Если в круге N человек и выбывает каждый k-ый, то номер этого выбывшего Nv и будет как раз остаток от деления N на k: N = x*k + Nv, где x - количество полных кругов и оно нас совершенно не интересует, сколько бы их ни было, на результат это не влияет.
На часах было 12:45, затем затем 46 минут, затем час и 7 минут. Сколько минут на часах?
((12 * 60 + 45) + 46 + (1 * 60 + 7)) % 60
тут тот же принцип
поскольку движение по кругу, используем модулярную арифметику
т.е. сначала вычисляется некоторая абсолютная позиция человека как start_count + number - 1, а затем через определения модуля по кол-ву человек (len(mens_list)) ее относительная позиция в круге