Число инверсий
Задача. Найти число инверсий в строке
Решение
Элементы ia=m и ib=n в строке [i1, i2,..., ik]
образуют инверсию, если a < b и m > n.
Рассмотрим последовательно элементы строки.
- Число 4 образует три инверсии с элементами 1,3,2.
- Число 6 образует четыре инверсии с элементами 5,1,3,2.
- Число 5 образует три инверсии с элементами 1,3,2.
- Число 1 не образует инверсий.
- Число 3 образует одну инверсию с 2.
Всего 3+4+3+1=12 инверсий.
Литература
Просветов Г.И. Дискретная математика. Задачи и решения М.: Альфа-Пресс. 2009
|