
Сообщение от
Байт
Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Отнюдь!
Во-первых, авторитет классической книги мы тут оспаривать мы не будем. Задача действительно является жемчужиной.
Во-вторых, в "Жемчужинах программирования" эта задача преподносится в большей степени для иллюстрации того, как формальная эффективность алгоритма (в данном случае - оцениваемая по количеству переносов единичных элементов массива в памяти) может существенно не согласовываться с фактической производительностью реализации этого алгоритма на современных кэшированных архитектурах.
Формально оптимальным решением данной задачи является "жонглирующий" алгоритм, который берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали). Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).
Вопрос поиска алгоримов и эффективных реализаций, которые хорошо себя ведут в таких ситуациях - вопрос весьма и весьма нетривиальный и, во многих случаях, неаналитический, т.е. решаемый только на чисто эмпирической основе.
Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма