Question

семь карточек с числами лежат на столе в таком порядке 3,1,4,5,7,6,2. За один ход разрешается поменять местами любые две карточки. За какое наименьшее число ходов, можно расположить их в порядке убывания

Answer 1

4 хода, но могу ошибаться 

Answer 2

Для того чтобы расположить карточки в порядке убывания, нужно упорядочить их так, чтобы самое большое число было слева, а самое маленькое — справа. Наименьшее число ходов, чтобы достичь этого, равно количеству инверсий в исходной последовательности.

Инверсия — это пара элементов в последовательности, расположенных в неправильном порядке относительно их сортировки. Например, в последовательности [3, 1, 4, 5, 7, 6, 2] есть следующие инверсии: (3, 1), (3, 2), (7, 6), (7, 2), (6, 2). Всего их 5.

Количество инверсий равно минимальному числу ходов для упорядочивания в порядке убывания. В данном случае, это 5 ходов.

Последовательность после всех ходов будет выглядеть так: [7, 6, 5, 4, 3, 2, 1].