На карточках записаны числа от 1 до 2007. Одна из карточек покрашена в красный цвет, а остальные – белые. Карточки выложены одна за другой в произвольном порядке. Разрешается поменять красную карточку с любой другой. Как за несколько таких операций можно расположить числа на карточках в порядке возрастания?
Answers & Comments
Verified answer
могу предложить алгоритм:
n = 1
1) если карточка с номером n лежит не на своем месте, то меняем карточку, которая лежит на месте карточки с номером n с красной карточкой (очевидно, если там лежит красная карточка, то пропускаем этот шаг)
2) меняем красную карточку с карточкой с номером n
n := n + 1 (означает, рассматриваем следующий номер карточки, т.е. 2, 3, ... по очереди все)
повторяем шаги 1-2 для нового n
по этому алгоритму за 2007 ходов карточки будут расположены в порядке возрастания, так же не важно какой номер написан на красной карточке.