Статья Автор: Лебедев Дмитрий

TUZ_5-06 Достижение стабильного состояния в распределении конфет

TUZ_5-06_ Достижение стабильного состояния в распределении конфет

TUZ_5-06_ Достижение стабильного состояния в распределении конфет
5.6. Достижение стабильного состояния в распределении конфет
Группа детей сидит за круглым столом, и перед ними лежат конфеты. Все конфеты совершенно одинаковые.
Игра начинается с того, что воспитатель звонит в колокольчик.
  • После звонка каждый ребенок, у которого есть хотя бы две конфеты,
    должен отдать одну конфету ребенку слева и одну конфету ребенку справа.
  • Дети, у которых одна конфета или нет конфет, ничего не должны делать.
Согласно принципу Дирихле, если конфет больше, чем детей, то такое деление конфет никогда не завершится.
Ваша задача: написать функцию, которая принимает исходное распределение конфет и 
возвращает количество шагов, необходимых для достижения стабильного состояния.
В табл. 5.6 показаны ожидаемые результаты для некоторых входных данных. 
Таблица 5.6. Некоторые ожидаемые результаты для задачи подсчета шагов для достижения стабильного состояния в распределении конфет
Candies   Ожидаемый результат
0, 0, 0, 3 1
2, 0, 0, 1 2
2, 0, 0, 0, 0, 0, 4, 0, 1 8
0, 4, 0, 0, 0, 3, 0, 1, 0, 0 4
0, 0, 0, 5 None

Алгоритм
Алгоритм рекурсивно применяет набор правил ко входному списку конфет candies,
пока не будет достигнуто стабильное состояние, когда у каждого ребенка окажется не более одной конфеты.
В каждой итерации алгоритм идентифицирует элемент массива, в котором имеются две или более конфет,
и перекладывает по одной конфете в соседние элементы.
Этот процесс повторяется до тех пор, пока во всех элементах будет не более одной конфеты,
после чего алгоритм завершает работу и возвращает количество шагов,
потребовавшихся для достижения этого состояния.
Вот подробное описание шагов алгоритма.
  1. Принимается два параметра: candies – список целых чисел, представляющий количество конфет, 
    которые есть у каждого ребенка, и states (необязательный параметр) – целое число, 
    представляющее количество шагов, потребовавшихся программе для достижения текущего состояния
    (по умолчанию имеет значение 0).
  2. Проверяется, достигнут ли базовый случай. 
    Если количество детей, имеющих 0 или 1 конфету, равно общему количеству детей, 
    то возвращается количество шагов.
  3. Создается копия списка candies для текущего шага.
  4. Выполняется обход элементов в списке candies.
  5. Проверяется, есть ли у текущего ребенка хотя бы две конфеты.
  • Если да, то из соответствующего элемента удаляются две конфеты и
     в соседние элементы добавляется по одной конфете
    (т. е. передаются детям слева и справа).
  1. Вышеуказанные шаги продолжают выполняться рекурсивно
    с обновленным списком candies и увеличенным значением states.
  2. По достижении базового случая возвращается конечное значение states.
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать