День 6 — Перераспределение памяти
Это довольно простая задача, но нам нужно создать несколько вспомогательных функций…
Предыдущие части:
День 1
День 2
День 3
День 4
День 5
Проблема первая:
У программы-отладчика здесь возникла проблема: она пытается исправить процедуру перераспределения памяти, но продолжает застревать в бесконечном цикле.
В этой области имеется шестнадцать банков памяти; каждый банк памяти может содержать любое количество блоков. Целью процедуры перераспределения является балансировка блоков между банками памяти.
Процедура перераспределения работает в циклах. В каждом цикле он находит банк памяти с наибольшим количеством блоков (ничью выигрывает банк памяти с наименьшим номером) и перераспределяет эти блоки между банками. Для этого он удаляет все блоки из выбранного банка, затем переходит к следующему (по индексу) банку памяти и вставляет один из блоков. Это продолжается до тех пор, пока не закончатся блоки; если он достигает последнего банка памяти, он переходит к первому.
Отладчик хотел бы знать, сколько перераспределений может быть выполнено, прежде чем будет создана конфигурация блоков в банках, которая была замечена ранее.
Например, представьте себе сценарий только с четырьмя банками памяти:
Банки начинаются с блоков
0
,2
,7
и0
. В третьем банке больше всего блоков, поэтому он выбирается для перераспределения.
Начиная со следующего банка (четвертого банка), а затем переходя к первому банку, второму банку и т. д., блоки
7
распределяются по банкам памяти. Четвертый, первый и второй банки получают по два блока каждый, а третий банк возвращает один блок. Окончательный результат выглядит так:2 4 1 2
.
Затем выбирается второй банк, поскольку он содержит наибольшее количество блоков (четыре). Поскольку имеется четыре банка памяти, каждый получает по одному блоку. Результат:
3 1 2 3
.
Теперь есть связь между первым и четвертым банками памяти, каждый из которых имеет три блока. Первый банк побеждает в ничьей, и три его блока равномерно распределяются по трем другим банкам, не оставляя ни одного:
0 2 3 4
.
Выбирается четвертый банк, и его четыре блока распределяются таким образом, что каждый из четырех банков получает по одному блоку:
1 3 4 1
.
Выбирается третий банк, и происходит то же самое:
2 4 1 2
.
В этот момент мы достигли состояния, которое видели раньше:
2 4 1 2
уже видели. Бесконечный цикл обнаруживается после пятого цикла перераспределения блоков, поэтому ответ в этом примере —5
.
Учитывая начальное количество блоков во входных данных вашей головоломки, сколько циклов перераспределения должно быть завершено, прежде чем будет создана конфигурация, которая была замечена ранее?
Проблема вторая:
Из любопытства отладчик также хотел бы знать размер цикла: начиная с состояния, которое уже было замечено, сколько циклов перераспределения блоков должно быть выполнено, прежде чем то же самое состояние будет замечено снова?
В приведенном выше примере
2 4 1 2
снова появляется после четырех циклов, поэтому ответ в этом примере будет4
.
Сколько циклов содержится в бесконечном цикле, возникающем из-за конфигурации входных данных вашей головоломки?
Решение:
Примечания:
- Мне было немного лень, поэтому я создал входной массив вручную (см. строку 30)
Но вы также можете прочитать файл (всего одну строку) и построить массив, используя
for i := range string.Fields(строка){ … } - Пришлось встроить вспомогательные функции «FindPosMax» и «IntToStr», потому что в go нет этой встроенной функции. (строка 9 + 25)
- В карте «hist», где «перераспределения блоков» будут сохранены в качестве ключа, я использовал счетчик в качестве значения — так что проблема номер два была легко решена; просто вычтите сохраненное значение из фактического счетчика. (см. строки 48 и 45)
Спасибо за чтение и, возможно, комментарии!
SR.